Fibonacci matrix-exponentiation: Difference between revisions
m
→{{header|Wren}}: Minor tidy
No edit summary |
m (→{{header|Wren}}: Minor tidy) |
||
| (6 intermediate revisions by one other user not shown) | |||
Line 1,705:
2^128: 15262728879740471565 ... 17229324095882654267</pre>
=={{header|Ruby}}==
===Matrix exponentiation by Ruby's fast exponentiation operator duck-typing applied to Ruby's built-in Integer Class
<pre>
##
fib_Num=(Matrix[[0,1],[1,1]] ** (n))[0,1] ## Matrix exponentiation
##
fib_Str= fib_Num.to_s()
if fib_Str.length <= 21
p ["Fibonacci(#{n})",fib_Str.length.to_s + ' digits' , fib_Str
else
end
</pre>
{{out}}
<pre>
["Fibonacci(2)", "1 digits", "1"]
["Fibonacci(3)", "1 digits", "2"]
["Fibonacci(4)", "1 digits", "3"]
["Fibonacci(10)", "2 digits", "55"]
[10000, "2090 digits", "33644764876431783266 ... 6607331005994736687", "Took 0.001502226s"]▼
["Fibonacci(100)", "21 digits", "354224848179261915075"]
[65536, "13696 digits", "73199214460290552832 ... 9727019095530746322", "Took 0.003220941s"]▼
▲
▲
["Fibonacci(100000)", "20899 digits", "25974069347221724166 ... 49895374653428746875"]
["Fibonacci(1000000)", "208988 digits", "19532821287077577316 ... 68996526838242546875"]
["Fibonacci(10000000)", "2089877 digits", "11298343782253997603 ... 86998673686380546875"]
Took 1.027948065s
</pre>
===Matrix exponentiation by Ruby's Matlix#exponentiation duck-typeing with Head-tail-BigNumber class
Here, the HeadTailBignum class holds the digits of the head part in Ruby's bigDecimal class and tail part in the BigInteger class.
and HeadTailBignum defines only the add and multply operators and the coerce method.
Line 1,815 ⟶ 1,824:
n = (2**h)
fib_Num=(Matrix[[ HeadTailBignum.new(0),1],[1,1]] ** (n))[0,1]
puts "Fibonacci(2^#{h.to_s}) = #{fib_Num.to_s} are #{fib_Num.exponent}
}
puts "Took #{Time.now - start_time}s"
Line 1,821 ⟶ 1,830:
{{out}}
<pre>
Fibonacci(2^8) = 14169381771405651323 ... 19657707794958199867 are 54
Fibonacci(2^16) = 73199214460290552832 ... 97270190955307463227 are 13696
Fibonacci(2^32) = 61999319689381859818 ... 39623735538208076347 are 897595080
Fibonacci(2^64) = 11175807536929528424 ... 17529800348089840187 are
Took 0.009357194s
</pre>
Line 2,002 ⟶ 2,011:
{{libheader|Wren-fmt}}
A tough task for Wren which takes just under 3 minutes to process even the 1 millionth Fibonacci number. Judging by the times for the compiled, statically typed languages using GMP, the 10 millionth would likely take north of 4 hours so I haven't attempted it.
<syntaxhighlight lang="
import "./fmt" for Fmt
var mul = Fn.new { |m1, m2|
Line 2,120 ⟶ 2,129:
Apart from the 2^16th number, the extra credit is still out of reach using this approach.
<syntaxhighlight lang="
import "./fmt" for Fmt
var lucas = Fn.new { |n|
Line 2,202 ⟶ 2,211:
{{libheader|Wren-gmp}}
Ridiculously fast (under 5ms) thanks to the stuff borrowed from Sidef and Julia combined with the speed of GMP.
<syntaxhighlight lang="
import "./fmt" for Fmt
| |||