Something in J6.02 to look forward to. Memo u M. mu lu ru
u M. is the same as u but may keep a record of the argument(s) and results for later look-up and reuse. It is commonly used for multiply-recursive verbs. The current implementation retains results only for arguments that are small non-negative integer atoms. For example: fib=: 3 : 0 M. if. 1>:y do. y else. (fib y-1)+fib y-2 end. ) fibx=: 3 : 0 if. 1>:y do. y else. (fibx y-1)+fibx y-2 end. ) 6!:2 'j=: fib 32' NB. memo version 0.000424922 6!:2 'k=: fibx 32' NB. non-memo version 43.4159 j 2178309 k 2178309 Another example is finding the number of partition of n. The following verbs implement a recurrence relation by Euler, equation 11 in http://mathworld.wolfram.com/PartitionFunctionP.html rec=: 3 : 0 _1>.y--:k*"1 ] _1 1+/3*k=. 1+i.1+<.%:y*0.6666666 ) pn=: 3 : 0 M. if. 0>:y do. 0=y else. -/+/pn"0 rec y end. ) pnx=: 3 : 0 if. 0>:y do. 0=y else. -/+/pnx"0 rec y end. ) 6!:2 'j=: pn 27' NB. memo version 0.00147935 6!:2 'k=: pnx 27' NB. non-memo version 73.649 j 3010 k 3010 Subsequent applications of a memoized verb to the same argument produces the result quickly: 6!:2 'fib 32' 2.5049e_5 6!:2 'pn 27' 2.46019e_5 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
