Я почти уверен, что это правильный сайт для этого вопроса, но не стесняйтесь перенести его на другой сайт 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 дважды).
Я уверен, что эту проблему можно как-то выразить, используя некоторую теорию графов или комбинаторику, но я недостаточно изучил эту штуку, чтобы хорошо к ней относиться.
И еще одно замечание: меня не волнует отмена, просто самый эффективный способ умножения вещей.
UPDATE:
Я должен был знать, что люди из stackoverflow будут предполагать, что это числа, но я настолько привык к своему случаю использования, что забыл упомянуть об этом.
Мы не можем просто «разделить» an от каждого термина. Вариант использования здесь является символической системой. На самом деле, я пытаюсь исправить функцию с именем .as_numer_denom() в системе компьютерной алгебры SymPy , которая в настоящее время вычисляет это наивным способом. См. соответствующий выпуск SymPy .
У деления вещей есть некоторые проблемы, которых я бы хотел избежать. Во-первых, нет гарантии, что все отменится. Это потому, что математически, (a*b)**n != a**n*b**n в целом (если a и b положительны, то это верно, но, например, если a == b ==-1 и n == 1/2, вы получите (a*b)**n == 1**(1/2) == 1, но (-1)**(1/2)*(-1)**(1/2) == I*I == -1). Поэтому я не думаю, что будет хорошей идеей предполагать, что деление на an отменит его в выражении (это может быть на самом деле необоснованно, мне нужно проверить, что делает код).
Во-вторых, я хотел бы также применить этот алгоритм для вычисления суммы рациональных функций. В этом случае члены будут автоматически умножаться вместе в один многочлен, и «деление» каждого an будет включать применение алгоритма деления многочлена. В этом случае вы можете видеть, что вы действительно хотите вычислить наиболее эффективное умножение.
ОБНОВЛЕНИЕ 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 от каждого слагаемого, чтобы у меня был эффективный алгоритм суммирования рациональных функций.