# Talk:Fibonacci matrix-exponentiation

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

Ruby's fast exponentiation operator duck-typing applied to Ruby's built-in Integer Class.

```require 'matrix'
start_time = Time.now
[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_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"
```

Ruby's built-in Integer Class outputs:

```[10, "2 digits", "55", "Took 6.836e-05s"]
[100, "21 digits", "354224848179261915075", "Took 0.000259665s"]
[256, "54 digits", "14169381771405651323 ... 1965770779495819986", "Took 0.000390585s"]
[1000, "209 digits", "43466557686937456435 ... 7613779516684922887", "Took 0.000576685s"]
[1024, "214 digits", "45066996336778198131 ... 0410363155392540524", "Took 0.001018916s"]
[10000, "2090 digits", "33644764876431783266 ... 6607331005994736687", "Took 0.001502226s"]
[65536, "13696 digits", "73199214460290552832 ... 9727019095530746322", "Took 0.003220941s"]
[100000, "20899 digits", "25974069347221724166 ... 4989537465342874687", "Took 0.006312s"]
[1000000, "208988 digits", "19532821287077577316 ... 6899652683824254687", "Took 0.076104599s"]
[10000000, "2089877 digits", "11298343782253997603 ... 8699867368638054687", "Took 1.112832817s"]
Took 1.112902545s
```

## Ruby's Matlix 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.

Matlix exponentiation operator is fast and can apply duck-typing to HeadTailBignum.

```require 'matrix'
require 'bigdecimal'

attr_accessor :hi, :lo
@@degitsLimit = 20
@@hiDegitsLimit = (@@degitsLimit + 1) * 2
@@loDegitsBase = 10 ** @@degitsLimit
BigDecimal::limit(@@hiDegitsLimit)
def initialize(other, loValue = nil)
if other.kind_of?(BigDecimal) && loValue.kind_of?(Integer)
@hi = other
@lo = loValue % @@loDegitsBase
@hi = other.hi
@lo = other.lo
elsif other.kind_of?(Integer)
@hi = BigDecimal(other)
@lo = other % @@loDegitsBase
else
raise StandardError.new("HeadTailBignum initialize Type Error (" + other.class.to_s + "," + loValue.class.to_s + ")")
end
end
def clone
end

def integer?()
true
end
def coerce(other)
if other.kind_of?(Integer)
else
super
end
end

def +(other)
if other.kind_of?(Integer)
return HeadTailBignum.new(self.hi + other, self.lo + other)
return HeadTailBignum.new(self.hi + other.hi , self.lo + other.lo)
else
end
end
def *(other)
if other.kind_of?(Integer)
return HeadTailBignum.new(self.hi * other, self.lo * other)
return HeadTailBignum.new(self.hi * other.hi , self.lo * other.lo)
else
raise StandardError.new("HeadTailBignum mulply Type Error (" + other.class.to_s + ")")
end

end

def exponent
@hi.exponent
end
def to_s
if @hi < @@loDegitsBase
return @lo.inspect
else
return @hi.to_s("E").slice(2,@@degitsLimit ) + " ... " + @lo.to_s
end
end
end

start_time = Time.now
[8,16,32,64].each {|h|
n = (2**h)
puts "Fibonacci(2^#{h.to_s}) = #{fib_Num.to_s} are #{fib_Num.exponent} degits"
}
puts "Took #{Time.now - start_time}s"

```

```Fibonacci(2^8) = 14169381771405651323 ... 19657707794958199867 are 54 degits