# Boost :

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..
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.

> 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