Rosetta Code

Knuth's power tree: Difference between revisions

Page Discussion

Knuth's power tree (view source)

Revision as of 01:54, 15 May 2021

15,461 bytes added ,  3 years ago
m
→‎{{header|Phix}}: added syntax colouring the hard way
m (→‎{{header|REXX}}: added/changed whitespace, split a compound statement, added a template for the output section.)
m (→‎{{header|Phix}}: added syntax colouring the hard way)
Line 1,307:
{{trans|Go}}
{{libheader|Phix/mpfr}}
<!--<lang Phix>constant p = new_dict({{1,0}}notonline)-->
<span style="color: #008080;">constant</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">new_dict</span><span style="color: #0000FF;">({{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">}})</span>
sequence lvl = {1}
<span style="color: #004080;">sequence</span> <span style="color: #000000;">lvl</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}</span>
 
function path(integer n)
<span style="color: #008080;">function</span> <span style="color: #000000;">path</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
if n=0 then return {} end if
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #0000FF;">{}</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
while getd_index(n,p)=NULL do
<span style="color: #008080;">while</span> <span style="color: #7060A8;">getd_index</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)=</span><span style="color: #004600;">NULL</span> <span style="color: #008080;">do</span>
sequence q = {}
<span style="color: #004080;">sequence</span> <span style="color: #000000;">q</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
for i=1 to length(lvl) do
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lvl</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
integer x = lvl[i]
<span style="color: #004080;">integer</span> <span style="color: #000000;">x</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">lvl</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
sequence px = path(x)
<span style="color: #004080;">sequence</span> <span style="color: #000000;">px</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">path</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">)</span>
for j=1 to length(px) do
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">px</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
integer y = x+px[j]
<span style="color: #004080;">integer</span> <span style="color: #000000;">y</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">+</span><span style="color: #000000;">px</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span>
if getd_index(y,p)!=NULL then exit end if
<span style="color: #008080;">if</span> <span style="color: #7060A8;">getd_index</span><span style="color: #0000FF;">(</span><span style="color: #000000;">y</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)!=</span><span style="color: #004600;">NULL</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
setd(y,x,p)
<span style="color: #7060A8;">setd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">y</span><span style="color: #0000FF;">,</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span>
q &= y
<span style="color: #000000;">q</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">y</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
lvl = q
<span style="color: #000000;">lvl</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">q</span>
end while
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
return path(getd(n,p))&n
<span style="color: #008080;">return</span> <span style="color: #000000;">path</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">getd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">))&</span><span style="color: #000000;">n</span>
end function
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
 
include mpfr.e
<span style="color: #008080;">include</span> <span style="color: #7060A8;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
mpfr_set_default_prec(500)
<span style="color: #7060A8;">mpfr_set_default_prec</span><span style="color: #0000FF;">(</span><span style="color: #000000;">500</span><span style="color: #0000FF;">)</span>
function treepow(object x, integer n, sequence pn = {})
<span style="color: #008080;">function</span> <span style="color: #000000;">treepow</span><span style="color: #0000FF;">(</span><span style="color: #004080;">object</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">pn</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{})</span>
-- x can be atom or string (but not mpfr)
<span style="color: #000080;font-style:italic;">-- x can be atom or string (but not mpfr)
-- (asides: sequence r uses out-by-1 indexing, ie r[1] is for 0.
-- (asides: sequence r uses out-by-1 indexing, ie r[1] is for 0.
-- sequence c is used to double-check we are not trying
-- tosequence usec somethingis whichused hasto notdouble-check yetwe beenare not calculated.)trying
-- to use something which has not yet been calculated.)</span>
if pn={} then pn=path(n) end if
<span style="color: #008080;">if</span> <span style="color: #000000;">pn</span><span style="color: #0000FF;">={}</span> <span style="color: #008080;">then</span> <span style="color: #000000;">pn</span><span style="color: #0000FF;">=</span><span style="color: #000000;">path</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
sequence r = {mpfr_init(1),mpfr_init(x)},
<span style="color: #004080;">sequence</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">mpfr_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">mpfr_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">)},</span>
c = {1,1}&repeat(0,max(0,n-1))
<span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</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: #7060A8;">max</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;">1</span><span style="color: #0000FF;">))</span>
for i=1 to max(0,n-1) do r &= mpfr_init() end for
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">max</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;">1</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> <span style="color: #000000;">r</span> <span style="color: #0000FF;">&=</span> <span style="color: #7060A8;">mpfr_init</span><span style="color: #0000FF;">()</span> <span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
integer p = 0
<span style="color: #004080;">integer</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
for i=1 to length(pn) do
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pn</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
integer pi = pn[i]
<span style="color: #004080;">integer</span> <span style="color: #000000;">pi</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">pn</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
if c[pi-p+1]=0 then ?9/0 end if
<span style="color: #008080;">if</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pi</span><span style="color: #0000FF;">-</span><span style="color: #000000;">p</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">?</span><span style="color: #000000;">9</span><span style="color: #0000FF;">/</span><span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
if c[p+1]=0 then ?9/0 end if
<span style="color: #008080;">if</span> <span style="color: #000000;">c</span><span style="color: #0000FF;">[</span><span style="color: #000000;">p</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">?</span><span style="color: #000000;">9</span><span style="color: #0000FF;">/</span><span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
mpfr_mul(r[pi+1],r[pi-p+1],r[p+1])
<span style="color: #000000;">mpfr_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pi</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span><span style="color: #000000;">r</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pi</span><span style="color: #0000FF;">-</span><span style="color: #000000;">p</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">],</span><span style="color: #000000;">r</span><span style="color: #0000FF;">[</span><span style="color: #000000;">p</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span>
c[pi+1] = 1
<span style="color: #000000;">c</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pi</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
p = pi
<span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">pi</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
string res = trim_tail(mpfr_sprintf("%.83Rf",r[n+1]),".0")
<span style="color: #004080;">string</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">trim_tail</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">mpfr_sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"%.83Rf"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</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: #008000;">".0"</span><span style="color: #0000FF;">)</span>
r = mpfr_free(r)
<span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">mpfr_free</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">)</span>
return res
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
end function
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
procedure showpow(object x, integer n)
<span style="color: #008080;">procedure</span> <span style="color: #000000;">showpow</span><span style="color: #0000FF;">(</span><span style="color: #004080;">object</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
sequence pn = path(n)
<span style="color: #004080;">sequence</span> <span style="color: #000000;">pn</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">path</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
string xs = iff(string(x)?x:sprintf("%3g",x))
<span style="color: #004080;">string</span> <span style="color: #000000;">xs</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">)?</span><span style="color: #000000;">x</span><span style="color: #0000FF;">:</span><span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"%3g"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">x</span><span style="color: #0000FF;">))</span>
printf(1,"%48s : %3s ^ %d = %s\n", {sprint(pn),xs,n,treepow(x,n,pn)})
<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;">"%48s : %3s ^ %d = %s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">sprint</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pn</span><span style="color: #0000FF;">),</span><span style="color: #000000;">xs</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">treepow</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pn</span><span style="color: #0000FF;">)})</span>
end procedure
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
for n=0 to 17 do
<span style="color: #008080;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">17</span> <span style="color: #008080;">do</span>
showpow(2,n)
<span style="color: #000000;">showpow</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
end for
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
showpow("1.1",81)
<span style="color: #000000;">showpow</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"1.1"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">81</span><span style="color: #0000FF;">)</span>
showpow(3,191)</lang>
<span style="color: #000000;">showpow</span><span style="color: #0000FF;">(</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">191</span><span style="color: #0000FF;">)</span>
<!--</lang>-->
{{out}}
<pre style="font-size: 12px">
Petelomax
7,820

edits

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