Rosetta Code

Fibonacci matrix-exponentiation: Difference between revisions

Page Discussion

Fibonacci matrix-exponentiation (view source)

Revision as of 20:03, 19 June 2021

38,069 bytes added ,  2 years ago
m
→‎{{header|Phix}}: added syntax colouring the hard way
m (→‎{{header|Phix}}: mpfr_set_default_precision renamed)
m (→‎{{header|Phix}}: added syntax colouring the hard way)
Line 1,143:
{{libheader|Phix/mpfr}} {{trans|Sidef}} Since I don't have a builtin fibmod, I had to roll my own, and used {n,m} instead of(/to mean) 2^n+m, thus avoiding some 2^53 native atom limits on 32-bit.<br>
(mpz and mpfr variables are effectively pointers, and therefore simply won't work as expected/needed should you try and use them as keys to a cache.)
<!--<lang Phix>(notonline)-->
<lang Phix>requires("1.0.0") -- (mpfr_set_default_prec[ision] has been renamed)
<span style="color: #008080;">without</span> <span style="color: #008080;">javascript_semantics</span> <span style="color: #000080;font-style:italic;">-- (no mpfr_log(), mpfr_exp() under pwa/p2js)</span>
include mpfr.e
<span style="color: #7060A8;">requires</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"1.0.0"</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- (mpfr_set_default_prec[ision] has been renamed)</span>
mpfr_set_default_precision(-40)
<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: #7060A8;">mpfr_set_default_precision</span><span style="color: #0000FF;">(-</span><span style="color: #000000;">40</span><span style="color: #0000FF;">)</span>
constant PHI = mpfr_init(1.25),
IHP = mpfr_init(),
<span style="color: #008080;">constant</span> <span style="color: #000000;">PHI</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpfr_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1.25</span><span style="color: #0000FF;">),</span>
HLF = mpfr_init(0.5),
<span style="color: #000000;">IHP</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpfr_init</span><span style="color: #0000FF;">(),</span>
L10 = mpfr_init(10)
<span style="color: #000000;">HLF</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpfr_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0.5</span><span style="color: #0000FF;">),</span>
mpfr_sqrt(PHI,PHI)
<span style="color: #000000;">L10</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpfr_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)</span>
mpfr_sub(IHP,PHI,HLF)
<span style="color: #7060A8;">mpfr_sqrt</span><span style="color: #0000FF;">(</span><span style="color: #000000;">PHI</span><span style="color: #0000FF;">,</span><span style="color: #000000;">PHI</span><span style="color: #0000FF;">)</span>
mpfr_add(PHI,PHI,HLF)
<span style="color: #7060A8;">mpfr_sub</span><span style="color: #0000FF;">(</span><span style="color: #000000;">IHP</span><span style="color: #0000FF;">,</span><span style="color: #000000;">PHI</span><span style="color: #0000FF;">,</span><span style="color: #000000;">HLF</span><span style="color: #0000FF;">)</span>
mpfr_neg(IHP,IHP)
<span style="color: #7060A8;">mpfr_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">PHI</span><span style="color: #0000FF;">,</span><span style="color: #000000;">PHI</span><span style="color: #0000FF;">,</span><span style="color: #000000;">HLF</span><span style="color: #0000FF;">)</span>
mpfr_log(L10,L10)
<span style="color: #000000;">mpfr_neg</span><span style="color: #0000FF;">(</span><span style="color: #000000;">IHP</span><span style="color: #0000FF;">,</span><span style="color: #000000;">IHP</span><span style="color: #0000FF;">)</span>
 
