Continuous memoization

Details Continuous memoization Continuous memoization

2000-01-21

2003-04-22

Ngo, Chuong Dinh (Department: 2124)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

Reexamination Certificate

active

06553394

ABSTRACT:

FIELD OF THE INVENTION
This invention relates generally to decreasing the number of computations that need to be done in a computer system, and more particularly to using memoization to reduce the number of computations.
BACKGROUND OF THE INVENTION
The term “memoization” is known in the field of computer science as a technique for recording and remembering the results of previous computations so that repeating the same computations can be avoided, see Field et al., in “Memoization,” Addison-Wesley Publishing Company Functional Programming, Chapter 19, pp. 505-506, 1988. The term comes from the word “memo”—“A short note written as a reminder,” The American Heritage Dictionary of the English Language, 1970, American Heritage Publishing. Memorization techniques have also been used to save results of data dependence tests in order to avoid calling data dependence routines multiple times for the same input. See, Dror Maydan, et al., in “Efficient and Exact Data Dependence Analysis,” Proceedings of the ACMSIGPLAN 1991.
For example, it is desired to compute the Fibonacci numbers using the following simple program:
fib(n) {
if n is 1 or 2, return 1;
return fib(n−1)+fib(n−2);
}
A method
100
for performing this computation is shown in FIG.
1
. The input parameters (I) are provided in step
110
. The computation itself (F) is done in step
120
, and the result (R) is provided in step
130
. Because fib( ) is recomputed over and over for the same argument, run time for the above method is O(1.6
n
).
A more complex program computes the Fibonacci numbers as follows:
allocate array for memo, initializing all elements to zero initialize memo[
1
] and memo[
2
] to 1;
fib(n) {
if memo[n] is not zero, return memo[n];
memo[n]=fib(n−1) +fib(n−2);
return memo[n];
}
When the value of fib(n) is memoized, the run time is reduced and becomes O(1) if n is in the memo and O(n) if n is not in the memo.
FIG. 2
shows how memoization is used to speed up the method. As above input
210
is provided in step
210
. Step
215
determines whether a result (R) for this particular input (I) is contained in a memo
216
. If true, the memo is read and the result (R) is provided in step
230
. Otherwise, if false, compute the result (R). in step
220
, memoize the result in the memo, and provide the result in step
230
.
The problem with this method is that the input must exactly match what is contained in the memo, that is the memo is limited to storing and producing discrete values, and thus the prior art memoization method has limited utility. The need remains to provide a more efficient and versatile memoization method.
SUMMARY OF THE INVENTION
A method memoizes a computation as follows. A set of input parameters are provided to the computation. A determination is made to see whether a memo contains results of the computation on sets of memoized parameters near the set of input parameters. If true, the computation for the set of input parameters is reconstructed using the results of the computations on the sets of memoized parameters near the set of input parameters. If false, the computation is performed using the set of input parameters. A result of the computation on the set of input parameters is then memoized, and that result is provided as output of the computation.
Reconstruction can be done by applying some continuous function, such as interpolation, on the memoized results. Additionally, the computation can be partitioned into a number of partial computations, and only selected partial computations are memoized.


REFERENCES:
patent: 3846625 (1974-11-01), Sasayama
patent: 3996456 (1976-12-01), Hoover
patent: 5260898 (1993-11-01), Richardson
patent: 5819102 (1998-10-01), Reed et al.
patent: 5828591 (1998-10-01), Rotstain
patent: 5862400 (1999-01-01), Reed et al.
patent: 5987254 (1999-11-01), Subrahmanyam
patent: 6223192 (2001-04-01), Oberman et al.
patent: 6256653 (2001-07-01), Juffa et al.
patent: 6263323 (2001-07-01), Baggett
Baggett, Technique for Producing Constructed Fares, May 2, 2002, U.S. patent application Publication No. US 2002/0052854 A1.

Affiliated with

Also associated with

Rating

Continuous memoization does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Continuous memoization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Continuous memoization will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3075038