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.     ## This one could be improved by binary squaring
  38.     def __pow__(self, n):
  39.         if n == 0:
  40.             return Qsqrt5(1)
  41.         return self*(self**(n-1))
  42.  
  43. phi1 = Qsqrt5(F(1,2), F(1,2))
  44. phi2 = Qsqrt5(F(1,2), -F(1,2))
  45.  
  46. def fib(n):
  47.     #Binet's formula
  48.     return (phi1**n - phi2**n)/(phi1 - phi2)
  49.  
  50. print fib(1)
  51. print fib(2)
  52. print fib(3)
  53. print fib(80)
  54.  
Success #stdin #stdout 0.13s 10536KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
1
2
23416728348467685
https://ideone.com/9dHQV9
language:
Python (cpython 2.7.16)
created:
10 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!