# Unsigned Long Long Overflow

Discussion in 'C Programming' started by Tarique, Feb 8, 2008.

1. ### TariqueGuest

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?

Tarique, Feb 8, 2008

2. ### WillemGuest

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

Willem, Feb 8, 2008

3. ### santoshGuest

Why do you treat fib1 as long long when it is declared as unsigned long
long?
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; }
Why the precision specifiers?
Are you sure about the output?

santosh, Feb 8, 2008
4. ### Malcolm McLeanGuest

Here you need if(fibn < fib0 || fibn < fib1)

unsigned numbers wrap silently.

You need a huge integer library to calculate high Fibonacci numbers
effectively.

Malcolm McLean, Feb 8, 2008
5. ### santoshGuest

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!

santosh, Feb 8, 2008
6. ### TariqueGuest

Overlooked that..changed it
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!
It's a little easier to actually add any two numbers in the output when
they are right aligned!
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, 2008
7. ### TariqueGuest

Yes. The compiler did not warn.Lint did!

Tarique, Feb 8, 2008
8. ### santoshGuest

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

santosh, Feb 8, 2008
9. ### TariqueGuest

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 ?

Tarique, Feb 8, 2008
10. ### Malcolm McLeanGuest

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.

Malcolm McLean, Feb 8, 2008
11. ### WillemGuest

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

Willem, Feb 8, 2008
12. ### santoshGuest

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.

santosh, Feb 8, 2008
13. ### TariqueGuest

Thank You everyone.

Tarique, Feb 8, 2008
14. ### BartcGuest

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

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.

Bartc, Feb 8, 2008
15. ### Richard HeathfieldGuest

Bartc said:
Right. It is, instead, to do with the OP's apparent belief that standard
integer types are infinitely wide.
No, unsigned integer arithmetic doesn't overflow, any more than a clock
overflows at midnight.
Or use, or even write and then use, a bignum library.

Richard Heathfield, Feb 8, 2008
16. ### TariqueGuest

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.
I definitely learned it today!

Tarique, Feb 8, 2008
17. ### Martin AmbuhlGuest

Tarique wrote:
[...]
[...]
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,
if (0)
{
}

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.

Martin Ambuhl, Feb 8, 2008
18. ### BartcGuest

The overflow/wraparound thing has been discussed here before. Clearly I
think that 'overflow' is a more appropriate term for this behaviour than
'wraparound', but the C standard dictates otherwise.

But, when I add 2 unsigned ints on my machine, in assembler, sometimes the
Carry flag gets set. OK, that's not in the province of C, but to me it says
'Overflow'. It's a piece of useful information ignored by C (possibly, why
overflow itself is ignored).

The clock would have the same problems, if you're trying to measure time and
it doesn't have a day counter.

There are many examples in everyday life of counters that 'wrap' yet it
would be unwise to ignore the obvious overflow that has occurred: electric
meters apparently showing a large negative kWh consumption, decrepit cars
with just 35 miles/km on the odometer, etc.

Bartc, Feb 8, 2008
19. ### christian.bauGuest

Actually, if you want to check an addition c = a + b for wrapping, you
only need to check _either_ (c < a) _or_ (c < b). You don't need to
check both. If one is true then the other must be true.

christian.bau, Feb 10, 2008