Catalan numbers/Pascal's triangle: Difference between revisions

Content added Content deleted
m (→‎{{header|Phix}}: bigatom -> mpfr)
Line 1,438: Line 1,438:
-- 35 56
-- 35 56
-- 126 (unused)</lang>
-- 126 (unused)</lang>

⚫
The following bigatom version is over ten times faster than the equivalent on [[Catalan_numbers#Phix|Catalan_numbers]]
=== gmp version ===
{{libheader|bigatom}}
{{libheader|mpfr}}
<lang Phix>include builtins\bigatom.e
<lang Phix>include builtins\mpfr.e


function catalanB(integer n) -- very very fast!
function catalanB(integer n) -- very very fast!
sequence catalan = {},
sequence catalan = mpz_inits(n),
p = repeat(1,n+1)
p = mpz_inits(n+1,1)
mpz p1 = mpz_init(1)
bigatom p1
if n=0 then return 1 end if
if n=0 then return p1 end if
for i=1 to n do
for i=1 to n do
p1 = ba_multiply(p[1],2)
mpz_mul_si(p1,p[1],2)
catalan = append(catalan,ba_sub(p1,p[2]))
mpz_sub(catalan[i],p1,p[2])
for j=1 to n-i+1 do
for j=1 to n-i+1 do
p1 = ba_add(p1,p[j+1])
mpz_add(p1,p1,p[j+1])
p[j] = p1
mpz_set(p[j],p1)
end for
end for
end for
end for
Line 1,458: Line 1,459:
end function
end function
⚫
printf(1,"%d: %s (%s)\n",{100,mpz_get_str(catalanB(100))})
atom t0 = time()
string sc100 = ba_sprint(catalanB(100))
printf(1,"%d: %s (%s)\n",{250,mpz_get_str(catalanB(250))})</lang>
⚫
printf(1,"%d: %s (%3.2fs)\n",{100,sc100,time()-t0})
atom t0 = time()
string sc250 = ba_sprint(catalanB(250))
printf(1,"%d: %s (%3.2fs)\n",{250,sc250,time()-t0})</lang>
{{out}}
{{out}}
<pre>
<pre>
100: 896519947090131496687170070074100632420837521538745909320 (0.08s)
100: 896519947090131496687170070074100632420837521538745909320
250: 465116795969233796497747947259667807407291160080922096111953326525143875193659257831340309862635877995262413955019878805418475969029457769094808256 (1.01s)
250: 465116795969233796497747947259667807407291160080922096111953326525143875193659257831340309862635877995262413955019878805418475969029457769094808256
</pre>
⚫
The above is significantly faster than the equivalent(s) on [[Catalan_numbers#Phix|Catalan_numbers]],
a quick comparison showing the latter getting exponentially worse (then again I memoised the slowest recursive version):
<pre>
800 2000 4000 8000
catalanB: 0.6s 3.5s 14.5s 64s
catalan2m: 0.7s 7.0s 64.9s 644s
</pre>
</pre>


Retrieved from "https://rosettacode.org/wiki/Catalan_numbers/Pascal%27s_triangle"