StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POAdding two fractions, why a (minor) optimization works
text
Body
copied!<p>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.</p> <p>To illustrate I will use fractions A and B, effecively consisting of An, Bn, Ad and Bd for numerator and denominator respectively.</p> <p>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.</p> <pre><code>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; } </code></pre> <p>First lets go around the 1st approach:</p> <pre><code>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 </code></pre> <p>Voila, works, obvious, done.</p> <p>Then through some scribbling on my notepad I came across another one that works:</p> <pre><code>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 </code></pre> <p>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:</p> <pre><code>new_numerator = An * den_quot_b + Bn * den_quot_a </code></pre> <p>Why is that not A<em>A + B</em>B?</p> <p>Input example: 5/12 & 11/18</p> <pre><code>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; </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload