+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Software Libraries (/forum-10.html)
+--- Forum: General Software Library (/forum-13.html)
+--- Thread: (12C) Check if given number is Fibonacci number (/thread-11336.html)
(12C) Check if given number is Fibonacci number - Gamo - 09-04-2018 11:58 AM
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 1Gamo
RE: (12C) Check if given number is Fibonacci number - Albert Chan - 09-04-2018 02:00 PM
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.
RE: (12C) Check if given number is Fibonacci number - Gamo - 09-04-2018 02:25 PM
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
RE: (12C) Check if given number is Fibonacci number - stored - 09-07-2018 03:19 PM
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)RE: (12C) Check if given number is Fibonacci number - Albert Chan - 09-07-2018 07:33 PM
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
RE: (12C) Check if given number is Fibonacci number - stored - 09-08-2018 06:48 PM
Hello, Albert!
Your remarks is correct and very useful.
Thanks you.
RE: (12C) Check if given number is Fibonacci number - Albert Chan - 09-09-2018 12:14 AM
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.