Я добавил класс 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;
}
Сначала давайте обойдем 1-й подход:
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
Теперь новый знаменатель довольно очевиден, поскольку он точно такой же, как и в функции ЖК-дисплея. Другие, похоже, тоже имеют смысл, за исключением того, что правильные множители для умножения исходных числителей поменялись местами, в этой строке, чтобы быть конкретными:
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;