Jump to content

Paraffins: Difference between revisions

Paraffins (view source)

Revision as of 14:29, 19 March 2022

28,659 bytes added ,  2 years ago
→‎{{header|Phix}}: syntax coloured, added gmp version
(Added 11l)
(→‎{{header|Phix}}: syntax coloured, added gmp version)
Line 2,127:
{{trans|Ruby}}
{{trans|FreeBASIC}}
Using IEEE754 floats, hence imprecise above n=45 on 32 bit, n=52 on 64bit, tested to n=500600, giving 63.988e21799378e+262 using %g format.
<!--<lang Phix>constant MAX_N = 32,(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
BRANCH = 4
<span style="color: #008080;">constant</span> <span style="color: #000000;">MAX_N</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">32</span><span style="color: #0000FF;">,</span>
 
<span style="color: #000000;">BRANCH</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">4</span>
sequence {rooted,unrooted} @= repeat(0,MAX_N+2)
 
<span style="color: #004080;">sequence</span> <span style="color: #000000;">rooted</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">MAX_N</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">),</span>
procedure tree(integer br, n, l=n, tot=1, atom cnt=1)
<span style="color: #000000;">unrooted</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">MAX_N</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
atom c
for b=br+1 to BRANCH do
<span style="color: #008080;">procedure</span> <span style="color: #000000;">tree</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">br</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">=</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">tot</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">atom</span> <span style="color: #000000;">cnt</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
tot += n
<span style="color: #004080;">atom</span> <span style="color: #000000;">c</span>
if tot>=MAX_N+1
<span style="color: #008080;">for</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">=</span><span style="color: #000000;">br</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">BRANCH</span> <span style="color: #008080;">do</span>
or (l*2>=tot and b>=BRANCH) then
<span style="color: #000000;">tot</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">n</span>
return
<span style="color: #008080;">if</span> <span style="color: #000000;">tot</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">MAX_N</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span>
end if
<span style="color: #008080;">or</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">l</span><span style="color: #0000FF;">*</span><span style="color: #000000;">2</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">tot</span> <span style="color: #008080;">and</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">BRANCH</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
if b==br+1 then
c <span style="color: rooted[n+1]*cnt#008080;">return</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
else
<span style="color: #004080;">integer</span> <span style="color: #000000;">n1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span>
c *= (rooted[n+1]+(b-br-1))/(b-br)
<span style="color: #000000;">t1</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tot</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span>
end if
<span style="color: #008080;">if</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">==</span><span style="color: #000000;">br</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
if l*2<tot then
<span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rooted</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n1</span><span style="color: #0000FF;">]*</span><span style="color: #000000;">cnt</span>
unrooted[tot+1] += c
<span style="color: #008080;">else</span>
end if
<span style="color: #000000;">c</span> <span style="color: #0000FF;">*=</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">rooted</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n1</span><span style="color: #0000FF;">]+(</span><span style="color: #000000;">b</span><span style="color: #0000FF;">-</span><span style="color: #000000;">br</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">))/(</span><span style="color: #000000;">b</span><span style="color: #0000FF;">-</span><span style="color: #000000;">br</span><span style="color: #0000FF;">)</span>
if b<BRANCH then
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
rooted[tot+1] += c
<span style="color: #008080;">if</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">*</span><span style="color: #000000;">2</span><span style="color: #0000FF;"><</span><span style="color: #000000;">tot</span> <span style="color: #008080;">then</span>
for m=1 to n-1 do
<span style="color: #000000;">unrooted</span><span style="color: #0000FF;">[</span><span style="color: #000000;">t1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">c</span>
tree(b,m,l,tot,c)
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
end for
<span style="color: #008080;">if</span> <span style="color: #000000;">b</span><span style="color: #0000FF;"><</span><span style="color: #000000;">BRANCH</span> <span style="color: #008080;">then</span>
end if
<span style="color: #000000;">rooted</span><span style="color: #0000FF;">[</span><span style="color: #000000;">t1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">c</span>
end for
<span style="color: #008080;">for</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
end procedure
<span style="color: #000000;">tree</span><span style="color: #0000FF;">(</span><span style="color: #000000;">b</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m</span><span style="color: #0000FF;">,</span><span style="color: #000000;">l</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tot</span><span style="color: #0000FF;">,</span><span style="color: #000000;">c</span><span style="color: #0000FF;">)</span>
 
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
procedure bicenter(integer s)
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
if mod(s,2)=0 then
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
atom aux = rooted[s/2+1]
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
unrooted[s+1] += aux*(aux+1)/2
end if
<span style="color: #008080;">procedure</span> <span style="color: #000000;">bicenter</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
end procedure
<span style="color: #008080;">if</span> <span style="color: #7060A8;">even</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
 
<span style="color: #004080;">atom</span> <span style="color: #000000;">aux</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rooted</span><span style="color: #0000FF;">[</span><span style="color: #000000;">s</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
rooted[1..2] = 1
<span style="color: #000000;">s</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
unrooted[1..2] = 1
<span style="color: #000000;">unrooted</span><span style="color: #0000FF;">[</span><span style="color: #000000;">s</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">aux</span><span style="color: #0000FF;">*(</span><span style="color: #000000;">aux</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">2</span>
for n=1 to MAX_N do
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
tree(0, n)
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
bicenter(n)
if n<10 or n=MAX_N then
<span style="color: #000000;">rooted</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
printf(1,"%d: %d\n",{n, unrooted[n+1]})
<span style="color: #000000;">unrooted</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
end if
<span style="color: #008080;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">MAX_N</span> <span style="color: #008080;">do</span>
end for</lang>
<span style="color: #000000;">tree</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">bicenter</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;"><</span><span style="color: #000000;">10</span> <span style="color: #008080;">or</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">MAX_N</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d: %d\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">unrooted</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</lang>-->
{{out}}
<pre>
Line 2,186 ⟶ 2,193:
9: 35
32: 27711253769
</pre>
And the same thing using gmp, obviously without any such accuracy limits
<!--<lang Phix>(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">max_n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">200</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">branch</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">4</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">ivals</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)&</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">max_n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">rooted</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_inits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">max_n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ivals</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">unrooted</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_inits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">max_n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ivals</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_inits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">branch</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">mpz</span> <span style="color: #000000;">tmp</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">tree</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">br</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">mpz</span> <span style="color: #000000;">cnt</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">mpz</span> <span style="color: #000000;">cbr</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">[</span><span style="color: #000000;">br</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">=</span><span style="color: #000000;">br</span> <span style="color: #008080;">to</span> <span style="color: #000000;">branch</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">s</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">n</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">></span><span style="color: #000000;">max_n</span>
<span style="color: #008080;">or</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">l</span><span style="color: #0000FF;">*</span><span style="color: #000000;">2</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">s</span> <span style="color: #008080;">and</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">branch</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">return</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">=</span><span style="color: #000000;">br</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">mpz_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cbr</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">rooted</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">cnt</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">else</span>
<span style="color: #7060A8;">mpz_add_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tmp</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">rooted</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">-</span><span style="color: #000000;">br</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cbr</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">cbr</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">tmp</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_divexact_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cbr</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">cbr</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">-</span><span style="color: #000000;">br</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">*</span><span style="color: #000000;">2</span><span style="color: #0000FF;"><</span><span style="color: #000000;">s</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">mpz</span> <span style="color: #000000;">u</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">unrooted</span><span style="color: #0000FF;">[</span><span style="color: #000000;">s</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #7060A8;">mpz_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">u</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">u</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">cbr</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">b</span><span style="color: #0000FF;"><</span><span style="color: #000000;">branch</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">mpz</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rooted</span><span style="color: #0000FF;">[</span><span style="color: #000000;">s</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #7060A8;">mpz_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">cbr</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">=</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">tree</span><span style="color: #0000FF;">(</span><span style="color: #000000;">b</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">cbr</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">bicenter</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">even</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">mpz</span> <span style="color: #000000;">aux</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">rooted</span><span style="color: #0000FF;">[</span><span style="color: #000000;">s</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span>
<span style="color: #000000;">u</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">unrooted</span><span style="color: #0000FF;">[</span><span style="color: #000000;">s</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #7060A8;">mpz_add_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tmp</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">aux</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tmp</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">aux</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">tmp</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_tdiv_q_2exp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tmp</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">tmp</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">u</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">u</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">tmp</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #004080;">mpz</span> <span style="color: #000000;">cnt</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">max_n</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">tree</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">cnt</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">bicenter</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">25</span> <span style="color: #008080;">or</span> <span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">100</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%d: %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #7060A8;">mpz_get_short_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">unrooted</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span>
<!--</lang>-->
Unusually this is significantly faster (6*) under pwa/p2js than desktop/Phix, the following output/time is from the former.<br>
The limit of 200 in the code above finishes on desktop/Phix in 6s, p2js 1s, 500 takes about 40s in the browser but a whopping three and a half minutes on desktop/Phix, compared to the Go entry above completing that task in 15.6s, all on the same box of course. I have earmarked this task for further investigation into performance improvements, should Phix 2.0 ever actually get started on, that is.
{{out}}
<pre>
1: 1
2: 1
3: 1
4: 2
5: 3
6: 5
7: 9
8: 18
9: 35
10: 75
11: 159
12: 355
13: 802
14: 1858
15: 4347
16: 10359
17: 24894
18: 60523
19: 148284
20: 366319
21: 910726
22: 2278658
23: 5731580
24: 14490245
25: 36797588
100: 5921072038125809849884993369103538010139
200: 94304332879903850516...51576307818857723954 (84 digits)
300: 30845274893235665913...77084032710062170279 (129 digits)
400: 13544322063698139999...74867143490557738328 (174 digits)
500: 69888806977968318652...40565376686372508743 (218 digits)
600: 39937810748209753430...83373172999304809224 (263 digits)
"1 minute and 23s"
</pre>
 
Petelomax
7,820

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/208247"
Cookies help us deliver our services. By using our services, you agree to our use of cookies.
More information