459,403 Members | 1,374 Online Need help? Post your question and get tips & solutions from a community of 459,403 IT Pros & Developers. It's quick & easy.

# Unsigned Long Long Overflow

 P: n/a This program was compiled on MS Visual C++ 08 /*Fibonacci Numbers*/ #include #include void fibonacci(int n) { unsigned long long fib0 = 0; /*First Fibonacci Number*/ unsigned long long fib1 = 1; /*Second Fibonacci Number*/ unsigned long long fibn = 1; /*Nth Fibonacci Number*/ int count = 3; /*Hold Count*/ printf(" 1 :%25llu \n 2 :%25lld \n",fib0,fib1); while(count <= n ) { fibn = fib0 + fib1 ; if((fibn < 0) || (fibn ULLONG_MAX)){ puts("\nOverflow\n"); break; } printf("%3d :%25llu \n",count,fibn); fib0 = fib1; fib1 = fibn; count++; } return ; } int main(void) { unsigned long temp = 0; puts("Fibonacci Numbers"); fibonacci(100); /*Print the first 100 Fibonacci Numbers*/ return 0; } This is a part of the output : Fibonacci Numbers ...snip... 90 : 1779979416004714189 91 : 2880067194370816120 92 : 4660046610375530309 93 : 7540113804746346429 94 : 12200160415121876738 95 : 1293530146158671551 96 : 13493690561280548289 97 : 14787220707439219840 98 : 9834167195010216513 99 : 6174643828739884737 100 : 16008811023750101250 Why are the numbers after 95th Fibonacci numbers (including it) wrong? Feb 8 '08 #1
17 Replies

 P: n/a Tarique wrote: ) ) unsigned long long fibn = 1; /*Nth Fibonacci Number*/ ) ) if((fibn < 0) || (fibn ULLONG_MAX)){ This can never happen. Some compilers would even warn about an if condition never being true, or about unreachable code, or something similar. ) puts("\nOverflow\n"); ) SaSW, Willem -- Disclaimer: I am in no way responsible for any of the statements made in the above text. For all I know I might be drugged or something.. No I'm not paranoid. You all think I'm paranoid, don't you ! #EOT Feb 8 '08 #2

 P: n/a Tarique wrote: This program was compiled on MS Visual C++ 08 /*Fibonacci Numbers*/ #include #include void fibonacci(int n) { unsigned long long fib0 = 0; /*First Fibonacci Number*/ unsigned long long fib1 = 1; /*Second Fibonacci Number*/ unsigned long long fibn = 1; /*Nth Fibonacci Number*/ int count = 3; /*Hold Count*/ printf(" 1 :%25llu \n 2 :%25lld \n",fib0,fib1); Why do you treat fib1 as long long when it is declared as unsigned long long? while(count <= n ) { fibn = fib0 + fib1 ; if((fibn < 0) || (fibn ULLONG_MAX)){ puts("\nOverflow\n"); break; } How can 'fibn' be less than zero when it is an unsigned type? Also how can it be greater than ULLONG_MAX? One method would be: if (ULLONG_MAX - fib1 < fib0) { puts("Overflow."); break; } printf("%3d :%25llu \n",count,fibn); Why the precision specifiers? fib0 = fib1; fib1 = fibn; count++; } return ; } int main(void) { unsigned long temp = 0; puts("Fibonacci Numbers"); fibonacci(100); /*Print the first 100 Fibonacci Numbers*/ return 0; } This is a part of the output : Fibonacci Numbers ...snip... 90 : 1779979416004714189 91 : 2880067194370816120 92 : 4660046610375530309 93 : 7540113804746346429 94 : 12200160415121876738 95 : 1293530146158671551 96 : 13493690561280548289 97 : 14787220707439219840 98 : 9834167195010216513 99 : 6174643828739884737 100 : 16008811023750101250 Why are the numbers after 95th Fibonacci numbers (including it) wrong? Are you sure about the output? Feb 8 '08 #3

 P: n/a "Tarique" #include void fibonacci(int n) { unsigned long long fib0 = 0; /*First Fibonacci Number*/ unsigned long long fib1 = 1; /*Second Fibonacci Number*/ unsigned long long fibn = 1; /*Nth Fibonacci Number*/ int count = 3; /*Hold Count*/ printf(" 1 :%25llu \n 2 :%25lld \n",fib0,fib1); while(count <= n ) { fibn = fib0 + fib1 ; if((fibn < 0) || (fibn ULLONG_MAX)){ Here you need if(fibn < fib0 || fibn < fib1) unsigned numbers wrap silently. You need a huge integer library to calculate high Fibonacci numbers effectively. -- Free games and programming goodies. http://www.personal.leeds.ac.uk/~bgy1mm Feb 8 '08 #4

 P: n/a Tarique wrote: This program was compiled on MS Visual C++ 08 /*Fibonacci Numbers*/ #include #include void fibonacci(int n) { unsigned long long fib0 = 0; /*First Fibonacci Number*/ unsigned long long fib1 = 1; /*Second Fibonacci Number*/ unsigned long long fibn = 1; /*Nth Fibonacci Number*/ int count = 3; /*Hold Count*/ printf(" 1 :%25llu \n 2 :%25lld \n",fib0,fib1); while(count <= n ) { fibn = fib0 + fib1 ; if((fibn < 0) || (fibn ULLONG_MAX)){ puts("\nOverflow\n"); break; } printf("%3d :%25llu \n",count,fibn); fib0 = fib1; fib1 = fibn; count++; } return ; } int main(void) { unsigned long temp = 0; puts("Fibonacci Numbers"); fibonacci(100); /*Print the first 100 Fibonacci Numbers*/ return 0; } This is a part of the output : Fibonacci Numbers ...snip... 90 : 1779979416004714189 91 : 2880067194370816120 92 : 4660046610375530309 93 : 7540113804746346429 94 : 12200160415121876738 95 : 1293530146158671551 96 : 13493690561280548289 97 : 14787220707439219840 98 : 9834167195010216513 99 : 6174643828739884737 100 : 16008811023750101250 Why are the numbers after 95th Fibonacci numbers (including it) wrong? Try this modification: #include #include void fibonacci(int n) { unsigned long long fib0 = 0; /*First Fibonacci Number*/ unsigned long long fib1 = 1; /*Second Fibonacci Number*/ unsigned long long fibn = 1; /*Nth Fibonacci Number*/ int count = 3; /*Hold Count*/ printf(" 1 :%25llu \n 2 :%25llu \n",fib0,fib1); while(count <= n ) { fibn = fib0 + fib1 ; /* if((fibn < 0) || (fibn ULLONG_MAX)){ puts("\nOverflow\n"); break; } */ if (ULLONG_MAX - fib1 < fib0) { puts("Overflow!"); break; } printf("%3d :%25llu \n",count,fibn); fib0 = fib1; fib1 = fibn; count++; } return ; } int main(void) { unsigned long temp = 0; puts("Fibonacci Numbers"); fibonacci(100); /*Print the first 100 Fibonacci Numbers*/ return 0; } Relavant output is: 88 : 679891637638612258 89 : 1100087778366101931 90 : 1779979416004714189 91 : 2880067194370816120 92 : 4660046610375530309 93 : 7540113804746346429 94 : 12200160415121876738 Overflow! Feb 8 '08 #5

 P: n/a santosh wrote: Tarique wrote: >This program was compiled on MS Visual C++ 08/*Fibonacci Numbers*/#include#includevoid fibonacci(int n){unsigned long long fib0 = 0; /*First Fibonacci Number*/unsigned long long fib1 = 1; /*Second Fibonacci Number*/unsigned long long fibn = 1; /*Nth Fibonacci Number*/int count = 3; /*Hold Count*/printf(" 1 :%25llu \n 2 :%25lld \n",fib0,fib1); Why do you treat fib1 as long long when it is declared as unsigned long long? Overlooked that..changed it >while(count <= n ){fibn = fib0 + fib1 ;if((fibn < 0) || (fibn ULLONG_MAX)){puts("\nOverflow\n");break;} How can 'fibn' be less than zero when it is an unsigned type? Also how can it be greater than ULLONG_MAX? Initially i was using a long long integer,but then changed it to unsigned int. Did not remove the fibn < 0 check. Since i was getting -ve numbers as output(some of them..which was obviously due to overflow),it seemed to be at least a temporary fix! > One method would be: if (ULLONG_MAX - fib1 < fib0) { puts("Overflow."); break; } >printf("%3d :%25llu \n",count,fibn); Why the precision specifiers? It's a little easier to actually add any two numbers in the output when they are right aligned! > >fib0 = fib1;fib1 = fibn;count++;}return ;} int main(void){unsigned long temp = 0;puts("Fibonacci Numbers");fibonacci(100); /*Print the first 100 Fibonacci Numbers*/return 0;}This is a part of the output :Fibonacci Numbers ...snip... 90 : 1779979416004714189 91 : 2880067194370816120 92 : 4660046610375530309 93 : 7540113804746346429 94 : 12200160415121876738 95 : 1293530146158671551 96 : 13493690561280548289 97 : 14787220707439219840 98 : 9834167195010216513 99 : 6174643828739884737100 : 16008811023750101250Why are the numbers after 95th Fibonacci numbers (including it) wrong? Are you sure about the output? Well yes.I did check the numbers prior to 90,the smaller ones are easier to check...did some random checks with larger numbers. The 95th one is obviously wrong! It is smaller than the 94th one. Feb 8 '08 #6

 P: n/a Willem wrote: Tarique wrote: ) ) unsigned long long fibn = 1; /*Nth Fibonacci Number*/ ) ) if((fibn < 0) || (fibn ULLONG_MAX)){ This can never happen. Some compilers would even warn about an if condition never being true, or about unreachable code, or something similar. Yes. The compiler did not warn.Lint did! Feb 8 '08 #7

 P: n/a Tarique wrote: santosh wrote: >Tarique wrote: >>This program was compiled on MS Visual C++ 08/*Fibonacci Numbers*/#include#includevoid fibonacci(int n){unsigned long long fib0 = 0; /*First Fibonacci Number*/unsigned long long fib1 = 1; /*Second Fibonacci Number*/unsigned long long fibn = 1; /*Nth Fibonacci Number*/int count = 3; /*Hold Count*/printf(" 1 :%25llu \n 2 :%25lld \n",fib0,fib1); Why do you treat fib1 as long long when it is declared as unsignedlong long? Overlooked that..changed it >>while(count <= n ){fibn = fib0 + fib1 ;if((fibn < 0) || (fibn ULLONG_MAX)){puts("\nOverflow\n");break;} How can 'fibn' be less than zero when it is an unsigned type? Alsohow can it be greater than ULLONG_MAX? Initially i was using a long long integer,but then changed it to unsigned int. Did not remove the fibn < 0 check. Since i was getting -ve numbers as output(some of them..which was obviously due to overflow),it seemed to be at least a temporary fix! Unsigned numbers cannot overflow in C. As for signed values, you must check for possible overflow /before/ the suspect calculation. Once overflow has occured the behaviour of your program is undefined. Some compilers have an option to enable overflow detection. This might be easier than doing so manually before every calculation. Feb 8 '08 #8

 P: n/a Umm..I am combining two questions together. These were the suggestions : 1. if(fibn < fib0 || fibn < fib1) from Mr.Malcolm McLean 2. if (ULLONG_MAX - fib1 < fib0) from Santosh Can you please explain the logic ? Feb 8 '08 #9

 P: n/a "Tarique"

 P: n/a Tarique wrote: ) Umm..I am combining two questions together. ) ) These were the suggestions : ) 1. if(fibn < fib0 || fibn < fib1) from Mr.Malcolm McLean Actually, if(fibn < fib0) is enough. If overflow occurs, then fibn will be like this: fibn = (fib0 + fib1) - (ULLONG_MAX + 1) You can algebraically rewrite this to: fibn = fib0 - (ULLONG_MAX+1 - fib1) Knowing that fib1 is smaller than ULLONG_MAX+1, you can deduce that if overflow occurs, fibn < fib0. Same holds for fibn < fib1, symmetrically. ) 2. if (ULLONG_MAX - fib1 < fib0) from Santosh You really want to check: if ((fib0 + fib1) ULLONG_MAX) But that will not work because of overflow. If you rewrite it algebraically, you get the above comparison. (Move fib1 to the right of the comparator.) SaSW, Willem -- Disclaimer: I am in no way responsible for any of the statements made in the above text. For all I know I might be drugged or something.. No I'm not paranoid. You all think I'm paranoid, don't you ! #EOT Feb 8 '08 #11

 P: n/a Tarique wrote: Umm..I am combining two questions together. These were the suggestions : 1. if(fibn < fib0 || fibn < fib1) from Mr.Malcolm McLean 2. if (ULLONG_MAX - fib1 < fib0) from Santosh Can you please explain the logic ? In addition to Malcolm's and Willem's explanations also note that method one is used after the concerned calculation while method 2 can be used before. But this doesn't matter for unsigned calculations. Feb 8 '08 #12

 P: n/a santosh wrote: Tarique wrote: >Umm..I am combining two questions together.These were the suggestions :1. if(fibn < fib0 || fibn < fib1) from Mr.Malcolm McLean2. if (ULLONG_MAX - fib1 < fib0) from SantoshCan you please explain the logic ? In addition to Malcolm's and Willem's explanations also note that method one is used after the concerned calculation while method 2 can be used before. But this doesn't matter for unsigned calculations. Thank You everyone. Feb 8 '08 #13

 P: n/a "Tarique"

 P: n/a Bartc said: > "Tarique" This program was compiled on MS Visual C++ 08/*Fibonacci Numbers*/ >Why are the numbers after 95th Fibonacci numbers (including it) wrong? Apparently the C standard says that unsigned arithmetic does not overflow, therefore the problem in your code is nothing to do with overflow. Right. It is, instead, to do with the OP's apparent belief that standard integer types are infinitely wide. Even though the problem in your code clearly *is* to do with overflowing the range of your datatype. No, unsigned integer arithmetic doesn't overflow, any more than a clock overflows at midnight. > In this case, I think you can test for overflow by making the sure each successive fibonacci number is the previous number. If you are particularly interesting in calculating big fibonaccis, try using double datatype. These will be approximate. Or use, or even write and then use, a bignum library. -- Richard Heathfield Email: -http://www. +rjh@ Google users: "Usenet is a strange place" - dmr 29 July 1999 Feb 8 '08 #15

 P: n/a Richard Heathfield wrote: Bartc said: >"Tarique" >This program was compiled on MS Visual C++ 08/*Fibonacci Numbers*/Why are the numbers after 95th Fibonacci numbers (including it) wrong? Apparently the C standard says that unsigned arithmetic does notoverflow, therefore the problem in your code is nothing to do withoverflow. It is, instead, to do with the OP's apparent belief that standard integer types are infinitely wide. I would like to differ here. If i believed that standard integer types are infinitely wide,i would not have bothered to at least try to check if bounds were transgressed. The problem was that I was using (signed) long long integer instead,as I have mentioned earlier in the thread.When i changed that to unsigned type,i should have changed the *failure* condition. >Even though the problem in your code clearly *is* to do withoverflowing the range of your datatype. No, unsigned integer arithmetic doesn't overflow, any more than a clock overflows at midnight. I definitely learned it today! Feb 8 '08 #16

 P: n/a Tarique wrote: [...] unsigned long long fib0 = 0; /*First Fibonacci Number*/ unsigned long long fib1 = 1; /*Second Fibonacci Number*/ unsigned long long fibn = 1; /*Nth Fibonacci Number*/ while(count <= n ) { fibn = fib0 + fib1 ; if((fibn < 0) || (fibn ULLONG_MAX)){ puts("\nOverflow\n"); break; } Why are the numbers after 95th Fibonacci numbers (including it) wrong? [...] Because you test for overflow after the overflow has occured. Note that fibn is unsigned so (fibn < 0) can never be true, and fibn is an unsigned long long so (fibn ULLONG_MAX) can never be true, so your test amounts to if (0) { /* dead code */ } Consider how your test differs from this while(count <= n ) { if(fib1 ULLONG_MAX - fib0) { puts("\nOverflow\n"); break; } fibn = fib0 + fib1 ; where fib0 must be less than or equal to ULLONG_MAX (since it is an unsigned long long), so ULLONG_MAX - fib0 always has a defined value for which the test against fib1 makes sense. Remember that fib1 ULLONG_MAX - fib0 (which can be true) and fib1 + fib0 ULLONG_MAX (which can never be true) do not mean the same thing. Feb 8 '08 #17

 P: n/a On Feb 8, 3:48*pm, "Malcolm McLean"

### This discussion thread is closed

Replies have been disabled for this discussion. 