0

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?

Improve this question
21
  • What is the range of inputs for n? Commented Mar 23, 2022 at 15:32
  • You may be interested in Binet's formula, which doesn't require iterations to compute Fibonacci numbers. Commented Mar 23, 2022 at 15:36
  • 4
    There are only 46 Fibonacci numbers between -2147483647 -1 and 2147483647 (give or take, allowing for off-by-one error). I suggest a lookup table :) Commented Mar 23, 2022 at 15:42
  • 1
    It's easier to just iterate and check if the number if a Fibonacci number or not, since they're very few in quantity in the given range (as highlighted by @pmg) Commented Mar 23, 2022 at 15:44
  • 2
    @devec, void main() is not the same as int main(). The former is wrong, and the latter is right. int main(void) would be even more right, or else int main(int argc, char *argv[]). These two and their semantic equivalents are the only signatures that a strictly conforming C program for a hosted environment may use. Commented Mar 23, 2022 at 15:59

2 Answers 2

Reset to default
3

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

17 Comments

Unfortunately sqrt is going to return a double which only has 53 bits of precision, so you still have a problem. The binary search suggestion is solid though.
@Mark Ransom, I know. That's why I said to use sqrtl instead of sqrt
I don't see that suggestion in the answer anywhere.
No, it would work. Adding.
On refection, perhaps long long s = llroundl( sqrtl( x ) ); return s * s == x; would be best.
|
1

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
Improve this answer

6 Comments

why size_t n=48?
devec, n could have been char, unsigned short, long long or any sort of integer type as only a small range is needed here. size_t is the not-too-narrow, not-too-wide type for array indexing and sizing in all cases. It should be the default type to use for that unless you have compelling requirements otherwise.
Sorry, it should be 47. The original code populated 1..46 (wrong), and searched 0..45 (also wrong). That means it relied on undefined behaviour, and it wasn't finding 1,134,903,170 or 1,836,311,903 as a fibonacci. It should populate and search 0..46. And this is done by using n=47. This is a bug in my fix. Fixed.
My test, btw. Note the correct use of int64_t instead of int (which could be as small as 16 bit, and is only 32 bit on the test platform).
No, there are 47 of them (not counting the negative ones).
|