I am a c
newbie, and start learning it by learning algorithm at the same time. However, I encountered some problem when writing this algorithm --- the number overflows, which is quite different to the overflow I thought. To solve the problem, I searched for a long time, but end up in no use. Here is my code:
#include <iostream>
using namespace std;
long long Fs[101];
long long F(int N) {
if (Fs[N] != -1) {
return Fs[N];
}
int res = F(N - 1) F(N - 2);
Fs[N] = res;
return res;
}
void main() {
// initialize Fs array
for (auto& item : Fs) {
item = -1;
}
Fs[0] = 0;
Fs[1] = 1;
cout << F(60) << endl;
cout << endl;
for (auto& item : Fs) {
cout << item << endl;
}
}
Part of the result is shown here:
165580141
267914296
433494437
701408733
1134903170
1836311903
-1323752223
512559680
-811192543
Question:
You can see that the overflow number is quite small than the minimum value of long long
type. Why this happened?
Appendix
I found some way to print the overflow index of unsigned type when generating fibonacci
, here is the code:
#include <iostream>
#include <limits>
using namespace std;
#define outFibonacci(nType) { int i = 1;\
while (i )\
if (Fibonacci<nType>(i 1)==Fibonacci<nType>(i 2)){\
cout<<"F("<<i<<")\t= "<<Fibonacci<nType>(i)<<endl;\
break;\
}\
cout<< "Max Num\t= " << numeric_limits<nType>::max() << endl << endl;\
}
template<typename _T> _T Fibonacci(_T n){
_T f, f1, f2;
f = f1 = f2 = 1;
for (auto i=3; i<=n; i){
f = f1 f2;
if (f<f2){ // Set overflow condition
f=-1;
break;
}
f1 = f2;
f2 = f;
}
return f;
}
int main(void)
{
outFibonacci(unsigned short);
outFibonacci(unsigned int);
outFibonacci(unsigned long);
outFibonacci(unsigned long long);
outFibonacci(size_t);
return 0;
}
and here is my result:
F(24) = 46368
Max Num = 65535
F(47) = 2971215073
Max Num = 4294967295
F(47) = 2971215073
Max Num = 4294967295
F(93) = 12200160415121876738
Max Num = 18446744073709551615
F(93) = 12200160415121876738
Max Num = 18446744073709551615
CodePudding user response:
This line in your function int res = F(N - 1) F(N - 2); makes your result an int, which is then casted to long long. so the overflow occurs here. Should be flagged by some compilers flags tho.
long long F(int N) {
if (Fs[N] != -1) {
return Fs[N];
}
// int res = F(N - 1) F(N - 2); // HERE !
long long res = F(N - 1) F(N - 2);
Fs[N] = res;
return res;
}