Subject: Re: [boost] [xint] Boost.XInt formal review
From: John Bytheway (jbytheway+boost_at_[hidden])
Date: 2011-03-14 19:39:43
On 14/03/11 22:22, Thomas Klimpel wrote:
> My current workaround for
>
> k = modulo(m,n);
>
> in places where I'm unable to work around the missing "modulo"
> functionality of C/C++ is to write
>
> k = ((m%n)+n)%n
Be careful; not only does that perform two divisions (which is slow), it
also gives the wrong answer when m and n are big enough.
> Based on the information from Kim Barrett,
>
> k = m >= 0 ? m%n : (m%n) + n;
>
> should also work (that's a bit longer than the old form, but looks
> more efficient, and I could write a "modulo" template encapsulating
> this functionality for my personal use). If I'm not mistaken, this
> would be the most efficient workaround in case of XInt.
I tend to use
r = m%n;
if (r < 0) r += n;
which the compiler is more likely to implement using a conditional move,
rather than a branch (but it does have the issue that it's not an
expression).
I did some tests with:
int m1(int m, int n)
{
return ((m%n)+n)%n;
}
int m2(int m, int n)
{
return m >= 0 ? m%n : (m%n) + n;
}
int m3(int m, int n)
{
int r = m%n;
if (r < 0) r += n;
return r;
}
icc 11.1 compiles m2 and m3 to essentially the same code. gcc 4.5.2's
version of m2 is longer than m3 and contains a branch (-O3 in all
cases). For both compilers m1 contains two divisions (there's no way to
optimize it down to one).
John Bytheway