views:

1154

answers:

13

I know how to make the list of the Fibonacci numbers, but i don't know how can i test if a given number belongs to the fibonacci list - one way that comes in mind is generate the list of fib. numbers up to that number and see if it belongs to the array, but there's got to be another, simpler and faster method.

Any ideas ?

+24  A: 

A positive integer ω is a Fibonacci number if and only if one of 5ω2 + 4 and 5ω2 - 4 is a perfect square.

See The Faboulous Fibonacci Numbers for more.

alt text

JRL
+1 for the book recommendation.
Thomas Matthews
+27  A: 

A very nice test is that N is a Fibonacci number if and only if 5 N^2 + 4 or 5N^2 – 4 is a square number. For ideas on how to efficiently test that a number is square refer to the SO discussion.

Hope this helps

Il-Bhima
+1 because saying "or" is more clear than saying "one of" + "and" First 4 times I read the other answers I thought they were saying different things because I didn't see the "one of" part
Davy8
I am skeptical of this solution, as it involves squaring a Fibonacci number. Fibonacci numbers grow extremely quickly, and most are very large. Doesn't squaring them become computationally expensive?
abelenky
Well yeah, beyond 2^63 (something like Fib(300)) you're going to have to use some arbitrary precision arithmetic which will be expensive. As the numbers grow, you must resort to approximate methods, either using Binet's formula or something else. I would be surprised to learn any efficient exact method that works for large numbers!
Il-Bhima
Hm... If exactly one of the propositions A and B need to hold (but not both!), you cannot write "A or B", for this compound statement is true if A is true and B is false, if A is false and B is true, and if both A and B are true. Then you need to write explicitly "exactly one of", or use the logical "xor" operator rather than "or".
Andreas Rejbrand
But it appears to be the case that "or" is indeed the correct operator. To see this, set N = 1. Then N is a Fibonacci number, and *both* 5*N^2 + 4 and 5*N^2 - 4 are perfect squares. If we had a xor operator, then "A xor B" would be false, even though 1 is Fibonacci, and we have a contradiction. (Here I assume that the theorem is correct with "or" or "xor".)
Andreas Rejbrand
So I agree with Davy8: Saying like Wikipedia that "... a positive integer z is a Fibonacci number if and only if *one of* 5z^2 + 4 or 5z^2 − 4 is a perfect square." is actually incorrect. For the positive integer z=1, both numbers are perfect squares, i.e. two of them, and hence not one of them, so, the by the equivalence, 1 cannot be a Fibonacci number. But it is, and we have a contradiction.
Andreas Rejbrand
+6  A: 

Positive integer ω is a Fibonacci number

If and only if one of2 + 4 and 5ω2 - 4 is a perfect square

from The (Fabulous) FIBONACCI Numbers by Alfred Posamentier and Ingmar Lehmann

bool isFibonacci(int  w)
{
       double X1 = 5 * Math.Pow(w, 2) + 4;
       double X2 = 5 * Math.Pow(w, 2) - 4;

       long X1_sqrt = (long)Math.Sqrt(X1);
       long X2_sqrt = (long)Math.Sqrt(X2);   

       return (X1_sqrt*X1_sqrt == X1) || (X2_sqrt*X2_sqrt == X2) ;
}

I copied it from this source


Snippet that prints Fibonacci numbers between 1k and 10k.

for (int i = 1000; i < 10000; i++)
{
         if (isFibonacci(i))
              Console.Write(" "+i);
}

OMG There are only FOUR!!!

With other method

from math import *

phi = 1.61803399
sqrt5 = sqrt(5)

def F(n):
    return int((phi**n - (1-phi)**n) /sqrt5)

def isFibonacci(z):
    return F(int(floor(log(sqrt5*z,phi)+0.5))) == z

print [i for i in range(1000,10000) if isFibonacci(i)]
TheMachineCharmer
No need for the "? true : false" part: the expression before that is already a boolean value.
lhf
+1 :) See I changed it. Thanks!
TheMachineCharmer
I wrote second method in python because I didn't know C# Math.Log works for other bases as well. Do you guys want me to write it too :P?? lol
TheMachineCharmer
+5  A: 

Since Fibonacci numbers grow exponentially, the method you suggest is pretty fast. Another is this.

lhf
+1 for a different method.
TheMachineCharmer
I really like the closed interval solution, should be much easier than checking for squares!
Matthieu M.
+7  A: 

If your numbers are of bounded size, than simply putting all fibonacci numbers below the upper bound into a hashtable and testing containment will do the trick. There are very few fibonacci numbers (for example, only 38 below 5mln), since they grow exponentially.

If your numbers are not of bounded size, then the suggested trick with square testing will almost surely be slower than generating the fibonacci sequence until the number is found or exceeded.

jkff
A: 

How big are the numbers you're dealing with?

Could a lookup table work for you? (a precomputed list of numbers you can search in)

