Skip to content

Instantly share code, notes, and snippets.

@mightymercado
Created March 13, 2020 05:01
Show Gist options
  • Save mightymercado/c5ad9c74d2773d8e5604dcde2542e566 to your computer and use it in GitHub Desktop.
Save mightymercado/c5ad9c74d2773d8e5604dcde2542e566 to your computer and use it in GitHub Desktop.
Computing Binet's Formula without Loss
from __future__ import annotations
'''
Unique way of solving fibonacci number.
By computing Binet's formula using integer operations only.
We do this by representing (1 + √5) and (1 - √5) as generalized tuple
representing the sum of an integer and the coefficient of √5.
All tuples would represent a algebraic field under basic arithmetic (+, -, *, /, and pow).
Below I implement this tuple as `binet` class then implement the
operations as class operators.
By some analysis or observation, the binet(1, 1)**n
has the same value with binet(1, -1)**n except that
the √5 coefficient is negated.
We compute the nth power by exponentiation by squaring
because we know that multiplication is commutative.
Side note:
The tuple themselves generate two simultaenous linear recurrences.
i(x) = i(x - 1) + 5 * s(x - 1)
s(x) = s(x - 1) + i(x - 1)
But when evaluated using standard techniques, just
gives the same results involving √5.
'''
class binet:
'''
represents
(i + s√5)
'''
def __init__(self, i: int, s: int):
self.i = i # integer
self.s = s # square root of 5 coefficient
def __mul__(self, other: binet):
return binet(self.i * other.i + self.s * self.s * 5,
self.i * other.s + other.i * self.s)
def __sub__(self, other: binet):
return binet(self.i - other.i, self.s - other.s)
def __pow__(self, n: int):
b = self
r = binet(1, 0)
while n > 0:
if n % 2 == 1: r = r * b
n //= 2
b = b * b
return r
def __repr__(self):
return f'({self.i} + {self.s}√5)'
def fib(n: int):
# return (binet(1, 1)**n - binet(1, -1)**n).s // 2**n
# return (binet(1, 1)**n).s * 2 // 2**n
return (binet(1, 1)**n).s // 2**(n-1)
if __name__ == '__main__':
print(fib(20))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment