添加两个分数,为什么(次要)优化有效

Question

我前几天在我的代码库中添加了一个Fraction类(第一次,以前从未需要一个,我怀疑我现在做了,但是到底是什么:-)).当在两个分数之间写入加法时,我发现了一个小的优化,但它没有意义(在数学意义上)为什么它是这样的.

为了说明,我将使用分数A和B,分别有效地由An,Bn,Ad和Bd组成分子和分母.

以下是我用于GCD/LCM的两个函数,公式也在维基百科上.它们很简单,可以理解.当然,LCM也可以是(A*B)/ C.

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;
}

首先让我们绕过第一种方法:

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  

瞧,工作,明显,完成.

然后通过我记事本上的一些涂鸦,我遇到了另一个有效的:

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 

现在新的分母相当明显,因为它与LCD功能完全相同.其他似乎也是有意义的,除了将原始分子乘以的正确因子进行交换,在这一行中是特定的:

new_numerator = An * den_quot_b + Bn * den_quot_a  

为什么不是A A + B B？

输入示例: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

这是非常简单的,你通常要做的是使得分数超过相同的分母 - 将每个分数的分子和分母乘以其分数在其分母中不存在于第一分数中的因子.

2是从18中缺失的因子36; 3是从12缺失的36因子.因此,你乘以:

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