Re: Generating Modulo and Remainder Operations

[Andrew Haley <aph at redhat dot com>]

David Carter-Hitchin wrote:
> Hello John,
> 
>> The % operator is well-defined for unsigned integer numbers.  
> 
> This is news to me, but I've never used C/C++ for any kind of modular
> arithmetic which would involve negatives. I shall have to be wary if I do
> :-)
> 
>> It is
>> platform dependent when dealing with negatively signed integer numbers.
> 
> Yikes, that sucks.

The depends on whether you have C90 or C99.

>> Rather depends on if you want Knuth modulus, or Euclidean modulus.
> 
> Never heard of Knuth modulus, but there again I don't know Knuth's
> works/ideas much beyond the TeX Book.  Also, presumably by Euclidean modulus
> you mean the Gaussian modulus, such as a = b (mod c) is equivalent to the
> statement that c|(a-b) (where = is equivalent [i.e. three equal marks] and |
> means 'divides without remainder').

You want x = a mod b.  Any multiple of b added to a does not change x.
Assuming a is of type int and b is a positive integer,

    unsigned long long A = a + ((long long) b << wordsize);
    x = A % b;

This can be optimized to a couple of instructions on some machines.

Andrew.