(12C) Check if given number is Fibonacci number

[Gamo]

Program to check if a given number is Fibonacci Number or not.

Procedure:

Yes display 1
No display 0

Example:

377 [R/S] display 1 // Yes this is Fibonacci Number

234 [R/S] display 0 // This number is not Fibonacci Number

987 [R/S] display 1

Program:

Code:


01 STO 1
02 ENTER
03  x
04  5
05  x
06  4
07  +
08  √x
09 FRAC
10 X=0 ?
11 GTO 25
12 RCL 1
13 ENTER
14  x
15  5
16  x
17  4
18  -
19 √x
20 FRAC
21 X=0 ?
22 GTO 25
23  0
24 GTO 00
25  1

Gamo

[Albert Chan]

Nice formula:

If (5 x^2 +/- 4) is perfect square, x is Fibonacci number.

However, there is a weakness if done on the HP-12C.
For x > 44721, the expression overflow 10-digits. Rounding errors kill the algorithm.

So, above code has a safe domain upto 44721 (only 23 Fibonacci numbers in that range)
It might be better to generate the Fibonacci numbers directly, and test the input.

[Gamo]

Thanks Albert Chan

Good idea. I was thinking about other ways to do this.
Let's see if anyone got any other ways to do this better.

Thanks

Gamo

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

[Albert Chan]

Hi, stored

Good job !

HP-12C does not have the precision of Python float (~ 15 decimals)
It failed with Fib(40) = 102334155, see First 300 Fibonacci Numbers

But, if you use <= eps, instead of < eps, it barely squeezed thru.

BTW, you do not need to check all possible X's.
Since the code is fitting n as a straight line, n ~ 1/ln(phi) * ln(X)+ ln(sqrt(5))/ln(phi),
only range of Fib(n) +/- 1 for confirmation is enough.

Edit : < eps passes Fib(40), if use form:

n = ln(X)/ln(phi) + ln(sqrt(5))/ln(phi) ~ ln(X)/0.4812118252 + 1.672275938

Test can be simplifed as IS_FIB = int(n + 1/X) - int(n - 1/X), where 0=False, 1=True

[stored]

Hello, Albert!

Your remarks is correct and very useful.
Thanks you.

[Albert Chan]

Hi, stored

To extend your algorithm for full ten digits (your code take care of eight), I use Binet formula.
Instead of guessing n from X, do it in reverse, with HP12C correction to match actual Fib(n):

X = phi^n / sqrt(5)
X = X - X * 7.7e-9
X = INT(X + 0.5)

For n>40, if your code think the number may be Fibonacci, above can check it.
note: eps = 2e-8 may cover this range, but need actual confirmation.