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 did not use BOOST_RATIONAL_USE_STD_SWAP.
>
> 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).
Thanks,
Paul.
PS: The version of rational.hpp linked on the website (*not* the one in the
download zip, just the one referenced from
http://www.boost.org/libs/rational/index.html) is seriously out of date.
Looks like the web site version hasn't been updated from the zip file.