Каков наиболее эффективный способ вычисления продукта
a 1 b 2 c 3 d 4 e 5...
Предполагая, что квадрат стоит примерно вдвое меньше, чем умножение? Число операндов меньше 100.
Существует ли простой алгоритм и для случая, когда время умножения пропорционально квадрату длины операнда (как при java.math.BigInteger)?
Первый (и единственный) ответ идеален w.r.t. количество операций.
Как ни странно, при применении к значимым BigInteger s эта часть вообще не имеет значения. Даже вычисления abbcccddddeeeee без каких-либо оптимизаций занимают одно и то же время.
Большую часть времени тратится на окончательное умножение (BigInteger реализует ни один из умных алгоритмов, таких как Карацуба, Тоом-Кук или БПФ, поэтому время квадратично). Важно то, что промежуточные мультипликаторы имеют одинаковую величину, т.е. Заданные числа p, q, r, s примерно того же размера, вычисляя (pq) (rs) обычно быстрее, чем ((pq) r) s. Коэффициент скорости, по-видимому, составляет около 1: 2 для некоторых десятков операндов.
