Fibonacci matrix-exponentiation: Difference between revisions
m
→{{header|Wren}}: Minor tidy
(→Ruby) |
m (→{{header|Wren}}: Minor tidy) |
||
| (8 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>
== Ruby's Matlix#exponentiation duck-typeing with Head-tail-BigNumber class ==▼
▲===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,814 ⟶ 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"
{{out}}
<pre>
Fibonacci(2^
Fibonacci(2^
Fibonacci(2^
Fibonacci(2^64) = 11175807536929528424 ... 17529800348089840187 are 3855141514259838964 digits
Took 0.009357194s
</pre>
=={{header|Raku}}==
Line 1,999 ⟶ 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,117 ⟶ 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,199 ⟶ 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
| |||