Integer overflow

[Beliavsky]

Playing with integers, I am surprised that even when i**2 overflows, the compiler may still give 2*i-1 for i**2-(i-1)**2, as this program shows.

program main
implicit none
integer, parameter :: imin = huge(1)/10, imax = huge(imin)-1
integer :: i,j,k,jk
logical, parameter :: print_all = .false.
print "(*(a18))","i","2*i-1","(i**2)-(i-1)**2","j=i**2","k=(i-1)**2","j-k"
do i=imin,imax
j = i**2
k = (i-1)**2
jk = j - k
if (print_all .or. i==imin .or. i==imax) &
print "(*(1x,i17))",i,2*i-1,i**2 - (i-1)**2,j,k,jk
if (jk /= (2*i-1)) stop "here"
end do
end program main

output:
i 2*i-1 (i**2)-(i-1)**2 j=i**2 k=(i-1)**2 j-k
214748364 429496727 429496727 687194768 257698041 429496727
2147483646 -5 -5 4 9 -5

[gah4]

Most hardware now gives the low bits of the full two's complement product.

If they both overflow the same amount, when you subtract then you get
the result that you would get without overflow.

You could put an IF in the loop, and compare them, but I suspect you are right.

Note that in the second case, both are overflowing.

The products give the low 32 bits as two's complement values.
When you subtract, you get the low 32 bits of the difference.
(In both cases, half the time they will have the wrong sign, though.)

It is slightly more interesting on ones' complement hardware.

[Robin Vowels]

Use Silverfrost FTN95.
The object program stops when integer overflow occurs.

[Robin Vowels]

On Friday, April 15, 2022 at 7:50:38 AM UTC+10, gah4 wrote:
> On Thursday, April 14, 2022 at 9:34:54 AM UTC-7, Beliavsky wrote:
> > Playing with integers, I am surprised that even when i**2 overflows, the compiler may still give 2*i-1 for i**2-(i-1)**2, as this program shows.
> >
> > program main
> > implicit none
> > integer, parameter :: imin = huge(1)/10, imax = huge(imin)-1
> > integer :: i,j,k,jk
> > logical, parameter :: print_all = .false.
> > print "(*(a18))","i","2*i-1","(i**2)-(i-1)**2","j=i**2","k=(i-1)**2","j-k"
> > do i=imin,imax
> > j = i**2
> > k = (i-1)**2
> > jk = j - k
> > if (print_all .or. i==imin .or. i==imax) &
> > print "(*(1x,i17))",i,2*i-1,i**2 - (i-1)**2,j,k,jk
> > if (jk /= (2*i-1)) stop "here"
> > end do
> > end program main
> >
> > output:
> > i 2*i-1 (i**2)-(i-1)**2 j=i**2 k=(i-1)**2 j-k
> > 214748364 429496727 429496727 687194768 257698041 429496727
> > 2147483646 -5 -5 4 9 -5

.

> Most hardware now gives the low bits of the full two's complement product.

.
The product is positive (see the initial values).
The low-order bits are not 2's complement. They are the
the truncated low-order bits of the positive product.

>
> If they both overflow the same amount, when you subtract then you get
> the result that you would get without overflow.
>
> You could put an IF in the loop, and compare them, but I suspect you are right.
>
> Note that in the second case, both are overflowing.
>
> The products give the low 32 bits as two's complement values.

No they aren't. The product s positive, and he gets the
truncated low-order bits. (see above)

[gah4]

On Friday, April 15, 2022 at 7:09:56 AM UTC-7, Robin Vowels wrote:

(snip)

> > Most hardware now gives the low bits of the full two's complement product.

> The product is positive (see the initial values).
> The low-order bits are not 2's complement. They are the
> the truncated low-order bits of the positive product.

Read carefully:

Most hardware now gives the low bits of the full two's complement product.

