(12C) Check if given number is Fibonacci number

[stored]

Hello, Gamo!

About overflow problem. I suggest alternative algorithm.
In Binet's formula the second term tends to zero when n → ∞:
((1-√5)/2)^n → 0

So, we can approx F_n with only first term and check that estimated n is close to integer number.
n ∼ (ln(√5) + ln(n)) / ln(phi), phi = (1+√5)/2

I write small Python3 script and checked that this approach is correct for all arguments > 1 up to 10^10.
In program n means number to test. Function is_fib1 implements your algorithm (without overflow due to integer numbers in Python is dinamically sized).
I think, it may be programmed on calculator.

Code:


from math import sqrt, log

def is_square(n):
    k = round(sqrt(n))
    return k*k==n

def is_fib1(n):
    return is_square(5*n**2+4) or is_square(5*n**2-4)

def is_near_int(x, eps):
    return abs(x - round(x)) < eps

def is_fib2(n):
    phi = (sqrt(5)+1) / 2
    x = (log(sqrt(5)) + log(n)) / log(phi)
    return is_near_int(x, eps=1/n)

def check(m):
    for n in range(2, m+1):
        if is_fib1(n) != is_fib2(n):
            print('Incorrect for n =', n)
            return
        if n%10000000 == 0: # show progress
            print(n)
    print('Correct up to', m)

check(10**10)