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