Talk:Fibonacci matrix-exponentiation: Difference between revisions
(→Ruby) |
|||
Line 18: | Line 18: | ||
require 'matrix' |
require 'matrix' |
||
start_time = Time.now |
start_time = Time.now |
||
[10,100,1_000,10_000, 2 ** 16, 100_000, 1_000_000, 2 ** 32 ].each {|n| |
[10,100,1_000,10_000, 2 ** 16, 100_000, 1_000_000,10_000_000, 2 ** 32 ].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() |
Revision as of 11:40, 8 June 2023
Clarify Task
The task to implement fib(n) using matrix multiplication is a great task. However, given that fib(2^32) has hundreds of million of digits, the task is unachievable. Many implementations use fibMod for the last digits, and another methodology for the first digits. Recommend a selecting smaller values of n, and sticking to the task of fib(n) using matrix multiplication, not fibMod or other implementations.
--DavidFashion (talk) 00:04, 13 February 2020 (UTC)
I will add fib(2^16) in the main task. If only fib(2^64) is not calculated, the task is considered accomplished.
The goal of the task is to show that the iterative method is slow to calculate large fibonacci numbers. Smaller values like fib(2^16) is easily found using the iterative method.
I think fib(2^32) is reachable using matrix exponentiation and even if it remains slow, Julia solution shows a faster method using Lucas sequence.
I confess fib(2^64) seems unreachable using matrix exponentiation. Nevertheless it allowed to see some creative solution like the Sidef solution using fibmod.
Ruby
require 'matrix' start_time = Time.now [10,100,1_000,10_000, 2 ** 16, 100_000, 1_000_000,10_000_000, 2 ** 32 ].each {|n| fib_Num=(Matrix[[0,1],[1,1]] ** (n))[0,1] fib_Str= fib_Num.to_s() if fib_Str.length <= 21 p [n,fib_Str.length.to_s + ' digits' , fib_Str, "Took #{Time.now - start_time}s"] else p [n,fib_Str.length.to_s + ' digits' , fib_Str.slice(0,20) + " ... " + fib_Str[-20 ... -1] , "Took #{Time.now - start_time}s"] end } puts "Took #{Time.now - start_time}s"
outputs
[10, "2 digits", "55", "Took 9.0311e-05s"] [100, "21 digits", "354224848179261915075", "Took 0.000259388s"] [1000, "209 digits", "43466557686937456435 ... 7613779516684922887", "Took 0.000512211s"] [10000, "2090 digits", "33644764876431783266 ... 6607331005994736687", "Took 0.001087754s"] [65536, "13696 digits", "73199214460290552832 ... 9727019095530746322", "Took 0.003636489s"] [100000, "20899 digits", "25974069347221724166 ... 4989537465342874687", "Took 0.008467388s"] [1000000, "208988 digits", "19532821287077577316 ... 6899652683824254687", "Took 0.104574053s"] [10000000, "2089877 digits", "11298343782253997603 ... 8699867368638054687", "Took 0.996411418s"]