Minkowski question-mark function: Difference between revisions
Content added Content deleted
(→{{header|Haskell}}: simplifed and rewrote the solution.) |
m (→{{header|Phix}}: added (proper) syntax colouring, marked p2js compatible) |
||
Line 727: | Line 727: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
{{trans|FreeBASIC}} |
{{trans|FreeBASIC}} |
||
<!--<lang Phix>(phixonline)--> |
|||
<lang Euphoria>constant MAXITER = 151 |
|||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
<span style="color: #008080;">constant</span> <span style="color: #000000;">MAXITER</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">151</span> |
|||
function minkowski(atom x) |
|||
atom p = floor(x) |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">minkowski</span><span style="color: #0000FF;">(</span><span style="color: #004080;">atom</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">)</span> |
|||
if x>1 or x<0 then return p+minkowski(x-p) end if |
|||
<span style="color: #004080;">atom</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">)</span> |
|||
atom q = 1, r = p + 1, s = 1, m, n, d = 1, y = p |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">></span><span style="color: #000000;">1</span> <span style="color: #008080;">or</span> <span style="color: #000000;">x</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: #000000;">p</span><span style="color: #0000FF;">+</span><span style="color: #000000;">minkowski</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> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
while true do |
|||
<span style="color: #004080;">atom</span> <span style="color: #000000;">q</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> <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: #000000;">m</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">y</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">p</span> |
|||
d = d/2 |
|||
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span> |
|||
if y + d = y then exit end if |
|||
<span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span> |
|||
m = p + r |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">y</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">y</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> |
|||
if m < 0 or p < 0 then exit end if |
|||
<span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">r</span> |
|||
n = q + s |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">m</span> <span style="color: #0000FF;"><</span> <span style="color: #000000;">0</span> <span style="color: #008080;">or</span> <span style="color: #000000;">p</span> <span style="color: #0000FF;"><</span> <span style="color: #000000;">0</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> |
|||
if n < 0 then exit end if |
|||
<span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">q</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">s</span> |
|||
if x < m/n then |
|||
<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;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
r = m |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">x</span> <span style="color: #0000FF;"><</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">/</span><span style="color: #000000;">n</span> <span style="color: #008080;">then</span> |
|||
s = n |
|||
<span style="color: #000000;">r</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">m</span> |
|||
else |
|||
<span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span> |
|||
y = y + d |
|||
<span style="color: #008080;">else</span> |
|||
<span style="color: #000000;">y</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">y</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">d</span> |
|||
q = n |
|||
<span style="color: #000000;">p</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">m</span> |
|||
end if |
|||
<span style="color: #000000;">q</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span> |
|||
end while |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
return y + d |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
end function |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">y</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">d</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
function minkowski_inv(atom x) |
|||
if x>1 or x<0 then return floor(x)+minkowski_inv(x-floor(x)) end if |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">minkowski_inv</span><span style="color: #0000FF;">(</span><span style="color: #004080;">atom</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">)</span> |
|||
if x=1 or x=0 then return x end if |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">></span><span style="color: #000000;">1</span> <span style="color: #008080;">or</span> <span style="color: #000000;">x</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: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">minkowski_inv</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">-</span><span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">))</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
sequence contfrac = {} |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">or</span> <span style="color: #000000;">x</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: #000000;">x</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
integer curr = 0, count = 1 |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">contfrac</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span> |
|||
while true do |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">curr</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span> |
|||
x *= 2 |
|||
<span style="color: #008080;">while</span> <span style="color: #004600;">true</span> <span style="color: #008080;">do</span> |
|||
if curr = 0 then |
|||
<span style="color: #000000;">x</span> <span style="color: #0000FF;">*=</span> <span style="color: #000000;">2</span> |
|||
if x<1 then |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">curr</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> <span style="color: #008080;">then</span> |
|||
count += 1 |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">x</span><span style="color: #0000FF;"><</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> |
|||
else |
|||
<span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
contfrac &= count |
|||
<span style="color: #008080;">else</span> |
|||
<span style="color: #000000;">contfrac</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">count</span> |
|||
curr = 1 |
|||
<span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span> |
|||
x -= 1 |
|||
<span style="color: #000000;">curr</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span> |
|||
end if |
|||
<span style="color: #000000;">x</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span> |
|||
else |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
if x>1 then |
|||
<span style="color: #008080;">else</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">x</span><span style="color: #0000FF;">></span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> |
|||
x -= 1 |
|||
<span style="color: #000000;">count</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span> |
|||
else |
|||
<span style="color: #000000;">x</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span> |
|||
contfrac &= count |
|||
<span style="color: #008080;">else</span> |
|||
<span style="color: #000000;">contfrac</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">count</span> |
|||
curr = 0 |
|||
<span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span> |
|||
end if |
|||
<span style="color: #000000;">curr</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span> |
|||
end if |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
if x = floor(x) then |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
contfrac &= count |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">x</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">x</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> |
|||
exit |
|||
<span style="color: #000000;">contfrac</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">count</span> |
|||
end if |
|||
<span style="color: #008080;">exit</span> |
|||
if length(contfrac)=MAXITER then exit end if |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
end while |
|||
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">contfrac</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">MAXITER</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> |
|||
atom ret = 1/contfrac[$] |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span> |
|||
for i = length(contfrac)-1 to 1 by -1 do |
|||
<span style="color: #004080;">atom</span> <span style="color: #000000;">ret</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">/</span><span style="color: #000000;">contfrac</span><span style="color: #0000FF;">[$]</span> |
|||
ret = contfrac[i] + 1.0/ret |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">contfrac</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> |
|||
end for |
|||
<span style="color: #000000;">ret</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">contfrac</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+</span> <span style="color: #000000;">1.0</span><span style="color: #0000FF;">/</span><span style="color: #000000;">ret</span> |
|||
return 1/ret |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
end function |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">/</span><span style="color: #000000;">ret</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
printf(1,"%20.16f %20.16f\n",{minkowski(0.5*(1+sqrt(5))), 5/3}) |
|||
printf(1,"%20.16f %20.16f\n",{minkowski_inv(-5/9), (sqrt(13)-7)/6}) |
|||
<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;">"%20.16f %20.16f\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">minkowski</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0.5</span><span style="color: #0000FF;">*(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">+</span><span style="color: #7060A8;">sqrt</span><span style="color: #0000FF;">(</span><span style="color: #000000;">5</span><span style="color: #0000FF;">))),</span> <span style="color: #000000;">5</span><span style="color: #0000FF;">/</span><span style="color: #000000;">3</span><span style="color: #0000FF;">})</span> |
|||
printf(1,"%20.16f %20.16f\n",{minkowski(minkowski_inv(0.718281828)), |
|||
<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;">"%20.16f %20.16f\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">minkowski_inv</span><span style="color: #0000FF;">(-</span><span style="color: #000000;">5</span><span style="color: #0000FF;">/</span><span style="color: #000000;">9</span><span style="color: #0000FF;">),</span> <span style="color: #0000FF;">(</span><span style="color: #7060A8;">sqrt</span><span style="color: #0000FF;">(</span><span style="color: #000000;">13</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">7</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">6</span><span style="color: #0000FF;">})</span> |
|||
minkowski_inv(minkowski(0.1213141516171819))})</lang> |
|||
<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;">"%20.16f %20.16f\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">minkowski</span><span style="color: #0000FF;">(</span><span style="color: #000000;">minkowski_inv</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0.718281828</span><span style="color: #0000FF;">)),</span> |
|||
<span style="color: #000000;">minkowski_inv</span><span style="color: #0000FF;">(</span><span style="color: #000000;">minkowski</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0.1213141516171819</span><span style="color: #0000FF;">))})</span> |
|||
<!--</lang>--> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |