RE: rational, gcd, big_int

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.