Re: [boost] Fixed width integers

From: Jens Maurer (Jens.Maurer_at_[hidden])
Date: 2001-04-03 13:19:04

nbecker_at_[hidden] wrote:

> Maybe I misunderstand - I think if width == bits(int), then it's not
> possible for there to be any overflow on assignment or construction,
> so there is no issue.

May I quote from your original mail on this issue:

>>> In working on DSP, I often need to use integer types of particular bit
>>> widths.  Although I have seen some other attempts to develop C++
>>> classes for this purpose, they usually are not what I am looking for.

>>> In order to simulate the effects of finite-width integers, all that is
>>> really needed is:
>>> 1) Check during construction and assignment
>>> 2) Conversion back to int.
>>> This of course assumes the bit width is less than or equal to the
>>> natural size of int.

I believe that your solution (sketched above) to providing those
finite-width integers is lacking.  However, that belief may also
be due to my failing to understand your definition of "finite-width
integer".  With the lack of accompanying documentation with the header
file, this is difficult to decide.

You do seem to provide a "saturation" and "wrap-around" policy classes.
Let's focus on the "saturation" policy for the moment.  Assuming I've
got an n-bit unsigned integer, saturation means that any operation
whose result overflows these n bit means that the maximum representable
value will be assumed as the result instead.  For example, if I have
4 bit integers (0000-0111 binary for positive numbers), multiplying
100 (bin) by 100 (bin) results in 10000 (bin), which saturates to the
maximum representable 0111 (bin).

Now, let us consider your implementation.  Assume (for the sake of
easy exposition) that my native "int" is (also) 4 bits wide. I choose
the "saturation" policy, with 4 bit wide "finite-width" integers.  With
your implementation, I believe the following happens for 100 * 100 (all
numbers in binary representation):
 - Both multiplicands are converted from Int<4> to int.
 - The multiplication is carried out in 4bit "int" mode.
0100 * 0100 = 10000 overflows in the basic C arithmetic (4 bit integers),
thus 0100 * 0100 = 0000 (here we're already in "undefined behaviour"
country, but let's continue).   Now the saturation check tries to
find out whether 0000 > 0111, which it obviously isn't.  Thus, the
result of 0100 * 0100 = 000 with your Int<4> implementation.

(For "real" bit widths, use Int<28> with a 32-bit native "int"
and multiply 2**16 by 2**16.)

This result is not what I would expect given my definition of
saturation above.   Please provide a definition of "saturation"
(or, more precisely, "finite-width integer") that is useful and
is matched by your implementation.

> I use this for very computationally intensive applications, such as
> Monte-Carlo simulation, where efficiency is of primary importance.

Efficiency is useless if the implementation doesn't comply with the
specification and/or the specification is unclear.  Probably I should
wait for your documentation before discussing further.

Jens Maurer