Talk:Fibonacci matrix-exponentiation: Difference between revisions
Talk:Fibonacci matrix-exponentiation (view source)
Revision as of 17:04, 8 June 2023
, 11 months ago→Ruby's Matlix duck-typeing with Head-tail-BigNumber class: new section
(→Ruby) |
(→Ruby's Matlix duck-typeing with Head-tail-BigNumber class: new section) |
||
Line 38:
[1000000, "208988 digits", "19532821287077577316 ... 6899652683824254687", "Took 0.104574053s"]
[10000000, "2089877 digits", "11298343782253997603 ... 8699867368638054687", "Took 0.996411418s"]
== 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 '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
| |||