Anonymous user
Fibonacci matrix-exponentiation: Difference between revisions
→{{header|Nim}}
m (added highlighting.) |
|||
Line 1,101:
2^64 11175807536929528424...17529800348089840187
</pre>
=={{header|Nim}}==
{{trans|Wren}}
{{trans|Go}}
Using the Lucas method.
<lang Nim>import strformat, strutils, times
import bignum
let
One = newInt(1)
Two = newInt(2)
Three = newInt(3)
proc lucas(n: Int): Int =
proc inner(n: Int): (Int, Int) =
if n.isZero: return (newInt(0), newInt(1))
var t = n shr 1
var (u, v) = inner(t)
t = n and Two
let q = t - One
var r = newInt(0)
u *= u
v *= v
t = n and One
if t == One:
t = (u - q) * Two
r = v * Three
result = (u + v, r - t)
else:
t = u * Three
r = v + q
r *= Two
result = (r - t, u + v)
var t = n shr 1
let (u, v) = inner(t)
let l = v * Two - u
t = n and One
if t == One:
let q = n and Two - One
return v * l + q
return u * l
let start = now()
var n: Int
var i = 10
while i <= 10_000_000:
n = newInt(i)
let s = $lucas(n)
echo &"The digits of the {($i).insertSep}th Fibonacci number ({($s.len).insertSep}) are:"
if s.len > 20:
echo &" First 20 : {s[0..19]}"
if s.len < 40:
echo &" Final {s.len-20:<2} : {s[20..^1]}"
else:
echo &" Final 20 : {s[^20..^1]}"
else:
echo &" All {s.len:<2} : {s}"
echo()
i *= 10
for e in [culong 16, 32]:
n = One shl e
let s = $lucas(n)
echo &"The digits of the 2^{e}th Fibonacci number ({($s.len).insertSep}) are:"
echo &" First 20 : {s[0..19]}"
echo &" Final 20 : {s[^20..^1]}"
echo()
echo &"Took {now() - start}"</lang>
{{out}}
<pre>The digits of the 10th Fibonacci number (2) are:
All 2 : 55
The digits of the 100th Fibonacci number (21) are:
First 20 : 35422484817926191507
Final 1 : 5
The digits of the 1_000th Fibonacci number (209) are:
First 20 : 43466557686937456435
Final 20 : 76137795166849228875
The digits of the 10_000th Fibonacci number (2_090) are:
First 20 : 33644764876431783266
Final 20 : 66073310059947366875
The digits of the 100_000th Fibonacci number (20_899) are:
First 20 : 25974069347221724166
Final 20 : 49895374653428746875
The digits of the 1_000_000th Fibonacci number (208_988) are:
First 20 : 19532821287077577316
Final 20 : 68996526838242546875
The digits of the 10_000_000th Fibonacci number (2_089_877) are:
First 20 : 11298343782253997603
Final 20 : 86998673686380546875
The digits of the 2^16th Fibonacci number (13_696) are:
First 20 : 73199214460290552832
Final 20 : 97270190955307463227
The digits of the 2^32th Fibonacci number (897_595_080) are:
First 20 : 61999319689381859818
Final 20 : 39623735538208076347
Took 6 minutes, 18 seconds, 643 milliseconds, 622 microseconds, and 965 nanoseconds</pre>
=={{header|Perl}}==
| |||