Re: [Boost-users] Valid arguments for boost::math::gcd()

From: Matthias Hofmann (hofmann_at_[hidden])
Date: 2006-07-20 18:28:28

<james.jones_at_[hidden]> schrieb im Newsbeitrag
news:A1B722A7A7710742976C7693E2EE8E9E38F0DF_at_rockfalls...
> From: "Matthias Hofmann" <hofmann_at_[hidden]>
> > Also, I would like to know how the greatest common divisor is defined
when
> > one or both of the arguments are zero. In that case, boost::math::gcd()
> > seems to return the nonzero argument, if there is any - but is this
> > mathematically correct?
>
> Yes, it's correct. gcd(a,b) is the greatest integer n such that n|a and
n|b. Every integer n has the property that n|0, so gcd(a,0) = a.

I see, thank you for the quick response. I also found out that it does not
matter which of the two arguments passed to boost::math::gcd() is the
greater one. Some texts require a > b for the euclidean algorithm to work,
but this does not seem to be true for boost's implementation:

while ( true )
{
    if ( a == zero )
        return b;
    b %= a;

    if ( b == zero )
        return a;
    a %= b;
}

It also plays no role in my own implementation:

int gcd( int a, int b )
{
    while ( b != 0 )
    {
        int r = a % b;
        a = b;
        b = r;
    }

    return std::abs( a );
}

However, it does matter in the following implementation, see the
corresponding comment:

int gcd( int a, int b )
{
    // This is crucial!
    if ( b > a )
        std::swap( a, b );

    while ( b != 0 )
    {
        int t = b;
        b = a - b;
        a = t;

        if ( b > a )
            std::swap( a, b );
    }

    return a;
}

Just thought that my observations might help someone...

--
Matthias Hofmann
Anvil-Soft, CEO
http://www.anvil-soft.com - The Creators of Toilet Tycoon
http://www.anvil-soft.de - Die Macher des Klomanagers