Velocity Reviews > Unsigned Long Long Overflow

# Unsigned Long Long Overflow

Willem
Guest
Posts: n/a

 02-08-2008
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
Guest
Posts: n/a

 02-08-2008
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
Guest
Posts: n/a

 02-08-2008
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
Guest
Posts: n/a

 02-08-2008

"Tarique" <(E-Mail Removed)> wrote in message news:fohsr9\$von\$(E-Mail Removed)...
> 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

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
Guest
Posts: n/a

 02-08-2008
Bartc said:

>
> "Tarique" <(E-Mail Removed)> wrote in message
> news:fohsr9\$von\$(E-Mail Removed)...
>> 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@
"Usenet is a strange place" - dmr 29 July 1999

Tarique
Guest
Posts: n/a

 02-08-2008
Richard Heathfield wrote:
> Bartc said:
>
>> "Tarique" <(E-Mail Removed)> wrote in message
>> news:fohsr9\$von\$(E-Mail Removed)...
>>> 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.

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

Martin Ambuhl
Guest
Posts: n/a

 02-08-2008
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,
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.

Bartc
Guest
Posts: n/a

 02-08-2008

"Richard Heathfield" <(E-Mail Removed)> wrote in message
news(E-Mail Removed)...
> Bartc said:

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

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.

--
Bart

christian.bau
Guest
Posts: n/a

 02-10-2008
On Feb 8, 3:48*pm, "Malcolm McLean" <(E-Mail Removed)> wrote:

> Here you need if(fibn < fib0 || fibn < fib1)
>
> unsigned numbers wrap silently.

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.