Re: [boost] [xint] Boost.XInt formal review

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