CODEWITHSUNDEEP
pythonalgorithmfibonacci
Tony Chen
Tony Chen

Reputation: 183

why is my little python fibonacci detector failed?

for some reason I have to determine if a big number is a fibonacci number, so I copy some code from internet and modified it a little, it seems not operate well when it's big input. here is code:

# python program to check if x is a perfect square

import math

# A utility function that returns true if x is perfect square
def isPerfectSquare(x):
    s = int(math.sqrt(x))
    boo = (s*s == x);
    return boo

# Returns true if n is a Fibinacci Number, else false
def isFibonacci(n):

    # n is Fibinacci if one of 5*n*n + 4 or 5*n*n - 4 or both
    # is a perferct square
    b = 5*n*n+4;
    c = 5*n*n-4;
    return isPerfectSquare(b) or isPerfectSquare(c)

# A utility function to test above functions

a = int(input("give me the number"));
print(isFibonacci(a))

when I input 610, it output true as planed, but when I input 

"215414832505658809004682396169711233230800418578767753330908886771798637"

which I know is the 343rd fibonacci number from another java program I made. it output false surprisingly. So is it because the number is too large so it makes mistakes? but I think python should be able to handle enormous big number because it is based on the memory you have? is the problem in my program or is it because it's too big input? Thx!

Upvotes: 1

Views: 177

Answers (4)

jmd_dk
jmd_dk

Reputation: 13120

As already pointed out, the problem arise solely from math.sqrt, which is a floating point operation, meaning not exactly precise (unlike integer operations). The precision of floats in python is about 16, meaning that precision float operations on a number with more than 16 digits always goes bad.

Instead of using floats (math.sqrt converts your integer to float implicitly), you can use the Decimal type from the decimal module, included in the standard library. This is a floating point type with variable, controllable precision. To fix your program, simply replace your isPerfectSquare function with this:

import decimal
def isPerfectSquare(x):
    # Set decimal precision and convert x to Decimal type
    decimal.getcontext().prec = len(str(x))
    x = decimal.Decimal(x)
    # Check if perfect square
    s = int(x.sqrt())
    boo = (s*s == x);
    return boo

Here the precision is set equal to the number of digits of the input number, which is given by the length of the str representation of the input number.

Upvotes: 2

scugn1zz0
scugn1zz0

Reputation: 337

It is related to the fact that python loose precision after 52 digits (in total before and after the dot). You have to use gmpy2.square() imported from module gmpy2 this is the only way you can handle big numbers.

Upvotes: 0

Yousef Azizi
Yousef Azizi

Reputation: 159

I checked it with Fibonacci numbers produced from mupad in Matlab(use numlib::fibonacci(n)) . It's because of precision. Python can't detect more than 52 precision, so for numbers larger than 2^52, precision will be lost. You can checked it with 76th fibonacci number and 77th fibonacci number to see the probelm. 76th fibonacci number: 3416454622906707 77th fibonacci number: 5527939700884757

Upvotes: 1

DYZ
DYZ

Reputation: 57105

You have a loss of precision. For n > 1e45 (approximately), (n**0.5)**2 != n. Try using gmpy2.isqrt() and gmpy2.square() from module gmpy2 - they are designed to work with very large integer numbers.

Upvotes: 5

Related Questions