That is, (the low bits of) (the full two's complement product).

That is, multiply them and generate a double length two's complement
product, then return the low bits. And yes often enough they have
a different sign, about half the time.

Maybe I should say it again:

[Robin Vowels]

On Saturday, April 16, 2022 at 11:01:59 AM UTC+10, gah4 wrote:
> On Friday, April 15, 2022 at 7:09:56 AM UTC-7, Robin Vowels wrote:
>
> (snip)
> > > Most hardware now gives the low bits of the full two's complement product.
> > The product is positive (see the initial values).
> > The low-order bits are not 2's complement. They are the
> > the truncated low-order bits of the positive product.
> Read carefully:

.

> Most hardware now gives the low bits of the full two's complement product.
> That is, (the low bits of) (the full two's complement product).

.
You still don't get it.
See the initial values.
The products are ALWAYS positive.
The products are NOT twos complement.
The products are ALWAYS positive.

.
> That is, multiply them and generate a double length two's complement
> product,

.
They are NOT twos complement products.
The products are ALWAYS positive.
.
It is only negative values that are represented in twos complement form.
.

> then return the low bits. And yes often enough they have
> a different sign, about half the time.

.
Because the high bits are removed, what remains are the truncated
low-order bits.
The most significant bit of that can be 0 or 1.
If it is 1, the value appears to be negative.

.
> Maybe I should say it again:
> Most hardware now gives the low bits of the full two's complement product.

.
See above.

[gah4]

On Friday, April 15, 2022 at 7:39:02 PM UTC-7, Robin Vowels wrote:


> They are NOT twos complement products.
> The products are ALWAYS positive.

Two's complement is the representation used on most machines now.

It can represent both negative and positive values. It is still called
two's complement even when the values are positive.

> It is only negative values that are represented in twos complement form.

The "two's complement" operation is used to change the sign of
a value that is represented in two's complement, but no, it is not only
negative values. They are negative when the sign bit is set, and
positive or zero when it isn't.

And, just to be sure, Unisys last I knew still sold some ones' complement
machines. There are complications with C on such machines, as
unsigned arithmetic doesn't do what it is supposed to do. And ones'
complement machines can also represent negative, positive,
and zero values.

[Robin Vowels]

On Saturday, April 16, 2022 at 1:18:40 PM UTC+10, gah4 wrote:
> On Friday, April 15, 2022 at 7:39:02 PM UTC-7, Robin Vowels wrote:
>
>

> > They are NOT twos complement products. [when an integer is squared]

> > The products are ALWAYS positive.
.
> Two's complement is the representation used on most machines now.
>
> It can represent both negative and positive values. It is still called
> two's complement even when the values are positive.

.
You are mistaken. It is only negative values that are represented

in twos complement form.
.
> > It is only negative values that are represented in twos complement form.
.
> The "two's complement" operation is used to change the sign of
> a value that is represented in two's complement,

.
You are still mistaken. A twos complement operation is used to
negate a value. When the argument represents a positive integer,
the operation produces the negative form. When the argument
represents a negative integer, the operation produces a positive integer
(with one exception).
.
However, it is only negative values that are held in two's complement form.
.
It might surprise you to know that when values are summed
(be they negative, positive, or zero), the adder merely forms
the sum by adding corresponding bits and adding to that any carry
from a lower-order bit, and forwarding any carry to the next-higher bit.
.

> but no, it is not only
> negative values. They are negative when the sign bit is set, and
> positive or zero when it isn't.

.
There is no sign bit. All bits are data bits.

[Ron Shepard]

On 4/17/22 8:21 AM, Robin Vowels wrote:
> On Saturday, April 16, 2022 at 1:18:40 PM UTC+10, gah4 wrote:
>> On Friday, April 15, 2022 at 7:39:02 PM UTC-7, Robin Vowels wrote:
>>
>>
>>> They are NOT twos complement products. [when an integer is squared]
>>> The products are ALWAYS positive.
> .
>> Two's complement is the representation used on most machines now.
>>
>> It can represent both negative and positive values. It is still called
>> two's complement even when the values are positive.
> .
> You are mistaken. It is only negative values that are represented
> in twos complement form.

Here is the wikipedia article about twos-complement arithmetic.

https://en.wikipedia.org/wiki/Two%27s_complement

As you can see there, the term "twos-complement" can be regarded both as
an operation applied to a string of bits and also as the name of the
storage representation used for integers.

For this discussion, the important feature of twos-complement arithmetic
(i.e. the storage representation) is that the bits that result from
integer operations for the signed twos-complement values are the same as
would result from treating those bits as an unsigned integer and
ignoring any overflow of the high-order bit. Thus the "twos-complement
operation" never appears explicitly in the addition and multiplication
integer operations, the correct result just happens naturally.

Another interesting way to view the twos-complement representation
(which is discussed in that wiki article) is that the integer value of
an unsigned integer is simply the result of the polynomial evaluation

Sum(i=0:N-1) b(i) * 2**(i)

over all the bits. The twos-complement value for those same bits is the
same expression, except the high-order bit term is replaced by
-b(N-1)*2**N. I learned this long ago from one of Hamming's books, and
over the years, that expression has clarified a lot of algorithms for me.

This then brings up the lack of an unsigned integer type in fortran. If
all hardware supported two-complement arithmetic, then I think it would
be straightforward to allow this type into the language. Compilers would
need to do little to support the type and its semantics. But those
computers that use different integer representations (e.g.
ones-complement and signed-magnitude), the twos-complement results would
need to be simulated, and that could be expensive and slow. I'm not
familiar with the current C standard, but in the past the C language
punted on this issue by defining results for unsigned arithmetic only
when there is no overflow (i.e. when the high-order bit can be ignored).
If a C compiler happens to give correct results also when there is
overflow (i.e. when the high-order bit comes into play), then that is
great, but it was not required by the language. Fortran could have taken
that same approach, but it didn't.

This issue also arises in the discussions over the decades for fortran
to support an intrinsic bit data type. When those bits are moved between
the bit data type and integer variables, then the meaning of the
high-order bit, or the sign bit, must be accounted for correctly, making
portable code difficult to write.

$.02 -Ron Shepard

[gah4]

On Sunday, April 17, 2022 at 11:08:22 AM UTC-7, Ron Shepard wrote:

(snip)

> This then brings up the lack of an unsigned integer type in fortran. If
> all hardware supported two-complement arithmetic, then I think it would
> be straightforward to allow this type into the language. Compilers would
> need to do little to support the type and its semantics. But those
> computers that use different integer representations (e.g.
> ones-complement and signed-magnitude), the twos-complement results would
> need to be simulated, and that could be expensive and slow. I'm not
> familiar with the current C standard, but in the past the C language
> punted on this issue by defining results for unsigned arithmetic only
> when there is no overflow (i.e. when the high-order bit can be ignored).
> If a C compiler happens to give correct results also when there is
> overflow (i.e. when the high-order bit comes into play), then that is
> great, but it was not required by the language. Fortran could have taken
> that same approach, but it didn't.

C allows for two's complement, ones' complement, or sign magnitude
for signed integers, but only one representation for unsigned.

Last I knew, Unisys was still selling ones' complement hardware, along
with a C compiler. The C compiler has funny rules for its unsigned,
because of what the hardware does.

> This issue also arises in the discussions over the decades for fortran
> to support an intrinsic bit data type. When those bits are moved between
> the bit data type and integer variables, then the meaning of the
> high-order bit, or the sign bit, must be accounted for correctly, making
> portable code difficult to write.

Well, Fortran, according to the standard, allows any integer radix
greater than one. It isn't obviously what it should do for bitwise
operators other than for radix two.