• Integer overflow

    From Beliavsky@21:1/5 to All on Thu Apr 14 09:34:51 2022
    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

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From gah4@21:1/5 to Beliavsky on Thu Apr 14 14:50:36 2022
    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.

    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.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Robin Vowels@21:1/5 to Beliavsky on Fri Apr 15 07:04:09 2022
    On Friday, April 15, 2022 at 2:34:54 AM UTC+10, 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

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

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Robin Vowels@21:1/5 to All on Fri Apr 15 07:09:53 2022
    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)

    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.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From gah4@21:1/5 to Robin Vowels on Fri Apr 15 18:01:57 2022
    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:

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

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Robin Vowels@21:1/5 to All on Fri Apr 15 19:39:00 2022
    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.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From gah4@21:1/5 to Robin Vowels on Fri Apr 15 20:18:38 2022
    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.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Robin Vowels@21:1/5 to All on Sun Apr 17 06:21:46 2022
    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.
    .
    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.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Ron Shepard@21:1/5 to Robin Vowels on Sun Apr 17 13:08:18 2022
    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

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From gah4@21:1/5 to Ron Shepard on Sun Apr 17 11:40:38 2022
    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.

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)