Velocity Reviews > Unsigned Long Long Overflow

# Unsigned Long Long Overflow

Tarique
Guest
Posts: n/a

 02-08-2008
This program was compiled on MS Visual C++ 08

/*Fibonacci Numbers*/

#include<stdio.h>
#include<limits.h>

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?

Willem
Guest
Posts: n/a

 02-08-2008
Tarique wrote:
) <snip>
) unsigned long long fibn = 1; /*Nth Fibonacci Number*/
) <snip>
) 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");
) <snip>

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

santosh
Guest
Posts: n/a

 02-08-2008
Tarique wrote:

> This program was compiled on MS Visual C++ 08
>
> /*Fibonacci Numbers*/
>
> #include<stdio.h>
> #include<limits.h>
>
> 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?

Malcolm McLean
Guest
Posts: n/a

 02-08-2008

"Tarique" <(E-Mail Removed)> wrote in message
> This program was compiled on MS Visual C++ 08
>
> /*Fibonacci Numbers*/
>
> #include<stdio.h>
> #include<limits.h>
>
> 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

santosh
Guest
Posts: n/a

 02-08-2008
Tarique wrote:

> This program was compiled on MS Visual C++ 08
>
> /*Fibonacci Numbers*/
>
> #include<stdio.h>
> #include<limits.h>
>
> 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<stdio.h>
#include<limits.h>

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!

Tarique
Guest
Posts: n/a

 02-08-2008
santosh wrote:
> Tarique wrote:
>
>> This program was compiled on MS Visual C++ 08
>>
>> /*Fibonacci Numbers*/
>>
>> #include<stdio.h>
>> #include<limits.h>
>>
>> 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?

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 : 6174643828739884737
>> 100 : 16008811023750101250
>>
>> Why 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.

Tarique
Guest
Posts: n/a

 02-08-2008
Willem wrote:
> Tarique wrote:
> ) <snip>
> ) unsigned long long fibn = 1; /*Nth Fibonacci Number*/
> ) <snip>
> ) 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!

santosh
Guest
Posts: n/a

 02-08-2008
Tarique wrote:

> santosh wrote:
>> Tarique wrote:
>>
>>> This program was compiled on MS Visual C++ 08
>>>
>>> /*Fibonacci Numbers*/
>>>
>>> #include<stdio.h>
>>> #include<limits.h>
>>>
>>> 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?

>
> 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!

<snip>

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.

Tarique
Guest
Posts: n/a

 02-08-2008
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 ?

Malcolm McLean
Guest
Posts: n/a

 02-08-2008

"Tarique" <(E-Mail Removed)> wrote in message news:fohun9\$74c\$(E-Mail Removed)...
> 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 ?
>

fibn is set to fib0 + fib1. So if fibn is less than either, some overflow
must have occurred. If greater than either, there cannot be overflow. This
holds true for any two positive integers represented by a fixed number of
bits.

Santosh is saying effectively the same thing. The overflow occurs if fib1 +
fib0 > ULLONG_MAX. However we cannot sum fib0 and fib1, because that in
itself woyuld give overflow. So he rearranges the equation.

--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm