Fibonacci Numbers in Java - `O(n)` time and `O(1)` space complexity and without using Recursion

Processing Coding Questions
4

See Wolfram MathWorld: Binet’s Fibonacci Number Formula.

Since we can only store approximations of φ and ψ, calculations of the nth Fibonacci number using Binet’s formula can be expected to diverge from the truth for high values of n.

Let’s test this using Python 3 …

def fib_binet(n):
    # Binet's method (approximation) O(1)
    phi = (5.0 ** 0.5 + 1.0) / 2.0
    psi = 1.0 - phi
    return int((phi ** n - psi ** n) / (phi - psi))

def fib_iter(n):
    # iterative method (exact) O(n)
    a, b = 0, 1
    for i in range(n):
        a, b = a + b, a
    return a

for n in range(80):
  if fib_binet(n) != fib_iter(n):
    print(n - 1, fib_binet(n - 1), fib_iter(n - 1))
    print(n, fib_binet(n), fib_iter(n))
    break

Output:

71 308061521170129 308061521170129
72 498454011879265 498454011879264

Calculations were fine for values of n between 0 and 71, inclusive, but diverged from the truth, thereafter.

Please feel free to try this with Java, and post the results here.

1 Like