Pagina's

2011/08/10

Faster inverse Fibonacci

A simple test to see if a number X is not a Fibonacci number.
Even Fibonacci numbers end binary with 000 or 010

The "proof" starts with F0=000 and F1=001
F2=F1+F0, F3=F2+F1, etc.

 F0  000------<----
 F1  001--<--      |
 F2  001     |     |
 F3  010     |     |
 F4  011     |     |
 F5  101     |     |
 F6  000     |     |
 F7  101     |     |
 F8  101     |     |
 F9  010     |     |
 F10 111     |     |
 F11 001-->--      |
 F12 000------>----

After 11 additions we're back at the starting point.
Even numbers end with 000 or 010 or 100 or 110
So 50% of the even numbers will be recognized as not
Fibonacci numbers. 50% Of the numbers are even.
So 25% will be recognized as not Fibonacci numbers,
just looking at the 3 least significant bits.

Let's look at the 5 least significant bits,
again a pattern can be found,
and a formula:
if (((X & 1)) == 0) && ((X & 7) != 0) && (((X - 2) & 31) != 0))
then X is not a Fibonacci number.
11 Of 32 numbers are excluded, that's 34.375%.
The average computing time decreases by about one third.

I tried to look at more than 5 least significant bits,
sorry, to hard for me today. I expect it's possible to exclude
nearly 3 of 8 numbers, an optimum close to 37.5%.
Is there a trick for odd Numbers? Stay tuned!

Another improvement for small X values <= Fib(46)(= 1836311093),
the largest integer Fibonacci number:

switch ((int)X))
{
    case 0: return 0;
    case 2: return 3;
    case 3: return 4;
    case 5: return 5;
    case 8: return 6;
    case 13: return 7;
//  ..................
//  ......................
//  ...........................
    case 1134903170: return 45;
    case 1836311093: return 46;
    default: return -1;
}

It's more than two times faster.
Isn't it a waste to hard-code all those Fibonacci numbers?
Isn't it a waste to use an array of Fibonacci numbers,
int[] fibSmall = { 0, 1 , 1, 2, 3, 5,....}
It's sufficient to use:
int[] fibSmall = { 0, 1 }
The code length is nothing compared to the magnitude of the
numbers computed. I will go for the fast way.

No comments:

Post a Comment