Check if given number is fibonacci in C-CodePudding

How to check if a given number is a Fibonacci number?

#include <math.h>
#include <stdio.h>
int isPerfectSquare(int x) {
  int s = sqrt(x);
  return (s * s == x);
}
int isFibonacci(int n) {
  return isPerfectSquare(5 * n * n   4) || isPerfectSquare(5 * n * n - 4);
}

void main() {
  isFibonacci(4) ? printf("%d yes\n", 4) : printf("%d no\n", 4);
  isFibonacci(-35) ? printf("%d yes\n", -35) : printf("%d no\n", -35);
  isFibonacci(9227465) ? printf("%d yes\n", 9227465): printf("%d no\n", 9227465);
}

OUTPUT:

4 no
-35 no
9227465 no

online tool for checking fibonacci

This algorithm doesn't work for longer integer numbers? How to fix it to work for all possible integer numbers(range between -2147483647 -1 and 2147483647?

CodePudding user response：

First of all, the implementation you have does work for negative numbers. It only fails for large numbers.

To work with inputs in the inclusive range [-2,147,483,648, 2,147,483,647], you need to accommodate numbers as large as 5 * -2,147,483,648 * -2,147,483,648 4. This requires 65 bit of precision as a floating point number. This is quite large, and would probably involve specialized libraries.

However, the largest fibonacci number in this range is 1,836,311,903. So if we check if |n| ≤ 1,836,311,903, we only need 64 bits of precision. A long double on an x86 would be large enough if it's implemented as x86's extended precision format, so switching to using long double instead of double could work.

int isPerfectSquare( int64_t x ) {
   int64_t r = llroundl( sqrtl( x ) );
   return r * r == x;
}

int isFibonacci( int32_t x ) {
   if ( x > 1836311903 || x < -1836311903 )
      return 0;

   int64_t t = ((int64_t)5) * x * x;
   if ( isPerfectSquare( t   4 ) )
      return 1;
   if ( isPerfectSquare( t - 4 ) )
      return 1;

   return 0;
}

The use llroundl was added to compensate for deviations in the results of sqrtl.

That's the math approach. The CS approach is to build a table of all 47 fibonacci numbers from 0 to 1,836,311,903, a perform a binary search on them.

CodePudding user response：

Here's one approach:

Create array of Fibonacci numbers, and check for every number if it belongs to array:

#include <stdio.h>
int is_fibonacci(int arr[], size_t n, int num) {
  for (size_t i = 0; i < n; i  )
    if (arr[i] == num || arr[i] == -num)
      return 1;
  return 0;
}
int main() {
  size_t n = 47;
  int n1 = 0, n2 = 1, nextTerm, arr[47];
  for (size_t i = 0; i < n; i  ) {
    arr[i] = n1;
    nextTerm = n1   n2;
    n1 = n2;
    n2 = nextTerm;
  }
  is_fibonacci(arr, n, 4) ? printf("%d yes\n", 4): printf("%d no\n", 4);
  is_fibonacci(arr, n, -5) ? printf("%d yes\n", -5): printf("%d no\n", -5);
  is_fibonacci(arr, n, -123456789) ? printf("%d yes\n", -123456789): printf("%d no\n", -123456789);
  is_fibonacci(arr, n, 9227465) ? printf("%d yes\n", 9227465): printf("%d no\n", 9227465);
  return 0;
}

OUTPUT:

4 no
-5 yes
-123456789 no
9227465 yes