Search Top Index

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) => */