Test if a number is fibonacci

2018-07-01 01:09:47

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 ?

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

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.

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);
}

More than 4 years after I wrote this answer, a commenter asked about the second parameter, passed by out .

Parameter #2 is the "Index" into the Fibonacci sequence.
If the value to be tested, T is a Fibonacci number, then idx will be the 1-based index of that number in the Fibonacci sequence. (with one notable exception)

The Fibonacci sequence is 1 1 2 3 5 8 13 , etc.
3 is the 4th number in the sequence: IsFib(3, out idx); will return true and value 4 .
8 is the 6th number in the sequence: IsFib(8, out idx); will return true and value 6 .
13 is the 7th number; IsFib(13, out idx); will return true and value 7 .

The one exception is IsFib(1, out idx); , which will return 2 , even though the value 1 appears at both index 1 and 2.

If IsFib is passed a non-Fibonacci number, it will return false , and the value of idx will be the index of the biggest Fibonacci number less than T .

16 is not a Fibonacci value.
IsFib(16, out idx); will return false and value 7 .
You can use Binet's Formula to convert index 7 into Fibonacci value 13, which is the largest number less than 16.

链接地址: http://www.djcxy.com/p/86596.html

上一篇: 我怎么能检查一个数字是一个完美的广场？

下一篇: 测试一个数字是否是斐波那契