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

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'

class HeadTailBignum < Numeric
	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
   	elsif other.kind_of?(HeadTailBignum)
   		@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
   	HeadTailBignum(self.hi, self.lo)
   end

   def integer?()
   	true
   end
	def coerce(other)
		if other.kind_of?(Integer)
          return HeadTailBignum.new(other), self
		else
          super
		end
   end

   def +(other)
   	if other.kind_of?(Integer)
   		return HeadTailBignum.new(self.hi + other, self.lo + other)
   	elsif other.kind_of?(HeadTailBignum)
   	    return HeadTailBignum.new(self.hi + other.hi , self.lo + other.lo)
   	else
           raise StandardError.new("HeadTailBignum add Type Error (" + other.class.to_s + ")")    		
       end
   end
   def *(other)
   	if other.kind_of?(Integer)
   		return HeadTailBignum.new(self.hi * other, self.lo * other)
   	elsif other.kind_of?(HeadTailBignum)
  	    	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)
   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} degits"  
}
puts "Took #{Time.now - start_time}s"

Outputs HeadTailBignum:

Fibonacci(2^8) = 14169381771405651323 ... 19657707794958199867 are 54 degits
Fibonacci(2^16) = 73199214460290552832 ... 97270190955307463227 are 13696 degits
Fibonacci(2^32) = 61999319689381859818 ... 39623735538208076347 are 897595080 degits
Fibonacci(2^64) = 11175807536929528424 ... 17529800348089840187 are 609335284 degits
Took 0.009357194s