Post Reply 
(12C) Check if given number is Fibonacci number
09-04-2018, 11:58 AM (This post was last modified: 09-04-2018 01:51 PM by Gamo.)
Post: #1
(12C) Check if given number is Fibonacci number
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
Find all posts by this user
Quote this message in a reply
09-04-2018, 02:00 PM
Post: #2
RE: (12C) Check if given number is Fibonacci number
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.
Find all posts by this user
Quote this message in a reply
09-04-2018, 02:25 PM
Post: #3
RE: (12C) Check if given number is Fibonacci number
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
Find all posts by this user
Quote this message in a reply
09-07-2018, 03:19 PM
Post: #4
RE: (12C) Check if given number is Fibonacci number
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)
Find all posts by this user
Quote this message in a reply
09-07-2018, 07:33 PM (This post was last modified: 09-08-2018 09:10 PM by Albert Chan.)
Post: #5
RE: (12C) Check if given number is Fibonacci number
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
Find all posts by this user
Quote this message in a reply
09-08-2018, 06:48 PM
Post: #6
RE: (12C) Check if given number is Fibonacci number
Hello, Albert!

Your remarks is correct and very useful.
Thanks you.
Find all posts by this user
Quote this message in a reply
09-09-2018, 12:14 AM (This post was last modified: 09-09-2018 01:35 AM by Albert Chan.)
Post: #7
RE: (12C) Check if given number is Fibonacci number
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.
Find all posts by this user
Quote this message in a reply
Post Reply 




User(s) browsing this thread: 1 Guest(s)