US4674039A — Method for determining whether a given value is i…

Claim 1

Independent Claim 344 words

A method for operating a digital computer that includes computer memory means to determine whether a given value is included in an ordered table of values stored in the computer memory means and, if so, the position in the table at which the given value is included, the method comprising: (a) defining a lower boundary position as the first table position in the computer memory means and a lower boundary value as the value in the lower boundary position; (b) defining an upper boundary position as the last table position in the computer memory means and an upper boundary value as the value in the upper boundary position; (c) determining by interpolation an assumed position for the given value in the computer memory means between the lower and upper boundary positions; (d) comparing the value in the assumed position to the given value, and if they are equal, then causing the computer to indicate that the given value is in the table at the assumed position, and terminating the process; (e) when the value at the assumed position is greater than the given value, adjusting the upper boundary position towards the assumed position, redefining the upper boundary value as the value at the adjusted upper boundary position, and adjusting the value of the lower boundary value towards the given value by setting the lower boundary value equal to an average of the unadjusted lower boundary value and the given value; (f) when the value at the assumed position is less than the given value, adjusting the lower boundary position towards the assumed position, redefining the lower boundary value as the value at the adjusted lower boundary position, and adjusting the value of the upper boundary value towards the given value by setting the upper boundary value equal to an average of the unadjusted upper boundary value and the given value; and, (g) repeating the operations of steps (c)-(f) until the value in the assumed position is equal to the given value or until the upper and lower boundary positions are adjacent to one another.

Claim 2

Independent Claim 344 words

A method for operating a digital computer that includes computer memory means to determine whether a given value is included in an ordered table of values stored in the computer memory means and, if so, the position in the table at which the given value is included, the method comprising: (a) defining a lower boundary position as the first table position in the computer memory means and a lower boundary value as the value in the lower boundary position; (b) defining an upper boundary position as the last table position in the computer memory means and an upper boundary value as the value in the upper boundary position; (c) determining by interpolation an assumed position for the given value in the computer memory means between the lower and upper boundary positions; (d) comparing the value in the assumed position to the given value, and if they are equal, then causing the computer to indicate that the given value is in the table at the assumed position, and terminating the process; (e) when the value at the assumed position is greater than the given value, adjusting the upper boundary position towards the assumed position, redefining the upper boundary value as the value at the adjusted upper boundary position, and adjusting the value of the lower boundary value towards the given value by setting the lower boundary value equal to an average of the unadjusted lower boundary value and the given value; (f) when the value at the assumed position is less than the given value, adjusting the lower boundary position towards the assumed position, redefining the lower boundary value as the value at the adjusted lower boundary position, and adjusting the value of the upper boundary value towards the given value by setting the upper boundary value equal to an average of the unadjusted upper boundary value and the given value; and, (g) repeating the operations of steps (c)-(f) until the value in the assumed position is equal to the given value or until the upper and lower boundary positions are adjacent to one another.

Claim 3

Dependent Claim 38 words

The method of claim 1, wherein an assumed position is determined for the given value based upon the assumption that the values between the upper and lower boundary values change uniformly between the lower and upper boundary positions.

Claim 4

Dependent Claim 56 words

The method of claim 1, wherein the upper boundary position is set equal to the assumed position when the value at the assumed position is greater than the given value, and wherein the lower boundary position is set equal to the assumed position when the value at the assumed position is less than the given value.

Claim 5

Dependent Claim 77 words

The method of claim 1, comprising the further step of establishing a maximum repeat count prior to performing step (c) for the first time, and wherein step (g) comprises repeating the operations of steps (c)-(f) until the value in the assumed position is equal to the given value, until the upper and lower boundary positions are adjacent to one another, or until steps (c)-(f) have been repeated a number of times equal to the maximum repeat count.

Claim 6

Dependent Claim 35 words

The method of claim 4, comprising the further step of performing a binary search for the given value between the upper and lower boundary positions whenever the maximum repeat count is reached in step (g).

Claim 7

Dependent Claim 38 words

The method of claim 5, wherein the maximum repeat count is based upon the average number of iterations that would be required to determine that the given value is not in the table using a binary search technique.

Claim 8

Dependent Claim 31 words

The method of claim 6, wherein the maximum repeat count is proportional to the natural logorithm of the number of positions in the table divided by the natural logorithm of two.

Claim 9

Independent Claim 622 words

