Re: [boost] rational +=,-=

From: Nickolay Mladenov (nikiml_at_[hidden])
Date: 2001-01-13 13:43:15

To prove it:

We have to compute a/b + c/d, where gcd(a,b)=1 and gcd(b,c)=1.
Let g = gcd(b,d), and b = b1*g , d=d1*g than gcd(b1,d1)=1

The result is (a*d1 + c*b1) / (b1*d1*g).
Now we have to normalize this ratio and lets assume h | gcd((a*d1 + c*b1) ,
(b1*d1*g)), h > 1
if h | b1 => gcd(h,d1)=1 and hence h|(a*d1+c*b1) => h|a. .But since
gcd(a,b1)=1 we have h=1..
similarly h|d1 leads to h=1.
So we have that h | gcd((a*d1 + c*b1) , (b1*d1*g)) => h|g
Finally we have gcd((a*d1 + c*b1) , (b1*d1*g)) = gcd((a*d1 + c*b1) , g)
Which proves, that instead of "normalize"-ing the result it is better divide
nom and den by gcd((a*d1 + c*b1) , g)

Example:
    111/97 +29/14 = (14*111+29*97)/(14*97), and since gcd(14,97)=1 this is
normalized,
    but calling normalize on it will perform 10 divs to find this out.

Nickolay Mladenov wrote:

> The += and -= operators will be way more efficient if rewriten as:
>
> template <typename IntType>
> rational<IntType>& rational<IntType>::operator+= (const
> rational<IntType>& r)
> {
>     IntType g= gcd(den, r.den)
>     den /= g; /one mull removed
>     // This calculation avoids overflow
>     num = num * (r.den / g) + r.num * (den); //one div removed
>     //    normalize(); // Example where this is needed: 1/2 + 1/2
>     g=gcd(nom,g);
>     //this does the normalisation since if h |den,nom => h|g,nom, and it
> is better since g is way smaller than den
>     nom/=g;
>     den *=r.den/g; //reduces the overflow even more
>     return *this;
> }
>
> template <typename IntType>
> rational<IntType>& rational<IntType>::operator-= (const
> rational<IntType>& r)
> {
>     IntType g= gcd(den, r.den)
>     den /= g;
>     // This calculation avoids overflow
>     num = num * (r.den / g) - r.num * (den);
>    //  normalize(); // Example where this is needed: 1/2 + 1/2
>     g=gcd(nom,g);
>     nom/=g;
>    den *=r.den/g;
>    return *this;
> }
>
> Nikolay