Rosetta Code

Catalan numbers/Pascal's triangle: Difference between revisions

Page Discussion

Catalan numbers/Pascal's triangle (view source)

Revision as of 02:35, 4 August 2019

127 bytes added ,  4 years ago
m
→‎{{header|Phix}}: bigatom -> mpfr
m (→‎{{header|Phix}}: bigatom -> mpfr)
Line 1,438:
-- 35 56
-- 126 (unused)</lang>
 
The following bigatom version is over ten times faster than the equivalent on [[Catalan_numbers#Phix|Catalan_numbers]]▼
=== gmp version ===
{{libheader|bigatommpfr}}
<lang Phix>include builtins\bigatommpfr.e
 
function catalanB(integer n) -- very very fast!
sequence catalan = {}mpz_inits(n),
p = repeatmpz_inits(1,n+1,1)
mpz p1 = mpz_init(1)
bigatom p1
if n=0 then return 1p1 end if
for i=1 to n do
p1 = ba_multiplympz_mul_si(p1,p[1],2)
catalan = appendmpz_sub(catalan[i],ba_sub(p1,p[2]))
for j=1 to n-i+1 do
p1 = ba_addmpz_add(p1,p1,p[j+1])
mpz_set(p[j] = ,p1)
end for
end for
Line 1,458 ⟶ 1,459:
end function
printf(1,"%d: %s (%3.2fss)\n",{100,sc100,timempz_get_str(catalanB(100))-t0})▼
atom t0 = time()
stringprintf(1,"%d: sc100%s = ba_sprint(%s)\n",{250,mpz_get_str(catalanB(100250))})</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}}
<pre>
100: 896519947090131496687170070074100632420837521538745909320 (0.08s)
250: 465116795969233796497747947259667807407291160080922096111953326525143875193659257831340309862635877995262413955019878805418475969029457769094808256 (1.01s)
</pre>
▲The following bigatom versionabove is over ten timessignificantly 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>
 
Petelomax
7,803

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/230256"