Catalan numbers: Difference between revisions

Line 2,376:

-- An explicitly memoized version of what seems to be the best, and the one that really needed it:

-- (and in fact it turned out to be faster than ~~a similarily~~ memoized ~~version~~ of ~~catalan3~~)

-- (and in fact it turned out to be faster than similarly memoized versions of 1 and 3, when atom)

-- I also converted this to use bigatoms.

include builtins\bigatom.e

sequence c2cache = {}

function ~~catalan2c~~(integer n) -- very fast!

function catalan2bc(integer n) -- very fast!

object r

atom r = not n

if n>0 then

if n<=0 then return BA_ONE end if

if n<=length(c2cache) then

r = c2cache[n]

if r!=0 then return r end if

else

c2cache &= repeat(0,n-length(c2cache))

end if

for i=0 to n-1 do

r += catalan2c(i) * catalan2c(n-1-i)

end for

c2cache[n] = r

end if

r = BA_ZERO

for i=0 to n-1 do

r = ba_add(r,ba_multiply(catalan2bc(i),catalan2bc(n-1-i)))

end for

c2cache[n] = r

return r

end function~~</lang>~~

end function

atom t0 = time() -- (this last call only)

string sc100 = ba_sprint(catalan2bc(100))

printf(1,"100: %s (%3.2fs)\n",{sc100,time()-t0})</lang>

<pre>

Line 2,414:

Line 2,421:

14: 2674440 2674440 2674440

15: 9694845 9694845 9694845

100: 896519947090131496687170070074100632420837521538745909320 (0.42s)

</pre>