Talk:Fibonacci matrix-exponentiation

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"]