unsigned __int64 overflow problem

V

Vivi

I am trying to find an elegant solution for the "unsigned __int64
overflow problem" or in general an "unsigned int overflow detection
problem". In particular, I just have written a little program that
calculates "aliquot sequences" using unsigned __int64. That gives me
integers up to 19 digits and that's all I need for now, but the
sequences often grow fast beyond the _UI64_MAX (maximum value of
__int64) and in that case, the __int64 variables assume incorrect
values (pretty much, garbage).

I was wondering if there is an elegant way, not crucially affecting
the calculation speed, of detecting if an unsigned __int64 (or any
other unsigned int) variable "got over the limit".

Thanks, Vivi
 
J

Jack Klein

I am trying to find an elegant solution for the "unsigned __int64
overflow problem" or in general an "unsigned int overflow detection
problem". In particular, I just have written a little program that
calculates "aliquot sequences" using unsigned __int64. That gives me
integers up to 19 digits and that's all I need for now, but the
sequences often grow fast beyond the _UI64_MAX (maximum value of
__int64) and in that case, the __int64 variables assume incorrect
values (pretty much, garbage).

I was wondering if there is an elegant way, not crucially affecting
the calculation speed, of detecting if an unsigned __int64 (or any
other unsigned int) variable "got over the limit".

Thanks, Vivi

Note that __int64 is not a standard C++ data type. It is an
acceptable representation for the C "long long" type which will
probably be added to the next version of the C++ standard, but for now
it is not a part of the language.

If/when "long long" is added to the C++ language, the unsigned version
will have exactly the same behavior as all of the other C and C++
unsigned types. Specifically, they can't overflow. If a calculation
or conversion produces a value outside the range of the unsigned type,
it is modified by repeatedly adding or subtracting one mare than the
type's maximum value until it is within range. This required behavior
is well-defined and guaranteed.

Essentially, that means you get the low 64 bits of the result, any
carry to higher bits is merely discarded.

As to whether or not you can detect this after the fact, you can do
this fairly easily for addition and subtraction for the unsigned
types:

Given any unsigned integer type UIT:

UIT u1, u2;

/* some values assigned to u1 and u2 */

/* want to add u2 to u1 unless it will overflow */
if (u1 + u2 < u1)
{
/* will overflow, do something */
}
else
{
/* won't overflow, OK to continue */
u1 += u2;
}

Likewise for subtraction:

if (u1 - u2 > u1)
{
/* would underflow */
}
else
{
u1 -= u2;
}

Off the top of my head, I think you must pre-test for division, using
UIT_MAX from <climits>:

if (UIT_MAX / u2 < u1)
{
/* u1 * u2 will wrap */
}
else
{
u1 *= u2;
}

As to how long that takes, and whether or not it crucially affects the
calculation speed, only you can determine that.

--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.learn.c-c++ ftp://snurse-l.org/pub/acllc-c++/faq
 
E

ES Kim

Vivi said:
I am trying to find an elegant solution for the "unsigned __int64
overflow problem" or in general an "unsigned int overflow detection
problem". In particular, I just have written a little program that
calculates "aliquot sequences" using unsigned __int64. That gives me
integers up to 19 digits and that's all I need for now, but the
sequences often grow fast beyond the _UI64_MAX (maximum value of
__int64) and in that case, the __int64 variables assume incorrect
values (pretty much, garbage).

I was wondering if there is an elegant way, not crucially affecting
the calculation speed, of detecting if an unsigned __int64 (or any
other unsigned int) variable "got over the limit".

Thanks, Vivi

A natural way would be to check if it overfloww before
you actually carry out the operation.
If you are concerned about only in unsigned integers,

1. addition
Check if a + b > _UI64_MAX, ie, a > _UI64_MAX - b
If so, it's overflow.

2. subtraction
Check if the second operand is greater than the first.

3. multiplication
Check if a * b > _UI64_MAX, ie, a > _UI64_MAX / b
If so, it's overflow. Oh, you must check if b is 0 first.

4. division
Nothing to worry about if the second operand is not 0.

Is this elegant and effecient? Well... it's upon you.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,731
Messages
2,569,432
Members
44,832
Latest member
GlennSmall

Latest Threads

Top