Самый эффективный алгоритм для вычисления общего числителя суммы дробей

Я почти уверен, что это правильный сайт для ответа на этот вопрос, но не стесняйтесь переместить его на какой-нибудь другой сайт stackexchange, если он подходит лучше.

Предположим, у вас есть сумма дробей a1 / d1 + a2 / d2 +… + an / dn . Вы хотите вычислить общий числитель и знаменатель, т.е. перепишите его как p / q . У нас есть формула

p = a1*d2*…*dn + d1*a2*d3*…*dn + … + d1*d2*…d(n-1)*an
q = d1*d2*…*dn.

. Какой наиболее эффективный способ вычислить эти вещи, в частности, p ? Вы можете видеть, что если вы вычислите это наивно, то есть используя формулу, которую я привел выше, вы вычислите много лишних вещей. Например, вы вычислите d1 * d2 n-1 раз.

Моей первой мыслью было итеративное вычисление d1 * d2 , d1 * d2 * d3 ,… и dn * d (n-1) , dn * d (n-1) * d (n-2) , ... но даже это неэффективно, потому что вы в конечном итоге дважды вычисляете умножение в «середине» (например, если n достаточно велик, вы вычислите d3 * d4 дважды).

Я уверен, что эту проблему можно как-то выразить, используя, может быть, некоторую теорию графов или комбинаторику, но я недостаточно изучил

И одно замечание: меня не волнует отмена, это просто самый эффективный способ умножения.

ОБНОВЛЕНИЕ:

Я должен был знать, что люди, использующие stackoverflow, будут предполагать, что это числа, но я так привык к своему варианту использования, что забыл упомянуть об этом.

Мы не можем просто «разделить» "out an из каждого термина. Пример использования здесь - символическая система. На самом деле, я пытаюсь исправить функцию под названием .as_numer_denom () в системе компьютерной алгебры SymPy , которая в настоящее время вычисляет это наивным способом. См. соответствующую проблему SymPy .

При разделении вещей есть некоторые проблемы, которых я бы хотел избежать. Во-первых, нет гарантии, что все будет отменено. Это потому, что математически (a * b) ** n! = A ** n * b ** n в целом (если a и b являются положительно, но e.g., если a == b == - 1 и n == 1/2 , вы получите (a * b) ** n == 1 ** (1/2) == 1 , но (- 1) ** (1/2) * (- 1) ** (1/2) == I * I == -1 ). Поэтому я не думаю, что будет хорошей идеей предполагать, что деление на на отменит его в выражении (на самом деле это может быть необоснованным, мне нужно проверить, что делает код).

Во-вторых, я хотел бы также применить этот алгоритм для вычисления суммы рациональных функций. В этом случае члены автоматически умножаются в один многочлен, и «деление» каждого на потребует применения алгоритма полиномиального деления. Как видите, в этом случае вы действительно хотите вычислить наиболее эффективное умножение.

ОБНОВЛЕНИЕ 2:

Я думаю, что мои опасения по поводу отмены символических терминов могут быть необоснованными. SymPy не отменяет такие вещи, как x ** n * x ** (m - n) автоматически, но я думаю, что любые экспоненты, которые объединяются посредством умножения, также объединяются посредством деления, поэтому степени должны отменяться.

Существует проблема с автоматическим распределением констант между дополнениями, например:

In [13]: 2*(x + y)*z*(S(1)/2)
Out[13]: 
z⋅(2⋅x + 2⋅y)
─────────────
      2      

Но это, во-первых, ошибка , а во-вторых, никогда не может быть проблемой (я думаю), потому что 1/2 будет разделен на 1 и 2 алгоритмом, который получает числитель и знаменатель каждого члена.

Тем не менее , я все еще хочу знать, как это сделать, не «отделяя» di от каждого члена, чтобы у меня был эффективный алгоритм для суммирования рациональных функций.