US3789203A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Function generation by approximation employing interative interpolation
Assignee: Gemalto Terminals Ltd
•
Filing: 1971-07-16
•
Granted: 1974-01-29
•
Expires: 1991-07-16
Abstract
Abstract A method of solving a function for values of a variable when values of an independent variable are given, the method being especially valuable for use in or with a computer, an advantage being minimization of storage requirements. The method is an extension of the branch of mathematics known as numerical analysis, and specifically of the division of that branch known as approximation. An expression is developed for a locus of points which approach points on the given function, i.e., a polynomial expression having a high degree of convergence. The method includes finding solutions to the terms of the polynomial expression by reiterated interpolation. Only a relatively small number of factors need be stored. The method can be employed to calculate values to predetermined accuracy, and is suitable for many functions although it is especially well suited for many transcendental functions. Embodiments of apparatus suitable for performing the method are also disclosed. The apparatus includes elements of electronic data processing such as shift registers, adders, and the like to perform the interpolation involving addition, subtraction and division by 2. The algorithm developed as a manifestation of this method is describable as an add-shift algorithm.
Inventors
- 👤 R Catherall
- 👤 S Knowles
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 19:22
CPC Classifications
G; G06; G06F; G06F17/00; G06F17/10; G06F17/17; G06F7/00; G06F7/38; G06F7/48; G06F7/544
Claims Analysis
Total Claims: 25
Claim 1
Independent Claim
146 words
In a digital system a method of approximating a desired value of a function included within a segment between two selected function point values, the method comprising the steps of interpolating between first and second digital signals representative of the two point values to generate a digital signal representative of a midpoint point value, compensating the result of the interpolation to generate a digital signal representative of a new function point value, replacing one of the first and second digital signals representative of two function point values by said new digital function point value signal thus generated to define a next segment which includes the desired value of the function, and repeating the steps of interpolating, compensating and replacing in successively smaller next segments containing the desired value of the function until the new point approaches the desired value to within a preselected degree of accuracy.
Claim 2
Dependent Claim
146 words
In a digital system a method of approximating a desired value of a function included within a segment between two selected function point values, the method comprising the steps of interpolating between first and second digital signals representative of the two point values to generate a digital signal representative of a midpoint point value, compensating the result of the interpolation to generate a digital signal representative of a new function point value, replacing one of the first and second digital signals representative of two function point values by said new digital function point value signal thus generated to define a next segment which includes the desired value of the function, and repeating the steps of interpolating, compensating and replacing in successively smaller next segments containing the desired value of the function until the new point approaches the desired value to within a preselected degree of accuracy.
Claim 3
Dependent Claim
32 words
A method according to claim 1 wherein the step of compensating comprises algebraically combining a digital signal representative of a correcting term with the digital midpoint signal generated by the linear interpolation.
Claim 4
Dependent Claim
195 words
In a digital system a method of automatically calculating an approximate value of a function of an independent variable by midpoint interpolation between two stored point values defining a segment comprising the steps of adding digital signals representative of the two stored point values to obtain a digital signal representative of the sum of the two stored point values, dividing by two the sum of first and second digital signals representative of the two stored point values to generate a digital midpoint signal, storing a digital signal representative of a predetermined value of a first correcting term, compensating at least a first one of the new digital midpoint signals thus generated by the addition of at least one first correcting term to form a compensated digital midpoint signal, replacing one of said first and second digital signals representative of the two stored point values by said compensated digital midpoint signal generated by compensating the midpoint interpolation to create a new segment containing a given value of the independent variable, repeating the steps of adding, dividing, compensating and replacing to generate new digital signals defining successively smaller segments having end points converging upon the given value.
Claim 5
Dependent Claim
195 words
In a digital system a method of automatically calculating an approximate value of a function of an independent variable by midpoint interpolation between two stored point values defining a segment comprising the steps of adding digital signals representative of the two stored point values to obtain a digital signal representative of the sum of the two stored point values, dividing by two the sum of first and second digital signals representative of the two stored point values to generate a digital midpoint signal, storing a digital signal representative of a predetermined value of a first correcting term, compensating at least a first one of the new digital midpoint signals thus generated by the addition of at least one first correcting term to form a compensated digital midpoint signal, replacing one of said first and second digital signals representative of the two stored point values by said compensated digital midpoint signal generated by compensating the midpoint interpolation to create a new segment containing a given value of the independent variable, repeating the steps of adding, dividing, compensating and replacing to generate new digital signals defining successively smaller segments having end points converging upon the given value.
Claim 6
Dependent Claim
46 words
A method according to claim 3, wherein the steps of compensating further comprises the step of dividing the stored digital signal representative of a predetermined value of a first correcting term successively by four to form a second correcting term for the successive steps of repeating.
Claim 7
Dependent Claim
35 words
A method according to claim 4, wherein the step of compensating further comprises the steps of dividing the second correcting term successively by eight to form a third correcting item for successive steps of repeating.
Claim 8
Dependent Claim
69 words
A method according to claim 3, wherein the step of compensating further comprises the step of dividing by a power of two the value of the previous correcting term to generate a digital signal representative of a new correcting term for compensating at least some newly generated digital midpoint signals before each successive step of repeating and wherein the power of two is related to the step of repeating.
Claim 9
Dependent Claim
44 words
A method according to claim 6, wherein the step of compensating further includes the step of modifying the digital signal representative of the new correcting term by combining therewith a signal representative of a cross term which is a multiple of another correcting term.
Claim 10
Dependent Claim
49 words
A method according to claim 6, wherein the sign of at least one of the digital signals representative of the terms is dependent upon whether the new segment created after the step of replacing is Up or DOWN with respect to the new value generated in the current interpolation.
Claim 11
Dependent Claim
50 words
A method accorDing to claim 6, wherein the sign of at least one of the digital signals representative of the terms is made dependent upon whether the new segment created after the step of replacing was UP or DOWN with respect to the new value generated in the previous interpolation.
Claim 12
Dependent Claim
58 words
A method according to claim 3, wherein the step of compensating further comprises calculating a plurality of digital signals representative of the initial values of the correcting terms, the correcting terms being calculated by the method steps of adding, dividing, storing, compensating, replacing and repeating the same as automatically calculating approximate values of functions of another independent variable.
Claim 13
Dependent Claim
65 words
A method according to claim 3, wherein the step of compensating further includes generating digital signals representative of initial values of the correcting terms, the values being calculated at intervals during the steps of interpolation in real time operation from given point values of the function and, between such intervals, values of the function intermediate the point values are calculated by the steps of interpolation.
Claim 14
Dependent Claim
179 words
Apparatus for interpolating a function of an independent variable to determine the value of the function of a given value of the independent variable, comprising means for storing digital signals representative of two point values of the function at the ends of a segment containing the said given value, means responsive to said means for storing for adding two point values to generate a digital signal representative of the sum value, dividing means responsive to said means for adding for generating a digital signal representative of a half sum value, means responsive to said dividing means for modifying said half sum value by a signal representative of at least one correcting term, control means responsive to said means for modifying for replacing one of the stored point values by the modified half sum value to establish digital signals representative of two point values at the end of a shorter segment containing the said given value, and timing means for timing the operation of said apparatus iteratively so that successively smaller segments of interpolation converge upon the said given value.
Claim 15
Dependent Claim
179 words
Apparatus for interpolating a function of an independent variable to determine the value of the function of a given value of the independent variable, comprising means for storing digital signals representative of two point values of the function at the ends of a segment containing the said given value, means responsive to said means for storing for adding two point values to generate a digital signal representative of the sum value, dividing means responsive to said means for adding for generating a digital signal representative of a half sum value, means responsive to said dividing means for modifying said half sum value by a signal representative of at least one correcting term, control means responsive to said means for modifying for replacing one of the stored point values by the modified half sum value to establish digital signals representative of two point values at the end of a shorter segment containing the said given value, and timing means for timing the operation of said apparatus iteratively so that successively smaller segments of interpolation converge upon the said given value.
Claim 16
Dependent Claim
31 words
Apparatus according to claim 12, wherein said means for modifying combines said signals representative of the at least one correcting term algebraically with said signals representative of the half sum value.
Claim 17
Dependent Claim
39 words
Apparatus according to claim 12 wherein said means for modifying includes a store for storing signals representative of a plurality of correcting terms, and means for extracting the correcting term signals from said store during a plurality of interpolations.
Claim 18
Dependent Claim
49 words
Apparatus according to claim 12 wherein said means for modifying includes at least one store for storing said signals representative of a correcting term to be used in a succession of interpolations, and means for dividing said correcting term signals by a higher power of 2 following each interpolation.
Claim 19
Dependent Claim
54 words
Apparatus according to claim 15, wherein said means for modifying is adapted to store signals representative of a sequence of correcting terms starting from a quadratic term and further comprises first means for dividing the signals representative of said correcting terms by 4 and the successively higher powers of 2, respectively, following each interpolation.
Claim 20
Dependent Claim
52 words
Apparatus according to claim 16, wherein said means for modifying further includes means for adding at least one signal representative of a higher order term to a signal representative of at least one of said correcting terms and second means for dividing said higher order term by its corresponding power of two.
Claim 21
Dependent Claim
44 words
Apparatus according to claim 17, wherein said means for modifying further includes means for adding a signal representative of at least one correcting term with a signal representative of a multiple of at least one higher order term to form a modifying multiple signal.
Claim 22
Dependent Claim
54 words
Apparatus according to cLaim 18, wherein said means for modifying further includes means responsive to said control means for selecting the sign of said modifying multiple signal and wherein said sign is determined by which of the two stored point value signals was replaced by the half sum value signal in the preceding interpolation.
Claim 23
Dependent Claim
73 words
Apparatus according to claim 12, wherein said control means includes a binary register for holding a signal representative of a given value of the independent variable and means for examining the bits in this register in ordered sequence at the rate of one per interpolation to determine in accordance with the value of the bit which of the two stored point value signals is to be replaced by the half sum value signal.
Claim 24
Dependent Claim
87 words
Apparatus according to claim 12 wherein said means for storing digital signals representative of the point values includes a plurality of shift registers; and means for modifying includes at least one shift register for storing at least one correcting term signal and said means for adding includes a plurality of full adders for adding the contents of registers in bit serial, word parallel operation, with a plurality of recirculating correction signals for re-entering said sum value signals and signals representative of the correcting terms in the registers.
Claim 25
Dependent Claim
47 words
Apparatus according to claim 21, wherein said control means further includes logic means to overshift the quantities re-entering the shift registers to effect division of the sum value signal by 2 and division of the signals representative of the correcting terms by their corresponding powers of 2.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1977-01-28 | 1977-07-30 | 1978-01-29 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1981-01-28 | 1981-07-30 | 1982-01-29 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1985-01-28 | 1985-07-30 | 1986-01-29 | $7700.00 | Window Closed / Lapsed |