Search                        Top                                  Index
TEACH MEMOFUNCTION                                                  Aaron sloman
                                                                     27 Nov 2011

Using a MemoFunction to Speed Up Fibonacci

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


        [ 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)



;;;test it:

timediff() ->;
remember_factorial(0) =>
remember_factorial(1) =>
remember_factorial(2) =>
remember_factorial(3) =>
remember_factorial(100) =>

remember_factorial(101) =>