Fibonacci matrix-exponentiation: Difference between revisions

Content added Content deleted
Line 1,707: Line 1,707:
===Matrix exponentiation by Ruby's fast exponentiation operator duck-typing applied to Ruby's built-in Integer Class===
===Matrix exponentiation by Ruby's fast exponentiation operator duck-typing applied to Ruby's built-in Integer Class===


require 'matrix'
require 'matrix'
start_time = Time.now
start_time = Time.now
[10,100,256, 1_000, 1024, 10_000, 2 ** 16, 100_000, 1_000_000,10_000_000 ].each {|n|
[0,1,2,3,4,10,100,256, 1_000, 1024, 10_000, 2 ** 16, 100_000, 1_000_000,10_000_000 ].each {|n|
fib_Num=(Matrix[[0,1],[1,1]] ** (n))[0,1]
fib_Num=(Matrix[[0,1],[1,1]] ** (n))[0,1]
fib_Str= fib_Num.to_s()
fib_Str= fib_Num.to_s()
if fib_Str.length <= 21
if fib_Str.length <= 21
p [n,fib_Str.length.to_s + ' digits' , fib_Str, "Took #{Time.now - start_time}s"]
p ["Fibonattch(#{n})",fib_Str.length.to_s + ' digits' , fib_Str]
else
else
p [n,fib_Str.length.to_s + ' digits' , fib_Str.slice(0,20) + " ... " + fib_Str[-20 ... -1] , "Took #{Time.now - start_time}s"]
p ["Fibonattch(#{n})",fib_Str.length.to_s + ' digits' , fib_Str.slice(0,20) + " ... " + fib_Str.slice(-20,20)]
end
end
}
}
puts "Took #{Time.now - start_time}s"
puts "Took #{Time.now - start_time}s"

{{out}}
{{out}}
<pre>
<pre>
[10, "2 digits", "55", "Took 6.836e-05s"]
["Fibonattch(0)", "1 digits", "0"]
[100, "21 digits", "354224848179261915075", "Took 0.000259665s"]
["Fibonattch(1)", "1 digits", "1"]
["Fibonattch(2)", "1 digits", "1"]
[256, "54 digits", "14169381771405651323 ... 1965770779495819986", "Took 0.000390585s"]
["Fibonattch(3)", "1 digits", "2"]
[1000, "209 digits", "43466557686937456435 ... 7613779516684922887", "Took 0.000576685s"]
["Fibonattch(4)", "1 digits", "3"]
[1024, "214 digits", "45066996336778198131 ... 0410363155392540524", "Took 0.001018916s"]
["Fibonattch(10)", "2 digits", "55"]
⚫
[10000, "2090 digits", "33644764876431783266 ... 6607331005994736687", "Took 0.001502226s"]
["Fibonattch(100)", "21 digits", "354224848179261915075"]
⚫
[65536, "13696 digits", "73199214460290552832 ... 9727019095530746322", "Took 0.003220941s"]
[100000, "20899 digits", "25974069347221724166 ... 4989537465342874687", "Took 0.006312s"]
["Fibonattch(256)", "54 digits", "14169381771405651323 ... 19657707794958199867"]
[1000000, "208988 digits", "19532821287077577316 ... 6899652683824254687", "Took 0.076104599s"]
["Fibonattch(1000)", "209 digits", "43466557686937456435 ... 76137795166849228875"]
[10000000, "2089877 digits", "11298343782253997603 ... 8699867368638054687", "Took 1.112832817s"]
["Fibonattch(1024)", "214 digits", "45066996336778198131 ... 04103631553925405243"]
⚫
["Fibonattch(10000)", "2090 digits", "33644764876431783266 ... 66073310059947366875"]
Took 1.112902545s
⚫
["Fibonattch(65536)", "13696 digits", "73199214460290552832 ... 97270190955307463227"]
["Fibonattch(100000)", "20899 digits", "25974069347221724166 ... 49895374653428746875"]
["Fibonattch(1000000)", "208988 digits", "19532821287077577316 ... 68996526838242546875"]
["Fibonattch(10000000)", "2089877 digits", "11298343782253997603 ... 86998673686380546875"]
Took 1.115647303s
</pre>
</pre>


Retrieved from "https://rosettacode.org/wiki/Fibonacci_matrix-exponentiation"