<span style="color: #000000;">mpfr_log</span><span style="color: #0000FF;">(</span><span style="color: #000000;">L10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">L10</span><span style="color: #0000FF;">)</span>
procedure binet_approx(mpfr r, integer n)
mpfr m = mpfr_init()
<span style="color: #008080;">procedure</span> <span style="color: #000000;">binet_approx</span><span style="color: #0000FF;">(</span><span style="color: #004080;">mpfr</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
mpfr_ui_pow_ui(m,2,n) -- (n as in 2^n here)
<span style="color: #004080;">mpfr</span> <span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpfr_init</span><span style="color: #0000FF;">()</span>
mpfr_log(r,PHI)
<span style="color: #000000;">mpfr_ui_pow_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m</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> <span style="color: #000080;font-style:italic;">-- (n as in 2^n here)</span>
mpfr_mul(r,r,m)
<span style="color: #000000;">mpfr_log</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">,</span><span style="color: #000000;">PHI</span><span style="color: #0000FF;">)</span>
mpfr_sub(m,PHI,IHP)
<span style="color: #7060A8;">mpfr_mul</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;">m</span><span style="color: #0000FF;">)</span>
mpfr_log(m,m)
<span style="color: #7060A8;">mpfr_sub</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m</span><span style="color: #0000FF;">,</span><span style="color: #000000;">PHI</span><span style="color: #0000FF;">,</span><span style="color: #000000;">IHP</span><span style="color: #0000FF;">)</span>
mpfr_sub(r,r,m)
<span style="color: #000000;">mpfr_log</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m</span><span style="color: #0000FF;">)</span>
m = mpfr_free(m)
<span style="color: #7060A8;">mpfr_sub</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;">m</span><span style="color: #0000FF;">)</span>
end procedure
<span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpfr_free</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
function nth_fib_first_k_digits(integer n, k)
mpfr {f,g,h} = mpfr_inits(3)
<span style="color: #008080;">function</span> <span style="color: #000000;">nth_fib_first_k_digits</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: #000000;">k</span><span style="color: #0000FF;">)</span>
binet_approx(f,n)
<span style="color: #004080;">mpfr</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">f</span><span style="color: #0000FF;">,</span><span style="color: #000000;">g</span><span style="color: #0000FF;">,</span><span style="color: #000000;">h</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpfr_inits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">3</span><span style="color: #0000FF;">)</span>
mpfr_div(g,f,L10)
<span style="color: #000000;">binet_approx</span><span style="color: #0000FF;">(</span><span style="color: #000000;">f</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
mpfr_add_si(g,g,1)
<span style="color: #7060A8;">mpfr_div</span><span style="color: #0000FF;">(</span><span style="color: #000000;">g</span><span style="color: #0000FF;">,</span><span style="color: #000000;">f</span><span style="color: #0000FF;">,</span><span style="color: #000000;">L10</span><span style="color: #0000FF;">)</span>
mpfr_floor(g,g)
<span style="color: #000000;">mpfr_add_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">g</span><span style="color: #0000FF;">,</span><span style="color: #000000;">g</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
mpfr_mul(g,L10,g)
<span style="color: #000000;">mpfr_floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">g</span><span style="color: #0000FF;">,</span><span style="color: #000000;">g</span><span style="color: #0000FF;">)</span>
mpfr_sub(f,f,g)
<span style="color: #7060A8;">mpfr_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">g</span><span style="color: #0000FF;">,</span><span style="color: #000000;">L10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">g</span><span style="color: #0000FF;">)</span>
mpfr_exp(f,f)
<span style="color: #7060A8;">mpfr_sub</span><span style="color: #0000FF;">(</span><span style="color: #000000;">f</span><span style="color: #0000FF;">,</span><span style="color: #000000;">f</span><span style="color: #0000FF;">,</span><span style="color: #000000;">g</span><span style="color: #0000FF;">)</span>
mpfr_ui_pow_ui(h,10,k)
<span style="color: #000000;">mpfr_exp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">f</span><span style="color: #0000FF;">,</span><span style="color: #000000;">f</span><span style="color: #0000FF;">)</span>
mpfr_mul(f,f,h)
<span style="color: #000000;">mpfr_ui_pow_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">h</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">k</span><span style="color: #0000FF;">)</span>
mpfr_floor(f,f)
<span style="color: #7060A8;">mpfr_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">f</span><span style="color: #0000FF;">,</span><span style="color: #000000;">f</span><span style="color: #0000FF;">,</span><span style="color: #000000;">h</span><span style="color: #0000FF;">)</span>
string fmt = sprintf("%%%d.0Rf",k)
<span style="color: #000000;">mpfr_floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">f</span><span style="color: #0000FF;">,</span><span style="color: #000000;">f</span><span style="color: #0000FF;">)</span>
return mpfr_sprintf(fmt,f)
<span style="color: #004080;">string</span> <span style="color: #000000;">fmt</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"%%%d.0Rf"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">k</span><span style="color: #0000FF;">)</span>
end function
<span style="color: #008080;">return</span> <span style="color: #7060A8;">mpfr_sprintf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">fmt</span><span style="color: #0000FF;">,</span><span style="color: #000000;">f</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
integer cache = new_dict()
-- key of {n,m} means 2^n+m (where n and m are integers, n>=0, m always 0 or -1)
<span style="color: #004080;">integer</span> <span style="color: #000000;">cache</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">new_dict</span><span style="color: #0000FF;">()</span>
setd({0,0},mpz_init(0),cache) -- aka fib(0):=0
<span style="color: #000080;font-style:italic;">-- key of {n,m} means 2^n+m (where n and m are integers, n&gt;=0, m always 0 or -1)</span>
setd({1,-1},mpz_init(1),cache) -- fib(1):=1
<span style="color: #7060A8;">setd</span><span style="color: #0000FF;">({</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</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><span style="color: #000000;">cache</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- aka fib(0):=0</span>
setd({1,0},mpz_init(1),cache) -- fib(2):=1
<span style="color: #7060A8;">setd</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;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">),</span><span style="color: #000000;">cache</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- fib(1):=1</span>
 
<span style="color: #7060A8;">setd</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><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: #000000;">cache</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- fib(2):=1</span>
procedure mpz_fibmod(mpz f, p, integer n, m=0)
sequence key = {n,m}
<span style="color: #008080;">procedure</span> <span style="color: #000000;">mpz_fibmod</span><span style="color: #0000FF;">(</span><span style="color: #004080;">mpz</span> <span style="color: #000000;">f</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">p</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: #000000;">m</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>
if getd_index(key,cache)!=NULL then
<span style="color: #004080;">sequence</span> <span style="color: #000000;">key</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m</span><span style="color: #0000FF;">}</span>
mpz_set(f,getd(key,cache))
<span style="color: #008080;">if</span> <span style="color: #7060A8;">getd_index</span><span style="color: #0000FF;">(</span><span style="color: #000000;">key</span><span style="color: #0000FF;">,</span><span style="color: #000000;">cache</span><span style="color: #0000FF;">)!=</span><span style="color: #004600;">NULL</span> <span style="color: #008080;">then</span>
else
<span style="color: #7060A8;">mpz_set</span><span style="color: #0000FF;">(</span><span style="color: #000000;">f</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">getd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">key</span><span style="color: #0000FF;">,</span><span style="color: #000000;">cache</span><span style="color: #0000FF;">))</span>
mpz {f1,f2} = mpz_inits(2)
<span style="color: #008080;">else</span>
n -= 1
<span style="color: #004080;">mpz</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">f1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">f2</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_inits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
mpz_fibmod(f1,p,n)
<span style="color: #000000;">n</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span>
mpz_fibmod(f2,p,n,-1)
<span style="color: #000000;">mpz_fibmod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">f1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
if m=-1 then
<span style="color: #000000;">mpz_fibmod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">f2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</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>
-- fib(2n-1) = fib(n)^2 + fib(n-1)^2
<span style="color: #008080;">if</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">=-</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span>
mpz_mul(f1,f1,f1)
<span style="color: #000080;font-style:italic;">-- fib(2n-1) = fib(n)^2 + fib(n-1)^2</span>
mpz_mul(f2,f2,f2)
<span style="color: #7060A8;">mpz_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">f1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">f1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">f1</span><span style="color: #0000FF;">)</span>
mpz_add(f1,f1,f2)
<span style="color: #7060A8;">mpz_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">f2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">f2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">f2</span><span style="color: #0000FF;">)</span>
else
<span style="color: #7060A8;">mpz_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">f1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">f1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">f2</span><span style="color: #0000FF;">)</span>
-- fib(2n) = (2*fib(n-1)+fib(n))*fib(n)
<span style="color: mpz_mul_si(f2,f2,2)#008080;">else</span>
<span style="color: #000080;font-style:italic;">-- fib(2n) = (2*fib(n-1)+fib(n))*fib(n)</span>
mpz_add(f2,f2,f1)
<span style="color: #7060A8;">mpz_mul_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">f2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">f2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
mpz_mul(f1,f2,f1)
<span style="color: #7060A8;">mpz_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">f2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">f2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">f1</span><span style="color: #0000FF;">)</span>
end if
<span style="color: #7060A8;">mpz_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">f1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">f2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">f1</span><span style="color: #0000FF;">)</span>
mpz_mod(f1,f1,p)
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
setd(key,f1,cache)
<span style="color: #7060A8;">mpz_mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">f1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">f1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">)</span>
mpz_set(f,f1)
<span style="color: #7060A8;">setd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">key</span><span style="color: #0000FF;">,</span><span style="color: #000000;">f1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">cache</span><span style="color: #0000FF;">)</span>
end if
<span style="color: #7060A8;">mpz_set</span><span style="color: #0000FF;">(</span><span style="color: #000000;">f</span><span style="color: #0000FF;">,</span><span style="color: #000000;">f1</span><span style="color: #0000FF;">)</span>
end procedure
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
function nth_fib_last_k_digits(integer n, k)
mpz {f,p} = mpz_inits(2)
<span style="color: #008080;">function</span> <span style="color: #000000;">nth_fib_last_k_digits</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: #000000;">k</span><span style="color: #0000FF;">)</span>
mpz_ui_pow_ui(p,10,k)
<span style="color: #004080;">mpz</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">f</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_inits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
mpz_fibmod(f,p,n)
<span style="color: #7060A8;">mpz_ui_pow_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">k</span><span style="color: #0000FF;">)</span>
return mpz_get_str(f)
<span style="color: #000000;">mpz_fibmod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">f</span><span style="color: #0000FF;">,</span><span style="color: #000000;">p</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
end function
<span style="color: #008080;">return</span> <span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">f</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
constant tests = {16,32,64}
for i=1 to length(tests) do
<span style="color: #008080;">constant</span> <span style="color: #000000;">tests</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">16</span><span style="color: #0000FF;">,</span><span style="color: #000000;">32</span><span style="color: #0000FF;">,</span><span style="color: #000000;">64</span><span style="color: #0000FF;">}</span>
integer n = tests[i]
<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;">tests</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
string first20 = nth_fib_first_k_digits(n, 20),
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
last20 = nth_fib_last_k_digits(n, 20)
<span style="color: #004080;">string</span> <span style="color: #000000;">first20</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">nth_fib_first_k_digits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">20</span><span style="color: #0000FF;">),</span>
printf(1,"F(2^%d) = %s ... %s\n",{n,first20,last20})
<span style="color: #000000;">last20</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">nth_fib_last_k_digits</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">20</span><span style="color: #0000FF;">)</span>
end for</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;">"F(2^%d) = %s ... %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">first20</span><span style="color: #0000FF;">,</span><span style="color: #000000;">last20</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</lang>-->
{{out}}
<pre>
Line 1,239 ⟶ 1,242:
Somewhat closer to the original specification, but certainly not recommended for 2^32, let alone 2^64...<br>
Contains copies of routines from [[Matrix-exponentiation_operator#Phix]], but modified to use gmp.
<!--<lang Phix>include mpfr.e(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
 
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
constant ZERO = mpz_init(0),
ONE = mpz_init(1)
<span style="color: #008080;">constant</span> <span style="color: #000000;">ZERO</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>
 
<span style="color: #000000;">ONE</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>
function identity(integer n)
sequence res = repeat(repeat(ZERO,n),n)
<span style="color: #008080;">function</span> <span style="color: #000000;">identity</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
for i=1 to n do
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ZERO</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>
res[i][i] = ONE
<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: #000000;">n</span> <span style="color: #008080;">do</span>
end for
<span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</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;">ONE</span>
return res
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
end function
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
function matrix_mul(sequence a, sequence b)
if length(a[1])!=length(b) then
<span style="color: #008080;">function</span> <span style="color: #000000;">matrix_mul</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">b</span><span style="color: #0000FF;">)</span>
crash("matrices cannot be multiplied")
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])!=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">b</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
end if
<span style="color: #7060A8;">crash</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"matrices cannot be multiplied"</span><span style="color: #0000FF;">)</span>
sequence c = repeat(repeat(ZERO,length(b[1])),length(a))
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
for i=1 to length(a) do
<span style="color: #004080;">sequence</span> <span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ZERO</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</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: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">))</span>
for j=1 to length(b[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;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">a</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
for k=1 to length(a[1]) 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;">b</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">do</span>
mpz cij = mpz_init()
<span style="color: #008080;">for</span> <span style="color: #000000;">k</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;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">do</span>
mpz_mul(cij,a[i][k],b[k][j])
<span style="color: #004080;">mpz</span> <span style="color: #000000;">cij</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">()</span>
mpz_add(cij,cij,c[i][j])
<span style="color: #7060A8;">mpz_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cij</span><span style="color: #0000FF;">,</span><span style="color: #000000;">a</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">k</span><span style="color: #0000FF;">],</span><span style="color: #000000;">b</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">])</span>
c[i][j] = cij
<span style="color: #7060A8;">mpz_add</span><span style="color: #0000FF;">(</span><span style="color: #000000;">cij</span><span style="color: #0000FF;">,</span><span style="color: #000000;">cij</span><span style="color: #0000FF;">,</span><span style="color: #000000;">c</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">])</span>
end for
<span style="color: #000000;">c</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">][</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">cij</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>
return c
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
end function
<span style="color: #008080;">return</span> <span style="color: #000000;">c</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
function matrix_exponent(sequence m, integer n)
integer l = length(m)
<span style="color: #008080;">function</span> <span style="color: #000000;">matrix_exponent</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">m</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
if l!=length(m[1]) then crash("not a square matrix") end if
<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;">m</span><span style="color: #0000FF;">)</span>
if n<0 then crash("negative exponents not supported") end if
<span style="color: #008080;">if</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;">m</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span> <span style="color: #008080;">then</span> <span style="color: #7060A8;">crash</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"not a square matrix"</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
sequence res = identity(l)
<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: #7060A8;">crash</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"negative exponents not supported"</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
while n do
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">identity</span><span style="color: #0000FF;">(</span><span style="color: #000000;">l</span><span style="color: #0000FF;">)</span>
if and_bits(n,1) then
<span style="color: #008080;">while</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span>
res = matrix_mul(res,m)
<span style="color: #008080;">if</span> <span style="color: #7060A8;">and_bits</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;">then</span>
end if
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">matrix_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m</span><span style="color: #0000FF;">)</span>
n = floor(n/2)
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
if n=0 then exit end if -- (avoid unnecessary matrix_mul)
<span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</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>
m = matrix_mul(m,m)
<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> <span style="color: #000080;font-style:italic;">-- (avoid unnecessary matrix_mul)</span>
end while
<span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">matrix_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">m</span><span style="color: #0000FF;">,</span><span style="color: #000000;">m</span><span style="color: #0000FF;">)</span>
return res
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
end function
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
function fibonacci(integer n)
sequence m = {{ONE, ONE},
<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>
{ONE, ZERO}}
<span style="color: #004080;">sequence</span> <span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">ONE</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ONE</span><span style="color: #0000FF;">},</span>
m = matrix_exponent(m,n-1)
<span style="color: #0000FF;">{</span><span style="color: #000000;">ONE</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ZERO</span><span style="color: #0000FF;">}}</span>
mpz res = m[1][1]
<span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">matrix_exponent</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;">1</span><span style="color: #0000FF;">)</span>
return res
<span style="color: #004080;">mpz</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">m</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>
end function
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
 
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
atom t0 = time()
mpz fn = fibonacci(power(2,16))
<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>
string s = mpz_get_str(fn)
<span style="color: #004080;">mpz</span> <span style="color: #000000;">fn</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">fibonacci</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">16</span><span style="color: #0000FF;">))</span>
string e = elapsed(time()-t0)
<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;">fn</span><span style="color: #0000FF;">)</span>
printf(1,"fibonnaci(2^16) = %s [%s]\n",{shorten(s),e})
<span style="color: #004080;">string</span> <span style="color: #000000;">e</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>
 
