Fibonacci sequence: Difference between revisions
Content added Content deleted
(→{Excel LAMBDA}: Added a Excel LAMBDA draft.) |
m (→{{header|Phix}}: added syntax colouring the hard way) |
||
| Line 8,396: | Line 8,396: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
<!--<lang Phix>(phixonline)--> |
|||
<lang Phix>function fibonacci(integer n) -- iterative, works for -ve numbers |
|||
<span style="color: #008080;">function</span> <span style="color: #000000;">fibonacci</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: #000080;font-style:italic;">-- iterative, works for -ve numbers</span> |
|||
atom a=0, b=1 |
|||
<span style="color: #004080;">atom</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> |
|||
if n=0 then return 0 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: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
if abs(n)>=79 then ?9/0 end if -- inaccuracies creep in above 78 |
|||
<span style="color: #008080;">if</span> <span style="color: #7060A8;">abs</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)>=</span><span style="color: #000000;">79</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> <span style="color: #000080;font-style:italic;">-- inaccuracies creep in above 78</span> |
|||
for i=1 to abs(n)-1 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;">abs</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;">do</span> |
|||
{a,b} = {b,a+b} |
|||
<span style="color: #0000FF;">{</span><span style="color: #000000;">a</span><span style="color: #0000FF;">,</span><span style="color: #000000;">b</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">b</span><span style="color: #0000FF;">,</span><span style="color: #000000;">a</span><span style="color: #0000FF;">+</span><span style="color: #000000;">b</span><span style="color: #0000FF;">}</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
if n<0 and remainder(n,2)=0 then return -b 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;">and</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;">2</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: #000000;">b</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
return b |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">b</span> |
|||
end function |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
for i=0 to 28 do |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">28</span> <span style="color: #008080;">do</span> |
|||
if i then puts(1,", ") end if |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">i</span> <span style="color: #008080;">then</span> <span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">", "</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
printf(1,"%d", fibonacci(i)) |
|||
<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"</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">fibonacci</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">))</span> |
|||
end for |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
puts(1,"\n")</lang> |
|||
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">)</span> |
|||
<!--</lang>--> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
| Line 8,418: | Line 8,420: | ||
Using native integers/atoms, errors creep in above 78, so the same program converted to use mpfr: |
Using native integers/atoms, errors creep in above 78, so the same program converted to use mpfr: |
||
{{libheader|Phix/mpfr}} |
{{libheader|Phix/mpfr}} |
||
<lang Phix>-- |
<!--<lang Phix>(notonline)--> |
||
<span style="color: #000080;font-style:italic;">-- demo\rosetta\fibonacci.exw</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> |
|||
<span style="color: #7060A8;">mpz</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">NULL</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">prev</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">next</span> |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">lastn</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;">function</span> <span style="color: #000000;">fibonampz</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: #000080;font-style:italic;">-- resumable, works for -ve numbers, yields mpz</span> |
|||
mpz res = NULL, prev, next |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">absn</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">abs</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> |
|||
integer lastn |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">=</span><span style="color: #004600;">NULL</span> <span style="color: #008080;">or</span> <span style="color: #000000;">absn</span><span style="color: #0000FF;">!=</span><span style="color: #7060A8;">abs</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lastn</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> |
|||
atom t0 = time() |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">=</span><span style="color: #004600;">NULL</span> <span style="color: #008080;">then</span> |
|||
<span style="color: #000000;">prev</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span> |
|||
function fibonampz(integer n) -- resumable, works for -ve numbers, yields mpz |
|||
<span style="color: #000000;">res</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> |
|||
integer absn = abs(n) |
|||
<span style="color: #000000;">next</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">()</span> |
|||
if res=NULL or absn!=abs(lastn)+1 then |
|||
<span style="color: #008080;">else</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">==</span><span style="color: #000000;">lastn</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #000000;">res</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
prev = mpz_init(0) |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
res = mpz_init(1) |
|||
<span style="color: #000000;">mpz_fib2_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">prev</span><span style="color: #0000FF;">,</span><span style="color: #000000;">absn</span><span style="color: #0000FF;">)</span> |
|||
next = mpz_init() |
|||
<span style="color: #008080;">else</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">lastn</span><span style="color: #0000FF;"><</span><span style="color: #000000;">0</span> <span style="color: #008080;">and</span> <span style="color: #7060A8;">remainder</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lastn</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> |
|||
if n==lastn then return res end if |
|||
<span style="color: #7060A8;">mpz_mul_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> |
|||
end if |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
mpz_fib2_ui(res,prev,absn) |
|||
<span style="color: #7060A8;">mpz_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">next</span><span style="color: #0000FF;">,</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">prev</span><span style="color: #0000FF;">)</span> |
|||
else |
|||
<span style="color: #0000FF;">{</span><span style="color: #000000;">prev</span><span style="color: #0000FF;">,</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">next</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">next</span><span style="color: #0000FF;">,</span><span style="color: #000000;">prev</span><span style="color: #0000FF;">}</span> |
|||
if lastn<0 and remainder(lastn,2)=0 then |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
mpz_mul_si(res,res,-1) |
|||
<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;">and</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;">2</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> |
|||
end if |
|||
<span style="color: #7060A8;">mpz_mul_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> |
|||
mpz_add(next,res,prev) |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
{prev,res,next} = {res,next,prev} |
|||
<span style="color: #000000;">lastn</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span> |
|||
end if |
|||
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span> |
|||
if n<0 and remainder(n,2)=0 then |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
|||
mpz_mul_si(res,res,-1) |
|||
end if |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">28</span> <span style="color: #008080;">do</span> |
|||
lastn = n |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">i</span> <span style="color: #008080;">then</span> <span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">", "</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
return res |
|||
<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;">"%s"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">fibonampz</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">))})</span> |
|||
end function |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">)</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;">"%s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">fibonampz</span><span style="color: #0000FF;">(</span><span style="color: #000000;">705</span><span style="color: #0000FF;">))})</span> |
|||
<span style="color: #004080;">string</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">fibonampz</span><span style="color: #0000FF;">(</span><span style="color: #000000;">4784969</span><span style="color: #0000FF;">))</span> |
|||
for i=0 to 28 do |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> |
|||
if i then puts(1,", ") end if |
|||
<span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">40</span><span style="color: #0000FF;">..-</span><span style="color: #000000;">40</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"..."</span> |
|||
printf(1,"%s", {mpz_get_str(fibonampz(i))}) |
|||
<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> |
|||
end for |
|||
<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> |
|||
puts(1,"\n") |
|||
<!--</lang>--> |
|||
printf(1,"%s\n", {mpz_get_str(fibonampz(705))}) |
|||
string s = mpz_get_str(fibonampz(4784969)) |
|||
integer l = length(s) |
|||
s[40..-40] = "..." |
|||
?{l,s} |
|||
?elapsed(time()-t0) |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||