CODEWITHSUNDEEP
pythonfibonaccifloating-accuracy
13deadfrogs
13deadfrogs

Reputation: 19

Errors in Directly vs Recursively Calculating a given Fibonacci Number

I was bored at work and was playing with some math and python coding, when I noticed the following:

Recursively (or if using a for loop) you simply add integers together to get a given Fibonacci number. However there is also a direct equation for calculating Fibonacci numbers, and for large n this equation will give answers that are, frankly, quite wrong with respect to the recursively calculated Fibonacci number.

I imagine this is due to rounding and floating point arithmetic ( sqrt(5) is irrational after all), and if so can anyone point me into a direction on how I could modify the fibo_calc_direct function to return a more accurate result?

Thanks!

def fib_calc_recur(n, ii = 0, jj = 1): 
    #n is the index of the nth fibonacci number, F_n, where F_0 = 0, F_1 = 1, ...
    if n == 0: #use recursion
        return ii
    if n == 1:
        return jj
    else:
        return(fib_calc_recur(n -1, jj, ii + jj))

def fib_calc_direct(n):

    a = (1 + np.sqrt(5))/2
    b = (1 - np.sqrt(5))/2

    f = (1/np.sqrt(5)) * (a**n - b**n)
    return(f)

Upvotes: 1

Views: 69

Answers (1)

trincot
trincot

Reputation: 351384

You could make use of Decimal numbers, and set its precision depending on the magninute of n

Not your question, but I'd use an iterative version of the addition method. Here is a script that makes both calculations (naive addition, direct with Decimal) for values of n up to 4000:

def fib_calc_iter(n): 
    a, b = 0, 1
    
    if n < 2:
        return n
    for _ in range(1, n):
        a, b = b, a + b
    return b

from decimal import Decimal, getcontext

def fib_calc_decimal(n):
    getcontext().prec = n // 4 + 3  # Choose a precision good enough for this n
    sqrt5 = Decimal(5).sqrt()
    da = (1 + sqrt5) / 2
    db = (1 - sqrt5) / 2
    f = (da**n - db**n) / sqrt5
    return int(f + Decimal(0.5))  # Round to nearest int

# Test it...
for n in range(1, 4000):
    x = fib_calc_iter(n)
    y = fib_calc_decimal(n)
    if x != y:
        print(f"Difference found for n={n}.\nNaive method={x}.\nDecimal method={y}")
        break
else:
    print("No differences found")

Upvotes: 1

Related Questions