Fibonacci matrix-exponentiation: Difference between revisions
m
→{{header|Wren}}: Minor tidy
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
m (→{{header|Wren}}: Minor tidy) |
||
| (9 intermediate revisions by one other user not shown) | |||
Line 1,704:
2^64 : 11175807536929528424 ... 17529800348089840187
2^128: 15262728879740471565 ... 17229324095882654267</pre>
=={{header|Ruby}}==
===Matrix exponentiation by Ruby's fast exponentiation operator duck-typing applied to Ruby's built-in Integer Class===
<pre>
require 'matrix'
start_time = Time.now
[0,1,2,3,4,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] ## Matrix exponentiation
##
fib_Str= fib_Num.to_s()
if fib_Str.length <= 21
p ["Fibonacci(#{n})",fib_Str.length.to_s + ' digits' , fib_Str]
else
p ["Fibonacci(#{n})",fib_Str.length.to_s + ' digits' , fib_Str.slice(0,20) + " ... " + fib_Str.slice(-20,20)]
end
}
puts "Took #{Time.now - start_time}s"
</pre>
{{out}}
<pre>
["Fibonacci(0)", "1 digits", "0"]
["Fibonacci(1)", "1 digits", "1"]
["Fibonacci(2)", "1 digits", "1"]
["Fibonacci(3)", "1 digits", "2"]
["Fibonacci(4)", "1 digits", "3"]
["Fibonacci(10)", "2 digits", "55"]
["Fibonacci(100)", "21 digits", "354224848179261915075"]
["Fibonacci(256)", "54 digits", "14169381771405651323 ... 19657707794958199867"]
["Fibonacci(1000)", "209 digits", "43466557686937456435 ... 76137795166849228875"]
["Fibonacci(1024)", "214 digits", "45066996336778198131 ... 04103631553925405243"]
["Fibonacci(10000)", "2090 digits", "33644764876431783266 ... 66073310059947366875"]
["Fibonacci(65536)", "13696 digits", "73199214460290552832 ... 97270190955307463227"]
["Fibonacci(100000)", "20899 digits", "25974069347221724166 ... 49895374653428746875"]
["Fibonacci(1000000)", "208988 digits", "19532821287077577316 ... 68996526838242546875"]
["Fibonacci(10000000)", "2089877 digits", "11298343782253997603 ... 86998673686380546875"]
Took 1.027948065s
</pre>
===Matrix exponentiation by Ruby's Matlix#exponentiation 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} digits"
}
puts "Took #{Time.now - start_time}s"
{{out}}
<pre>
Fibonacci(2^8) = 14169381771405651323 ... 19657707794958199867 are 54 digits
Fibonacci(2^16) = 73199214460290552832 ... 97270190955307463227 are 13696 digits
Fibonacci(2^32) = 61999319689381859818 ... 39623735538208076347 are 897595080 digits
Fibonacci(2^64) = 11175807536929528424 ... 17529800348089840187 are 3855141514259838964 digits
Took 0.009357194s
</pre>
=={{header|Raku}}==
(formerly Perl 6)
Line 1,878 ⟶ 2,011:
{{libheader|Wren-fmt}}
A tough task for Wren which takes just under 3 minutes to process even the 1 millionth Fibonacci number. Judging by the times for the compiled, statically typed languages using GMP, the 10 millionth would likely take north of 4 hours so I haven't attempted it.
<syntaxhighlight lang="
import "./fmt" for Fmt
var mul = Fn.new { |m1, m2|
Line 1,996 ⟶ 2,129:
Apart from the 2^16th number, the extra credit is still out of reach using this approach.
<syntaxhighlight lang="
import "./fmt" for Fmt
var lucas = Fn.new { |n|
Line 2,078 ⟶ 2,211:
{{libheader|Wren-gmp}}
Ridiculously fast (under 5ms) thanks to the stuff borrowed from Sidef and Julia combined with the speed of GMP.
<syntaxhighlight lang="
import "./fmt" for Fmt
| |||