TEACH MEMOFUNCTION Aaron sloman
27 Nov 2011
Using a MemoFunction to Speed Up Fibonacci
------------------------------------------
Introduction
There are many procedures that handle a complex problem by dealing with a
simpler version, using the result of that, and then adding a final step.
An example is factorial: in order to find the factorial of N, if N > 0 you work
out the factorial of N-1, then multiply by N. If N - 0 then the factorial is 1.
For negative N, Factorial(N) is not defined. So factorial(-3) should produce an
error message, but we'll ignore tha.
The factorial function therefore does one multiplication for factorial 1, 2 for
factorial 2, 3 for factorial 3, etc. So in order to find the factorial of a
large number N you need to perform a large multiplication. But that large
multiplication will need to be repeated for all numbers larter than N.
Can we avoid the repetition by storing intermediate cases? Yes, by using a memo
function, which works by checking whether it is being asked to repeat something
done previously. If so it looks up the previous result and returns that.
otherwise it computes the new result, and stores it for future use.
define remember_factorial(N) -> result;
lconstant fact_memo = newproperty([[0 1]], 1000, false, "perm");
;;; see of factorial N is alread in fact_memo
fact_memo(N) -> result;
if result then
;;; nothing else to do
else
[ remembered: ^(fact_memo(N-1))] =>
;;; compute new value from previous one.
N * remember_factorial(N-1) -> result;
;;; remember the result for future use
result -> fact_memo(N)
endif
enddefine;
/*
;;;test it:
timediff() ->;
remember_factorial(0) =>
remember_factorial(1) =>
remember_factorial(2) =>
remember_factorial(3) =>
remember_factorial(100) =>
remember_factorial(101) =>
*/