My Fibonacci generator is giving incorrect results

Question

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

This is incredibly close to a duplicate, but not quite. https://stackoverflow.com/questions/10725522/arbitrary-precision-of-square-roots — Adam Smith, Oct 20 '20 at 05:28
@AdamSmith I think you are right... I will leave it open unless someone else closes it but it seems reasonable that it would be a duplicate. — rpgstar, Oct 20 '20 at 05:55

Anurag Wagh · Accepted Answer · 2020-10-20T06:18:36.780

1

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

edited Oct 20 '20 at 06:18

answered Oct 20 '20 at 05:42

Anurag Wagh

1,086
6
16

`decimal` is still floating point. It's just configurable-precision, decimal floating point. It's still subject to rounding error. – user2357112 Oct 20 '20 at 05:46
You are correct, I meant the in-built float precision isn't accurate. I'll reword it – Anurag Wagh Oct 20 '20 at 05:49
This answer seems to have gotten me much farther at least (small hiccup at 465 but that may still be floating point accuracy) – rpgstar Oct 20 '20 at 05:57
After changing the accuracy that does seem to be the issue... I wonder if there'd be a way of having the accuracy scale as n increases... – rpgstar Oct 20 '20 at 06:01
@rpgstar You can configure the Decimal accuracy using for example `c=decimal.getcontext(); c.prec=1000` which gives you 1000 digits of precision. – Mark Tolonen Oct 20 '20 at 06:01
@rpgstar as Mark suggested, `getcontext().prec = 4096` would take care for n=465. Updated the answer – Anurag Wagh Oct 20 '20 at 06:20

score 0 · Answer 2 · answered Oct 20 '20 at 06:48

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) F₀ to F_999,999 in ~17s, and then prints the number of digits in F_1,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

My Fibonacci generator is giving incorrect results

2 Answers2