Computing Binet's Formula without Loss

binet.py

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))