(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
 Gamo Senior Member Posts: 700 Joined: Dec 2016
(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
09-04-2018, 02:00 PM
Post: #2
 Albert Chan Senior Member Posts: 1,600 Joined: Jul 2018
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.
09-04-2018, 02:25 PM
Post: #3
 Gamo Senior Member Posts: 700 Joined: Dec 2016
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
09-07-2018, 03:19 PM
Post: #4
 stored Junior Member Posts: 15 Joined: Sep 2016
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)
09-07-2018, 07:33 PM (This post was last modified: 09-08-2018 09:10 PM by Albert Chan.)
Post: #5
 Albert Chan Senior Member Posts: 1,600 Joined: Jul 2018
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
09-08-2018, 06:48 PM
Post: #6
 stored Junior Member Posts: 15 Joined: Sep 2016
RE: (12C) Check if given number is Fibonacci number
Hello, Albert!

Your remarks is correct and very useful.
Thanks you.
09-09-2018, 12:14 AM (This post was last modified: 09-09-2018 01:35 AM by Albert Chan.)
Post: #7
 Albert Chan Senior Member Posts: 1,600 Joined: Jul 2018
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.
 « Next Oldest | Next Newest »

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