require "mathn"
def fib_tuple(n)
x1, x0, a, b = 1, 0, 1, 0
while (n != 0)
x1, x0 = x1*(a + b) + x0*a, x1*a + x0*b if n[0] == 1
a, b = (a**2) + 2*a*b, (a**2) + (b**2)
n >>= 1
end
[x0, x1]
end
class Integer
def digits
self.to_s(10).length
end
end
def linear_search(digits, x0, x1)
i = 1
loop {
return [x0, x1, i] if x0.digits < x1.digits and x1.digits == digits
x0, x1, i = x1, x0 + x1, i + 1
}
end
begin_time = Time.now
golden_ratio = (1 + Math.sqrt(5)) / 2
start_index = ((1000 - 1) / (Math.log10(golden_ratio))).floor
start_tuple = fib_tuple(start_index)
result_triple = linear_search(1000, *start_tuple)
end_time = Time.now
p result_triple[1]
p start_index + result_triple[2]
p end_time - begin_time
require "mathn"
class Fibonacci
attr_accessor :tuple, :index
protected :tuple, :tuple=, :index=
def initialize
@tuple = [1, 0]
@index = 0
end
def succ!
a, b = *@tuple
@tuple = [b, a + b]
@index += 1
self
end
def succ
robj = self.clone
robj.succ!
end
def *(t)
a, b = *@tuple
c, d = *t.tuple
robj = self.class.new
robj.tuple = [a*c + b*d, a*d + b*(c + d)]
robj.index = @index + t.index
robj
end
def **(i)
a, b = *@tuple
c, d = 1, 0
n = i
while (n != 0)
c, d = a*c + b*d, a*d + b*(c + d) if n[0] == 1
a, b = (a**2) + (b**2), 2*a*b + (b**2)
n >>= 1
end
robj = self.class.new
robj.tuple = [c, d]
robj.index = @index * i
robj
end
def inv!
a, b = *@tuple
det = (a**2) + a*b - (b**2)
@tuple = [(a + b) / det, -b / det]
@index *= -1
self
end
def inv
robj = self.clone
robj.inv!
end
def inspect
"#<#{@tuple.inspect} at #{@index.inspect}>"
end
def to_fibonacci
@tuple[1]
end
def to_vector
a, b = *@tuple
Vector[b, a]
end
def to_matrix
a, b = *@tuple
Matrix[[a + b, b], [b, a]]
end
end
p a = Fibonacci.new
p b = Fibonacci.new.succ
p c = b.succ
p b*c
p d = c**2
p b*d
p e = (b**2)*(c**2)
p e.to_fibonacci
p f = e.to_vector
p g = e.to_matrix
p g*f
p Fibonacci.new.succ!**1000
p e*e.inv
