[Bug other/60843] Documentation: 4.5 Integers/C99 6.3.1.3 ("reduce modulo 2^N")

[kdevel at vogtner dot de]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=60843

--- Comment #2 from Stefan <kdevel at vogtner dot de> ---
(In reply to joseph@codesourcery.com from comment #1)
> > Reduce A modulo M usually means find the least integer R in the range [0, M -
> > 1] such that A is congruent R modulo M. But this is not what gcc compiled
> 
> I don't see the problem.

The problem is the erroneous wording "reduction modulo 2^N". *Reduction* by
definition results in the least *nonnegative* number out of the list of
congruent numbers, cf. http://www.youtube.com/watch?v=SO6l6sDwEFg&t=5m50s

What gcc does is not reduction.

> It explicitly says "reduced modulo 2^N to be 
> within range of the type", and that unambiguously defines the result 
> value, as there is exactly one result within the range of the type that is 
> equal to the input, modulo 2^N.

The reduction of 2147483649 modulo 2^32 is unambigously 2147483649. Therefore
by reduction one does not get a number which is within the range of int.
"Reduce A modulo M" is definitionally complete. Adjoining "to be within range
of type" does not change or extend its meaning it only clarifies the intent.

> The qualifier "to be within range of the 
> type" says that [0, M - 1] is irrelevant, because that isn't the range of 
> the type in question.

If you remove the "least nonnegative" part from the definition of reduction you
no longer have a reduction modulo 2^N but something else, e.g. subtraction.

> This is the normal form of modulo arithmetic for signed types, as used for 
> example by -fwrapv (and defined in detail in the first (1994) edition of 
> LIA-1; the second (2012) edition removes the modulo operations, but the 
> underlying wrap_I operation is in LIA-2).

Thanks for these references. AFAICS neither ISO/IEC 10967-1:1994(E) nor
:2012(E) provide a definition of the notion of reduction modulo some number.
They do not use the notion either. ISO/IEC 10967-1:1994(E) defines conversion
between distint integer types in § 5.3 by means of a function wrap_I which is
defined in § 5.1.2 as (if x not in I):

    wrap_I: Z -> I
    wrap_I(x) = x + j * (maxint - minint + 1) for some j in Z
    wrap_I(x) in I

In ISO/IEC 10967-2:2001 wrap_I is defined in § 5.1.1 as (if x not in I):

    wrap_I: Z -> I
    wrap_I(x) = x - (n · (maxint_I - minint_I + 1)) where n in Z  is chosen
        such that the result is in I

This wrapper function does not reduce modulo 2^N and it is not named
"reduction".