from fractions import Fraction as F
class Qsqrt5:
def __repr__(self):
return self.__str__()
def __str__(self):
if self.b == 0:
return str(self.a)
if self.a == 0:
return "{0} sqrt(5)".format(str(self.b))
return "{0} + {1} sqrt(5)".format(str(self.a), str(self.b))
def __init__(self, a, b=0):
self.a = F(a)
self.b = F(b)
## Define arithmetic on Q[sqrt(5)], analogous to defining
## arithmetic on the complex numbers
def __add__(self, other):
return Qsqrt5(self.a + other.a, self.b + other.b)
def __sub__(self, other):
return Qsqrt5(self.a - other.a, self.b - other.b)
def __mul__(self, other):
return Qsqrt5(self.a*other.a + 5*self.b*other.b,
self.a*other.b + self.b*other.a)
def inverse(self):
denom = self.a**2 - 5*self.b**2
return Qsqrt5(self.a/denom, -self.b/denom)
def __div__(self, other):
return self*other.inverse()
## This one could be improved by binary squaring
def __pow__(self, n):
if n == 0:
return Qsqrt5(1)
return self*(self**(n-1))
phi1 = Qsqrt5(F(1,2), F(1,2))
phi2 = Qsqrt5(F(1,2), -F(1,2))
def fib(n):
#Binet's formula
return (phi1**n - phi2**n)/(phi1 - phi2)
print fib(1)
print fib(2)
print fib(3)
print fib(80)
ZnJvbSBmcmFjdGlvbnMgaW1wb3J0IEZyYWN0aW9uIGFzIEYKCmNsYXNzIFFzcXJ0NToKICAgIGRlZiBfX3JlcHJfXyhzZWxmKToKICAgICAgICByZXR1cm4gc2VsZi5fX3N0cl9fKCkKCiAgICBkZWYgX19zdHJfXyhzZWxmKToKICAgICAgICBpZiBzZWxmLmIgPT0gMDoKICAgICAgICAgICAgcmV0dXJuIHN0cihzZWxmLmEpCiAgICAgICAgaWYgc2VsZi5hID09IDA6CiAgICAgICAgICAgIHJldHVybiAiezB9IHNxcnQoNSkiLmZvcm1hdChzdHIoc2VsZi5iKSkKICAgICAgICByZXR1cm4gInswfSArIHsxfSBzcXJ0KDUpIi5mb3JtYXQoc3RyKHNlbGYuYSksIHN0cihzZWxmLmIpKQoKICAgIGRlZiBfX2luaXRfXyhzZWxmLCBhLCBiPTApOgogICAgICAgIHNlbGYuYSA9IEYoYSkKICAgICAgICBzZWxmLmIgPSBGKGIpCgogICAgIyMgRGVmaW5lIGFyaXRobWV0aWMgb24gUVtzcXJ0KDUpXSwgYW5hbG9nb3VzIHRvIGRlZmluaW5nCiAgICAjIyBhcml0aG1ldGljIG9uIHRoZSBjb21wbGV4IG51bWJlcnMKICAgIGRlZiBfX2FkZF9fKHNlbGYsIG90aGVyKToKICAgICAgICByZXR1cm4gUXNxcnQ1KHNlbGYuYSArIG90aGVyLmEsIHNlbGYuYiArIG90aGVyLmIpCgogICAgZGVmIF9fc3ViX18oc2VsZiwgb3RoZXIpOgogICAgICAgIHJldHVybiBRc3FydDUoc2VsZi5hIC0gb3RoZXIuYSwgc2VsZi5iIC0gb3RoZXIuYikKCiAgICBkZWYgX19tdWxfXyhzZWxmLCBvdGhlcik6CiAgICAgICAgcmV0dXJuIFFzcXJ0NShzZWxmLmEqb3RoZXIuYSArIDUqc2VsZi5iKm90aGVyLmIsCiAgICAgICAgICAgICAgICAgICAgICBzZWxmLmEqb3RoZXIuYiArIHNlbGYuYipvdGhlci5hKQoKICAgIGRlZiBpbnZlcnNlKHNlbGYpOgogICAgICAgIGRlbm9tID0gc2VsZi5hKioyIC0gNSpzZWxmLmIqKjIKICAgICAgICByZXR1cm4gUXNxcnQ1KHNlbGYuYS9kZW5vbSwgLXNlbGYuYi9kZW5vbSkKCiAgICBkZWYgX19kaXZfXyhzZWxmLCBvdGhlcik6CiAgICAgICAgcmV0dXJuIHNlbGYqb3RoZXIuaW52ZXJzZSgpCgogICAgIyMgVGhpcyBvbmUgY291bGQgYmUgaW1wcm92ZWQgYnkgYmluYXJ5IHNxdWFyaW5nCiAgICBkZWYgX19wb3dfXyhzZWxmLCBuKToKICAgICAgICBpZiBuID09IDA6CiAgICAgICAgICAgIHJldHVybiBRc3FydDUoMSkKICAgICAgICByZXR1cm4gc2VsZiooc2VsZioqKG4tMSkpCgpwaGkxID0gUXNxcnQ1KEYoMSwyKSwgRigxLDIpKQpwaGkyID0gUXNxcnQ1KEYoMSwyKSwgLUYoMSwyKSkKCmRlZiBmaWIobik6CiAgICAjQmluZXQncyBmb3JtdWxhCiAgICByZXR1cm4gKHBoaTEqKm4gLSBwaGkyKipuKS8ocGhpMSAtIHBoaTIpCgpwcmludCBmaWIoMSkKcHJpbnQgZmliKDIpCnByaW50IGZpYigzKQpwcmludCBmaWIoODApCg==