Boost logo

Boost :

From: Moore, Paul (paul.moore_at_[hidden])
Date: 2001-07-05 03:35:27

Helmut Zeisel wrote:
> I tested gcd from rational.hpp with my big_int class.
> As a good citizen of the C++ community
> I think, however, that it is not really necessary
> to provide a swap function for the special case
> of gcd, since the swap is undone in every other step.
> Two steps per loop make the swap unnecessary.
> I tried to use a slightly different version for gcd:
> template<typename IntType>
> IntType gcd_alternative(IntType n, IntType m)
> {
> IntType zero(0);
> if (n < zero)
> n = -n;
> if (m < zero)
> m = -m;
> for(;;)
> {
> if(m == zero) return n;
> n %= m;
> if(n == zero) return m;
> m %= n;
> }
> }
> For my specific big_int,
> I get a performance gain of 15-20%.
> How do you like this alternative version?

Clever! I like this a lot. It's a nice simple loop-unrolling optimisation,
which avoids some of the nasty areas around std::swap.

Can someone with CVS access add this for me? (With an appropriate comment
crediting Helmut).


PS: The version of rational.hpp linked on the website (*not* the one in the
download zip, just the one referenced from is seriously out of date.
Looks like the web site version hasn't been updated from the zip file.

Boost list run by bdawes at, gregod at, cpdaniel at, john at