<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;">"fibonnaci(2^16) = %s [%s]\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">shorten</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">),</span><span style="color: #000000;">e</span><span style="color: #0000FF;">})</span>
for i=1 to 7 do
t0 = time()
<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: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()=</span><span style="color: #004600;">JS</span><span style="color: #0000FF;">?</span><span style="color: #000000;">6</span><span style="color: #0000FF;">:</span><span style="color: #000000;">7</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
integer n = power(10,i)
<span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
fn = fibonacci(n)
<span style="color: #004080;">integer</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)</span>
s = mpz_get_str(fn)
<span style="color: #000000;">fn</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">fibonacci</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
t0 = time()-t0
<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;">fn</span><span style="color: #0000FF;">)</span>
e = iff(t0>0.1?" ["&elapsed(t0)&"]":"")
<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: #000000;">t0</span>
printf(1,"fibonnaci(%,d) = %s%s\n",{n,shorten(s),e})
<span style="color: #000000;">e</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">></span><span style="color: #000000;">0.1</span><span style="color: #0000FF;">?</span><span style="color: #008000;">" ["</span><span style="color: #0000FF;">&</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)&</span><span style="color: #008000;">"]"</span><span style="color: #0000FF;">:</span><span style="color: #008000;">""</span><span style="color: #0000FF;">)</span>
end for</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;">"fibonnaci(%,d) = %s%s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">shorten</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">),</span><span style="color: #000000;">e</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</lang>-->
{{out}}
<pre>
Line 1,320 ⟶ 1,326:
fibonnaci(10,000,000) = 11298343782253997603...86998673686380546875 (2,089,877 digits) [9.0s]
</pre>
Note that under pwa/p2js 10^6 takes 11.4s so we'll stop there...<br>
Change that loop to 8 and a 9 year old 3.3GHz i3 also eventually gets:
<pre>
Petelomax
7,795

edits

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