Adding two fractions, why a (minor) optimization works..

Question

I was adding a Fraction class to my codebase the other day (the first time, never needed one before and I doubt I do now, but what the hell :-)). When writing the addition between two fractions, I found a small optimization but it doesn't make sense (in the mathematical sense) why it is like it is.

To illustrate I will use fractions A and B, effecively consisting of An, Bn, Ad and Bd for numerator and denominator respectively.

Here are two functions I use for GCD/LCM, the formulas are on Wikipedia as well. They're simple enough to understand. The LCM one could just as well be (A*B)/C of course.

static unsigned int GreatestCommonDivisor(unsigned int A, unsigned int B)
{
    return (!B) ? A : GreatestCommonDivisor(B, A % B);
}

static unsigned int LeastCommonMultiple(unsigned int A, unsigned int B)
{
    const unsigned int gcDivisor = GreatestCommonDivisor(A, B);
    return (A / gcDivisor) * B;
}

First lets go around the 1st approach:

least_common_mul = least_common_multiple(Ad, Bd)  
new_nominator = An * (least_common_mul / Ad) + Bn * (least_common_mul / Bd)  
new_denominator = least_common_mul

Voila, works, obvious, done.

Then through some scribbling on my notepad I came across another one that works:

greatest_common_div = greatest_common_divisor(Ad, Bd)  
den_quot_a = Ad / greatest_common_div  
den_quot_b = Bd / greatest_common_div  
new_numerator = An * den_quot_b + Bn * den_quot_a  
new_denominator = den_quot_a * Bd

Now the new denominator is fairly obvious, as it's exactly the same as happens in the LCD function. The other ones seem to make sense too, except for that the the right factors to multiply the original numerators with are swapped, in this line to be specific:

new_numerator = An * den_quot_b + Bn * den_quot_a

Why is that not A*A + B*B?

Input example: 5/12 & 11/18

greatest_common_div = 6  
den_quot_a = 12/6 = 2;  
den_quot_b = 18/6 = 3;  
new_numerator = 5*3 + 11*2 = 37;  
new_denominator = 36;

Answer 1

It's pretty straightforward, it's what you'd normally do to make fractions be over the same denominator - multiply each fraction's numerator and denominator by the factors that the other fraction has in its denominator that aren't present in the first.

2 is the factor of 36 which is missing from 18; 3 is the factor of 36 which is missing from 12. Thus, you multiply:

(5/12)  * (3/3)  ==>  15/36
(11/18) * (2/2)  ==>  22/36

Answer 2

Perhaps you're missing one of the identities of number theory... for any two positive numbers m and n,

 m*n = gcd(m,n) * lcm(m,n)

examples:

 4*18 = 2 * 36
 15*9 = 3 * 45

Finding a common denominator to fractions a/b and c/d involves using the lcm(b,d) or equivalently, bd/gcd(b,d).