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