There's also a closed-form expression that I guess you could invert to get at the answer analytically (though I'm no mathematician, so I can't promise this suggestion makes sense)

Assaf Lavie
I'm dealing with arbitrary numbers. Even an approximation will be useful, if it runs very quickly.
blueberryfields
I think psmears has the solution: http://stackoverflow.com/questions/2821778/im-looking-for-an-efficient-algorithm-to-test-whether-a-given-number-is-part-of/2821832#2821832
Assaf Lavie
+7  A: 

Towards a solution, take a look at Binet's Formula.
(Look for "Closed-Form Expression" under Fibonacci Number on Wikipedia)

It says that the sequence of Fibonacci Number's is created by a simple closed formula:

alt text

I believe if you solve for n, and test if n is an integer, you'll have your answer.

Edit As @psmears points out, the same Wikipedia article also has a section on detecting Fibonacci numbers. Wikipedia is an excellent source.

abelenky
+8  A: 

See the section "Recognizing Fibonacci numbers" on the wikipedia article about the Fibonacci numbers.

psmears
Hey, are you P Smears who was at Lincoln?
Steve Jessop
A: 

From Wikipedia: http://en.wikipedia.org/wiki/Fibonacci_number

A positive integer z is a Fibonacci number if and only if one of 5z^2 + 4 or 5z^2 − 4 is a perfect square.

Mark Lavin
+7  A: 
#!/bin/bash
victim="144"
curl http://aux.planetmath.org/files/objects/7680/fib.txt | sed 's/^[0-9]*//;s/[ \t]//g' | grep "^$victim$" >/dev/null 2>/dev/null
if [[ $? -eq 0 ]] ; then
    echo "$victim is a fibonacci number"
else
    echo "$victim aint"
fi
Shin
+1  A: 

Based on earlier answers by me and psmears, I've written this C# code.

It goes through the steps slowly, and it can clearly be reduced and optimized:

// Input: T: number to test.
// Output: idx: index of the number in the Fibonacci sequence.
//    eg: idx for 8 is 6. (0, 1, 1, 2, 3, 5, 8)
// Return value: True if Fibonacci, False otherwise.
static bool IsFib(long T, out int idx)
{
    double root5 = Math.Sqrt(5);
    double PSI = (1 + root5) / 2;

    // For reference, IsFib(72723460248141) should show it is the 68th Fibonacci number

    double a;

    a = T*root5;
    a = Math.Log(a) / Math.Log(PSI);
    a += 0.5;
    a = Math.Floor(a);
    idx = (Int32)a;

    long u = (long)Math.Floor(Math.Pow(PSI, a)/root5 + 0.5);

    if (u == T)
    {
        return true;
    }
    else
    {
        idx = 0;
        return false;
    }
}

Testing reveals this works for the first 69 Fibonacci numbers, but breaks down for the 70th.

F(69) = 117,669,030,460,994 - Works
F(70) = 190,392,490,709,135 - Fails

In all, unless you're using a BigInt library of some kind, it is probably better to have a simple lookup table of the Fibonacci Numbers and check that, rather than run an algorithm.

A list of the first 300 Numbers is readily available online.

But this code does outline a workable algorithm, provided you have enough precision, and don't overflow your number representation system.

abelenky
The problem with phi is that it's not exactly usable using floating point numbers, and so you have to approximate.
Rubys
+2  A: 

While several people point out the perfect-square solution, it involves squaring a Fibonacci number, frequently resulting in a massive product.

There are less than 80 Fibonacci numbers that can even be held in a standard 64-bit integer.

Here is my solution, which operates entirely smaller than the number to be tested.
(written in C#, using basic types like double and long. But the algorithm should work fine for bigger types.)

static bool IsFib(long T, out long idx)
{
    double root5 = Math.Sqrt(5);
    double phi = (1 + root5) / 2;

    idx    = (long)Math.Floor( Math.Log(T*root5) / Math.Log(phi) + 0.5 );
    long u = (long)Math.Floor( Math.Pow(phi, idx)/root5 + 0.5);

    return (u == T);
}
abelenky
+1 for taking machine limitations into account
dss539
+1  A: 

I ran some benchmarks on the methods presented here along with simple addition, pre-computing an array, and memoizing the results in a hash. For Perl, at least, the squaring method is a little bit faster than the logarithmic method, perhaps 20% faster. As abelenky points out, it's a tradeoff between whether you've got the room for squaring bit numbers.

Certainly, the very fastest way is to hash all the Fibonacci numbers in your domain space. Along the lines of another point that abelenky makes, there are only 94 of these suckers that are less than 2^64.

You should just pre-compute them, and put them in a Perl hash, Python dictionary, or whatever.

The properties of Fibonacci numbers are very interesting, but using them to determine whether some integer in a computer program is one is kind of like writing a subroutine to compute pi every time the program starts.

David M