fork(1) download
copy 
  1. from fractions import Fraction as F
  2.  
  3. class Qsqrt5:
  4.     def __repr__(self):
  5.         return self.__str__()
  6.  
  7.     def __str__(self):
  8.         if self.b == 0:
  9.             return str(self.a)
  10.         if self.a == 0:
  11.             return "{0} sqrt(5)".format(str(self.b))
  12.         return "{0} + {1} sqrt(5)".format(str(self.a), str(self.b))
  13.  
  14.     def __init__(self, a, b=0):
  15.         self.a = F(a)
  16.         self.b = F(b)
  17.  
  18.     ## Define arithmetic on Q[sqrt(5)], analogous to defining
  19.     ## arithmetic on the complex numbers
  20.     def __add__(self, other):
  21.         return Qsqrt5(self.a + other.a, self.b + other.b)
  22.  
  23.     def __sub__(self, other):
  24.         return Qsqrt5(self.a - other.a, self.b - other.b)
  25.  
  26.     def __mul__(self, other):
  27.         return Qsqrt5(self.a*other.a + 5*self.b*other.b,
  28.                       self.a*other.b + self.b*other.a)
  29.  
  30.     def inverse(self):
  31.         denom = self.a**2 - 5*self.b**2
  32.         return Qsqrt5(self.a/denom, -self.b/denom)
  33.  
  34.     def __div__(self, other):
  35.         return self*other.inverse()
  36.  
  37.     def __pow__(self, n):
  38.         if n == 0:
  39.             return Qsqrt5(1)
  40.  
  41.         ## Do binary squaring
  42.         halfpower = self**(n//2)
  43.         return halfpower*halfpower*(self if n%2 == 1 else Qsqrt5(1))
  44.  
  45.  
  46. phi1 = Qsqrt5(F(1,2), F(1,2))
  47. phi2 = Qsqrt5(F(1,2), -F(1,2))
  48.  
  49. def fib(n):
  50.     #Binet's formula
  51.     return (phi1**n - phi2**n)/(phi1 - phi2)
  52.  
  53. print fib(1)
  54. print fib(2)
  55. print fib(3)
  56. print fib(80)
  57.  
Success #stdin #stdout 0.03s 8656KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
1
2
23416728348467685
https://ideone.com/NWQe38
language:
Python (cpython 2.7.16)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!