implementing integer overflow when calculating large Fibonacci numbers in C
I'm trying to implement a function in C that calculates Fibonacci numbers up to the 50th term. However, when I run my code, I notice that the results become incorrect for indices greater than 46. I suspect it's due to integer overflow, but I want to confirm this and find a solution. Here’s the code I have: ```c #include <stdio.h> unsigned long long fibonacci(int n) { if (n <= 1) return n; return fibonacci(n - 1) + fibonacci(n - 2); } int main() { for (int i = 0; i <= 50; i++) { printf("Fibonacci(%d) = %llu\n", i, fibonacci(i)); } return 0; } ``` When I run this, I get correct results for Fibonacci(0) to Fibonacci(46), but Fibonacci(47) outputs `2971215073` instead of the expected `2971215073`. I’m using GCC version 9.3.0 on Ubuntu 20.04. I’ve tried changing the return type to `unsigned long long`, but it still doesn’t help. Is there a better way to calculate Fibonacci numbers in C that avoids this overflow scenario? Would using an iterative approach help, or is there a more efficient method? Also, would using a larger data type (like `__int128`) be more beneficial in this case? Any suggestions on how to properly handle this would be greatly appreciated. This is part of a larger API I'm building. I'd really appreciate any guidance on this.