Эффективно вычислить произведение a * b² * c³

Каков наиболее эффективный способ вычисления произведения

a1 b2 c3 d4 e5 .. .

если предположить, что возведение в квадрат стоит примерно вдвое меньше, чем умножение? Количество операндов меньше 100.

Существует ли простой алгоритм для случая, когда время умножения пропорционально квадрату длины операнда (как в случае java.math.BigInteger)?

Первый (и единственный) ответ идеален. количество операций.

Как ни странно, применительно к значительным BigInteger эта часть вообще не имеет значения. Даже вычисление abbcccdddddeeeee без каких-либо оптимизаций занимает примерно столько же времени.

Большая часть времени тратится на окончательное умножение (BigInteger не реализует ни один из более умных алгоритмов, таких как Карацуба, Тум-Кук или БПФ, поэтому время квадратично). Важно убедиться, что промежуточные множители имеют примерно одинаковый размер, т. е. заданы числа p, q, r, s примерно одинакового размера, вычисление (pq) (rs) обычно быстрее, чем ((pq) r) s. Соотношение скоростей примерно 1:2 для нескольких десятков операндов.

Обновлять

В Java 8 в BigInteger есть как умножения Карацубы, так и умножения Тум-Кука.


java math biginteger arbitrary-precision
person maaartinus    schedule 25.10.2012    source источник
comment
Похоже на разумный вопрос для интервью... Основное решение (не оптимальное) состояло бы в том, чтобы просто вычислить мощности каждого члена в отдельности (log2 (мощность) умножения) и умножить результаты...   -  person Alexei Levenkov    schedule 26.10.2012
comment
Для этого существует алгоритм O(N log(N)^2) (где N — размер конечного числа). Но для этого вам нужно выйти за рамки java.math.BigInteger.   -  person Mysticial    schedule 26.10.2012
comment
Что такое тип операндов? инт?   -  person Adam Stelmaszczyk    schedule 26.10.2012
comment
@Adam: На самом деле операнды BigIntegers, но в настоящее время я не знаю, насколько они велики.   -  person maaartinus    schedule 26.10.2012
comment
BigInteger implements none of the smarter algorithms like Karatsuba, Toom–Cook, or FFT, so the time is quadratic к какой реализации java.math.BigInteger это относится/применяется?   -  person greybeard    schedule 21.07.2019
comment
@greybeard Обновлено .... его не было в древние времена (я не знаю истории).   -  person maaartinus    schedule 21.11.2019

Ответы (2)


arrow_upward
8
arrow_downward

Я абсолютно не знаю, оптимальный ли это подход (хотя я думаю, что он асимптотически оптимален), но вы можете сделать все это в O(N) умножениях. Вы группируете аргументы a * b^2 * c^3 следующим образом: c * (c*b) * (c*b*a). В псевдокоде:

result = 1
accum = 1
for i in 0 .. arguments:
  accum = accum * arg[n-i]
  result = result * accum

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

person jpalecek    schedule 25.10.2012
comment
Похоже, это будет выполнено примерно через O(N^2) раз. Что, кажется, достаточно хорошо для OP. +1 Тем не менее, это не асимптотически оптимально, поскольку это можно сделать в O(N log(N)^2), хотя и с использованием очень сложных для реализации алгоритмов. - person Mysticial; 26.10.2012
comment
С его текущим псевдокодом он выполняется за O(n) времени. Его код кэширует предыдущие умножения, таким образом выполняя только 2*n умножения. Все, если n — количество входных аргументов. - person Sebastian Graf; 26.10.2012
comment
@Sebastian Умножение на BigInteger не является постоянным временем. - person Mysticial; 26.10.2012
comment
Ах, это имеет смысл. Не понял, что это ограничение. - person Sebastian Graf; 26.10.2012
comment
Да, это привлекает много людей. Для BigInteger Java это может быть так же медленно, как O(N^2) для размеров операнда. - person Mysticial; 26.10.2012
comment
@Mysticial: Конечно, вы правы со временем умножения, но он как бы упускает из виду мой вопрос. Это решение работает с линейным количеством умножений, другая проблема заключается в том, что каждое умножение занимает квадратичное время. Вы не можете сказать, что время O(n**2) (используя BigInteger или лучше используя какой-то сумасшедший алгоритм), так как есть два входа: размер числа и количество терминов. - person maaartinus; 26.10.2012
comment
@maaartinus О, хорошо. Из вопроса не было ясно, были ли вы после времени выполнения или # умножения. Я предположил первое, потому что это то, что обычно волнует людей. Прости за это. Сложности, которые я привел в комментариях здесь и в этом вопросе, упрощены, поскольку действительно есть два входа. Но независимо от того, как искажены входные данные, самый известный алгоритм будет находиться в пределах логарифмического коэффициента O(N log(N)^2). Если бы у вас было только два термина или небольшое фиксированное количество терминов, на самом деле было бы всего O(N log(N)). - person Mysticial; 26.10.2012

arrow_upward
1
arrow_downward

Как упомянуто в редактировании от 26 октября 2012 года:
При сверхлинейном времени умножения по размеру операндов было бы Было бы полезно сохранить одинаковый размер операндов для длинных операций (особенно если единственным доступным Toom-Cook был toom-2 (Karatsuba)). Если не идти на полную оптимизацию, размещение операндов в очереди, которая позволяет извлекать их в порядке увеличения (значительной) длины, выглядит приличным выстрелом из бедра.
Опять же, есть особые случаи: 0, степень двойки, умножения, где один множитель (иначе) «тривиален» («умножение длинной на однозначную цифру», линейное по сумме длин множителей).
И возведение в квадрат проще/быстрее, чем обычное умножение (вопрос предлагает принять ½), что предполагает следующую стратегию:

  • на этапе предварительной обработки подсчитывать конечные нули, взвешенные по показателю степени,
    результат 0, если встречается 0
  • удалить конечные нули, отбросить результирующие значения 1
    результат 1, если не осталось значений
  • найти и объединить значения, встречающиеся более одного раза
  • настроить очередь, позволяющую извлекать «самый короткий» номер. Для каждой пары (число, показатель степени) вставьте множители, которые возведение в степень путем возведения в квадрат будет умножаться
  • необязательно: объединить "тривиальные факторы" (см. выше) и вставить заново
    Не знаю, как это сделать. Скажем, множители длины 12, где тривиальные, и начальные множители имеют длину 1, 2,..., 10, 11, 12,..., n. В оптимальном случае вы комбинируете 1+10, 2+9, … для 7 тривиальных множителей из 12. Комбинация кратчайших дает 3, 6, 9, 12 для 8 из 12.
  • извлеките самую короткую пару множителей, умножьте и снова вставьте
    , как только останется только одно число, результат таков, что с добавлением нулей из первого шага

(Если бы факторизация была дешевой, ее пришлось бы проводить довольно рано, чтобы получить максимальную отдачу от дешевого возведения в квадрат.)

person greybeard    schedule 21.11.2019