A method for operating a digital computer that includes computer memory means to determine whether a given value is included in an ordered table of values stored in the computer memory means and, if so, the position in the table at which the given value is included, the method comprising: (a) defining a lower boundary position as the first table position in the computer memory means and a lower boundary value as the value in the lower boundary position; (b) defining an upper boundary position as the last table position in the computer memory means and an upper boundary value as the value in the upper boundary position; (c) determining by interpolation an assumed position for the given value in the computer memory means between the lower and upper boundary positions; (d) comparing the value in the assumed position to the given value, proceeding to step (e) if they are equal, proceeding to step (f) if the value in the assumed position is greater than the given value, and proceeding to step (k) if the value in the assumed position is less than the given value; (e) causing the computer to indicate that the given value is in the table at the assumed position, and terminating the process; (f) adjusting the upper boundary position towards the assumed position, redefining the upper boundary value as the value at the adjusted upper boundary position, and adjusting the value of the lower boundary value towards the given value by setting the lower boundary value equal to an average of the unadjusted lower boundary value and the given value; (g) determining by interpolation an assumed position for the given value in the computer memory means between the lower and upper boundary positions; (h) comparing the value in the assumed position to the given value, proceeding to step (e) if they are equal, proceeding to step (f) if the value in the assumed position is greater than the given value, and proceeding to step (i) if the value in the assumed position is less than the given value; (i) comparing the upper and lower boundary positions, and proceeding to step (p) if they are adjacent to one another, and proceeding to step (j) if they are not adjacent to one another; (j) adjusting the lower boundary position towards the assumed position, redefining the lower boundary value as the value at the adjusted lower boundary position, and proceeding to step (c); (k) adjusting the lower boundary position towards the assumed position, redefining the lower boundary value as the value of the adjusted lower boundary position, and adjusting the value of the upper boundary value towards the given value by setting the upper boundary value equal to an average of the unadjusted upper boundary value and the given value; (l) determining by interpolation an assumed position for the given value in the computer memory means between the lower and upper boundary positions; (m) comparing the value in the assumed position to the given value, proceeding to step (e) if they are equal, proceeding to step (n) if the value in the assumed position is greater than the given value, and proceeding to step (k) if the value in the assumed position is less than the given value; (n) comparing the upper and lower boundary positions, and proceeding to step (p) if they are adjacent to one another, and proceeding to step (o) if they are not adjacent to one another; (o) adjusting the upper boundary position towards the assumed position, redefining the upper boundary value as the value of the adjusted upper boundary position, and proceeding to step (c); and (p) causing the computer to indicate that the given value is not in the table, and terminating the process.

Claim 10

Independent Claim 622 words

A method for operating a digital computer that includes computer memory means to determine whether a given value is included in an ordered table of values stored in the computer memory means and, if so, the position in the table at which the given value is included, the method comprising: (a) defining a lower boundary position as the first table position in the computer memory means and a lower boundary value as the value in the lower boundary position; (b) defining an upper boundary position as the last table position in the computer memory means and an upper boundary value as the value in the upper boundary position; (c) determining by interpolation an assumed position for the given value in the computer memory means between the lower and upper boundary positions; (d) comparing the value in the assumed position to the given value, proceeding to step (e) if they are equal, proceeding to step (f) if the value in the assumed position is greater than the given value, and proceeding to step (k) if the value in the assumed position is less than the given value; (e) causing the computer to indicate that the given value is in the table at the assumed position, and terminating the process; (f) adjusting the upper boundary position towards the assumed position, redefining the upper boundary value as the value at the adjusted upper boundary position, and adjusting the value of the lower boundary value towards the given value by setting the lower boundary value equal to an average of the unadjusted lower boundary value and the given value; (g) determining by interpolation an assumed position for the given value in the computer memory means between the lower and upper boundary positions; (h) comparing the value in the assumed position to the given value, proceeding to step (e) if they are equal, proceeding to step (f) if the value in the assumed position is greater than the given value, and proceeding to step (i) if the value in the assumed position is less than the given value; (i) comparing the upper and lower boundary positions, and proceeding to step (p) if they are adjacent to one another, and proceeding to step (j) if they are not adjacent to one another; (j) adjusting the lower boundary position towards the assumed position, redefining the lower boundary value as the value at the adjusted lower boundary position, and proceeding to step (c); (k) adjusting the lower boundary position towards the assumed position, redefining the lower boundary value as the value of the adjusted lower boundary position, and adjusting the value of the upper boundary value towards the given value by setting the upper boundary value equal to an average of the unadjusted upper boundary value and the given value; (l) determining by interpolation an assumed position for the given value in the computer memory means between the lower and upper boundary positions; (m) comparing the value in the assumed position to the given value, proceeding to step (e) if they are equal, proceeding to step (n) if the value in the assumed position is greater than the given value, and proceeding to step (k) if the value in the assumed position is less than the given value; (n) comparing the upper and lower boundary positions, and proceeding to step (p) if they are adjacent to one another, and proceeding to step (o) if they are not adjacent to one another; (o) adjusting the upper boundary position towards the assumed position, redefining the upper boundary value as the value of the adjusted upper boundary position, and proceeding to step (c); and (p) causing the computer to indicate that the given value is not in the table, and terminating the process.

Claim 11

Dependent Claim 44 words

The method of claim 8, wherein an assumed position is determined for the given value in steps (c), (g) and (l), based on the assumption that the values between the upper and lower boundary values change uniformly between the lower and upper boundary positions.

Claim 12

Dependent Claim 41 words

The method of claim 8, wherein in the upper boundary position is set equal to the assumed position in steps (f) and (o), and wherein the lower boundary position is set equal to the assumed position in steps (j) and (k).

Claim 13

Dependent Claim 106 words

The method of claim 8, comprising the further step of establishing a maximum repeat count prior to performing step (c) for the first time, wherein an iteration counter is incremented by one each time that a new assumed position is determined in step (c), (g) or (l), and wherein steps (i) and (n) include comparing the iteration counter to the maximum repeat count whenever the upper and lower boundary positions are not adjacent to one another, and performing a binary search for the given value between the upper and lower boundary positions whenever the iteration counter is greater than or equal to the maximum repeat count.

Claim 14

Dependent Claim 38 words

The method of claim 11, wherein the maximum repeat count is based upon the average number of iterations that would be required to determine that the given value is not in the table using a binary search technique.

Claim 15

Dependent Claim 31 words

The method of claim 12, wherein the maximum repeat count is proportional to the natural logorithm of the number of positions in the table divided by the natural logorithm of two.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	1990-06-15	1990-12-15	1991-06-16	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	1994-06-15	1994-12-15	1995-06-16	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	1998-06-15	1998-12-15	1999-06-16	$7700.00	Window Closed / Lapsed

Method for determining whether a given value is included in an ordered table of values stored in a computer readable memory

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag