Unsigned Long Long Overflow

**Willem** · Feb 8 '08, 03:45 PM

Re: Unsigned Long Long Overflow

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("\nOverflo w\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** · Feb 8 '08, 03:55 PM

Re: Unsigned Long Long Overflow

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("\nOverflo w\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 : 177997941600471 4189
91 : 288006719437081 6120
92 : 466004661037553 0309
93 : 754011380474634 6429
94 : 122001604151218 76738
95 : 129353014615867 1551
96 : 134936905612805 48289
97 : 147872207074392 19840
98 : 983416719501021 6513
99 : 617464382873988 4737
100 : 160088110237501 01250
>
Why are the numbers after 95th Fibonacci numbers (including it) wrong?

Are you sure about the output?

**Malcolm McLean** · Feb 8 '08, 03:55 PM

Re: Unsigned Long Long Overflow

"Tarique" <peo_leo@yahoo. comwrote 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** · Feb 8 '08, 03:55 PM

Re: Unsigned Long Long Overflow

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("\nOverflo w\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 : 177997941600471 4189
91 : 288006719437081 6120
92 : 466004661037553 0309
93 : 754011380474634 6429
94 : 122001604151218 76738
95 : 129353014615867 1551
96 : 134936905612805 48289
97 : 147872207074392 19840
98 : 983416719501021 6513
99 : 617464382873988 4737
100 : 160088110237501 01250
>
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("\nOverflo w\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 : 679891637638612 258
89 : 110008777836610 1931
90 : 177997941600471 4189
91 : 288006719437081 6120
92 : 466004661037553 0309
93 : 754011380474634 6429
94 : 122001604151218 76738
Overflow!

**Tarique** · Feb 8 '08, 04:05 PM

Re: Unsigned Long Long Overflow

santosh wrote:

Tarique wrote:
>

>This program was compiled on MS Visual C++ 08
>>
>/*Fibonacci Numbers*/
>>
>#include<stdio .h>
>#include<limit s.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("\nOverfl ow\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("Fibonacc i Numbers");
>fibonacci(100) ; /*Print the first 100 Fibonacci Numbers*/
>>
>return 0;
>}
>>
>This is a part of the output :
>Fibonacci Numbers
>>
> ...snip...
>>
> 90 : 177997941600471 4189
> 91 : 288006719437081 6120
> 92 : 466004661037553 0309
> 93 : 754011380474634 6429
> 94 : 122001604151218 76738
> 95 : 129353014615867 1551
> 96 : 134936905612805 48289
> 97 : 147872207074392 19840
> 98 : 983416719501021 6513
> 99 : 617464382873988 4737
>100 : 160088110237501 01250
>>
>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** · Feb 8 '08, 04:05 PM

Re: Unsigned Long Long Overflow

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** · Feb 8 '08, 04:15 PM

Re: Unsigned Long Long Overflow

Tarique wrote:

santosh wrote:

>Tarique wrote:
>>

>>This program was compiled on MS Visual C++ 08
>>>
>>/*Fibonacci Numbers*/
>>>
>>#include<stdi o.h>
>>#include<limi ts.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("\nOverf low\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** · Feb 8 '08, 04:15 PM

Re: Unsigned Long Long Overflow

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** · Feb 8 '08, 04:25 PM

Re: Unsigned Long Long Overflow

"Tarique" <peo_leo@yahoo. comwrote in message news:fohun9$74c $1@aioe.org...

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

**Willem** · Feb 8 '08, 04:35 PM

Re: Unsigned Long Long Overflow

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

**santosh** · Feb 8 '08, 04:55 PM

Re: Unsigned Long Long Overflow

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.

**Tarique** · Feb 8 '08, 05:15 PM

Re: Unsigned Long Long Overflow

santosh wrote:

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

Thank You everyone.

**Bartc** · Feb 8 '08, 05:55 PM

Re: Unsigned Long Long Overflow

"Tarique" <peo_leo@yahoo. comwrote in message news:fohsr9$von $1@aioe.org...

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. Even
though the problem in your code clearly *is* to do with overflowing the
range of your datatype.

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.

--
Bart

**Richard Heathfield** · Feb 8 '08, 06:25 PM

Re: Unsigned Long Long Overflow

Bartc said:

>
"Tarique" <peo_leo@yahoo. comwrote in message
news:fohsr9$von $1@aioe.org...

>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 <http://www.cpax.org.uk >
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

Unsigned Long Long Overflow

Unsigned Long Long Overflow

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment

Comment