Catalan numbers: Difference between revisions
→{{header|Phix}}: bigatom -> mpfr
(→{{header|Phix}}: bigatom -> mpfr) |
|||
Line 3,051:
=={{header|Phix}}==
{{libheader|bigatom}}▼
See also [[Catalan_numbers/Pascal%27s_triangle#Phix]] which may be faster.
<lang Phix>-- returns inf/-nan for n>85, and needs the rounding for n>=14, accurate to n=29
Line 3,057 ⟶ 3,056:
return floor(factorial(2*n)/(factorial(n+1)*factorial(n))+0.5)
end function
-- returns inf for n>519, accurate to n=30:
function catalan2(integer n) -- NB: very slow!
Line 3,067 ⟶ 3,066:
return res
end function
-- returns inf for n>514, accurate to n=30:
function catalan3(integer n)
Line 3,073 ⟶ 3,072:
return 2*(2*n-1)/(1+n)*catalan3(n-1)
end function
sequence res = repeat(repeat(0,4),16),
for i=0 to 15 do▼
for t=1 to 4 do
atom t0 = time()
▲ for i=0 to 15 do
switch t do
case 1: res[i+1][2] = catalan1(i)
case 2: res[i+1][3] = catalan2(i)
case 3: res[i+1][4] = catalan3(i)
case 4: res[i+1][1] = i; printf(1,"%2d: %10d %10d %10d\n",res[i+1])
end for▼
times[t] = elapsed(time()-t0)
end for
{{out}} ▼
include builtins\bigatom.e▼
sequence c2cache = {}▼
function catalan2bc(integer n) -- very fast!▼
object r -- result (a bigatom)▼
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
r = BA_ZERO▼
for i=0 to n-1 do▼
▲ end for
c2cache[n] = r▼
return r▼
end function▼
▲printf(1,"100: %s (%3.2fs)\n",{sc100,time()-t0})</lang>
▲{{out}}
<pre>
0: 1 1 1
Line 3,124 ⟶ 3,107:
14: 2674440 2674440 2674440
15: 9694845 9694845 9694845
times: 0s 1.6s 0s
100: 896519947090131496687170070074100632420837521538745909320 (0.42s)▼
</pre>
As expected, catalan2() is by far the slowest, so let's memoise that one!
== memoized recursive gmp version ==
▲sequence c2cache = {}
-- (nb: modifying result will mess up cache)
▲ 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
mpz t = mpz_init()
▲ for i=0 to n-1 do
mpz_mul(t,catalan2m(i),catalan2m(n-1-i))
mpz_add(r,r,t)
end for
t = mpz_free(t)
▲ c2cache[n] = r
▲ return r
▲end function
sequence s = {}
for i=0 to 15 do s = append(s,mpz_get_str(catalan2m(i))) end for
printf(1,"0..15: %s\n",join(s,","))
printf(1,"100: %s\n",{mpz_get_str(catalan2m(100))})</lang>
{{out}}
<pre>
0..15: 1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845
</pre>
| |||