CODEWITHSUNDEEP
pythonpython-3.xfibonacci
rpgstar
rpgstar

Reputation: 132

My Fibonacci generator is giving incorrect results

I am trying to work on a function which takes in a value n and outputs the nth number in the Fibonacci sequence. I have a looping function which seems to work like so:

def fibonacci_v1(n):
    a = b = 1
    for _ in range(1, n):
        a, b = b, a + b
    return a

and I am trying to work on a version which uses Binet's Formula as describes here:

Phi = (1 + math.sqrt(5)) / 2


def fibonacci_v2(n):
    c = pow(Phi, n)
    return math.floor((c - pow(-1, n) / c) / math.sqrt(5))

which seems to work for low values of n but breaks when a number is entered which is higher than 72... I suspect that this has to do with the accuracy of the math.sqrt() function but the documentation here doesn't say anything about its level of accuracy... is it the case that this is an issue with math.sqrt or is there something else wrong with my function?

For testing purposes I was using this for loop:

for x in range(1, 73):
    print(fibonacci_v1(x))
    print(fibonacci_v2(x))

Upvotes: 0

Views: 231

Answers (2)

Mark Tolonen
Mark Tolonen

Reputation: 177620

If you are looking for speed and accuracy, use a Python generator instead. Below calculates the first 10,000 Fibonacci numbers in five milliseconds, then calculates (but doesn't store) F0 to F999,999 in ~17s, and then prints the number of digits in F1,000,000. Since this uses integer math instead of floating point, it is much faster and has no inaccuracies.

import time

def fib():
    a,b = 0,1
    while True:
        yield a
        a,b = b,a+b

s = time.time()
it = fib()
f = [next(it) for _ in range(10000)] # list of F[0] - f[9999]
print(time.time() - s)

s = time.time()
it = fib()
for _ in range(1000000): # Skip over F[0]-F[999999]
    next(it)
print(time.time() - s)
print(len(str(next(it)))) # display no. of digits in F[1000000].

f = [next(it) for _ in range(10000)]
it = fib()
for _ in range(1000000): # Skip over F[0]-F[999999]
    next(it)
print(len(str(next(it)))) # display no. of digits in F[1000000].

Output:

0.005221128463745117
17.795812129974365
208988

Upvotes: 0

Anurag Wagh
Anurag Wagh

Reputation: 1086

This has less to do with math.sqrt than how the floating-point numbers are represented in python. The default implementation

Almost all machines today (November 2000) use IEEE-754 floating point arithmetic, and almost all platforms map Python floats to IEEE-754 “double precision”.

You can read more about the limitation of in-built floating-point here.

You can use decimal module to take care of this inaccuracy

Unlike hardware based binary floating point, the decimal module has a user alterable precision

If you need even more accurate representation you can use getContext() to tweak the precision

from decimal import *
# Your Existing v1 implementation 
def fibonacci_v1(n):
    a = b = 1
    for _ in range(1, n):
        a, b = b, a + b
    return a

Phi = (1 + Decimal(5).sqrt()) / 2
# V2 implementation using the decimal module
def fibonacci_v2(n):
    getcontext().prec = 4096 # You need to tweak this number based on your precision requirements 
    c = Decimal(Phi) ** n
    fib = (c - (Decimal(-1)** n) / c) / Decimal(5).sqrt()
    return fib.quantize(Decimal('1.'), rounding=ROUND_UP)


for x in range(73, 80):
    print(f"n={x}: v1={fibonacci_v1(x)}, v2={fibonacci_v2(x)}")

Output:

n=73: v1=806515533049393, v2=806515533049393
n=74: v1=1304969544928657, v2=1304969544928657
n=75: v1=2111485077978050, v2=2111485077978050
n=76: v1=3416454622906707, v2=3416454622906707
n=77: v1=5527939700884757, v2=5527939700884757
n=78: v1=8944394323791464, v2=8944394323791464
n=79: v1=14472334024676221, v2=14472334024676221

Upvotes: 1

Related Questions