lundi 20 avril 2015

(n*2-1)%p: avoiding the use of 64 bits when n and p are 32 bits

Consider the following function:

inline unsigned int f(unsigned int n, unsigned int p) 
{
    return (n*2-1)%p;
}

Now suppose that n (and p) are greater than std::numeric_limits<int>::max().

For example f(4294967295U, 4294967291U).

The mathematical result is 7 but the function will return 2, because n*2 will overflow.

Then the solution is simple: we just have to use 64 bits integer instead. Assuming that the declaration of the function has to stay the same:

inline unsigned int f(unsigned int n, unsigned int p) 
{
    return (static_cast<unsigned long long int>(n)*2-1)%p;
}

Everything is fine. At least in principle. The problem is that this function will be called millions of times in my code, and 64 bits modulus is way slower than the 32 bits version (see here for example).

The question is the following: is there any trick (mathematical or algorithmic) to avoid to execute a 64 bits version of the modulus operation. And what would be a new version of f using this trick? (keeping the same declaration).

Note: the less the number of modulo operation used, the better

Aucun commentaire:

Enregistrer un commentaire