Здравствуйте, deniok, Вы писали:
D> Я тут подумал, сделал оценки, и рост в два раза с продукта до произведения субпродуктов объяснить могу:
D> ...
Cool!
Теперь осталось только вывести аналитическую формулу, обобщающую результаты эксперимента...
Здравствуйте, geniepro, Вы писали:
G>Теперь осталось только вывести аналитическую формулу, обобщающую результаты эксперимента...
Ну, можно немножко обобщить, правда оценки довольно грубые
Пусть
x! = 10^n
n — сложность, n >> 1000. Рассмотрим в каждом способе вычислений последнюю сотню умножений. Внутри генерации подпродуктов умножение идёт на столь малое число, что сложность на этой сотне практически не растёт (f.e. 10^350000*10^5=10^350005). Пусть Pk — сложность вычисления с k подпродуктами
P1=n*100
P2=n/2*99+(n+n) = n/2*99 + 2*n
P3=n/3*98+2*n+(2*n+n) = n/3*98 + 5*n
P4=n/4*97+2*n+3*n+(3*n+n) = n/4*97 + 9*n
...
Pk = n/k*(101-k) + (k*(k+1)/2-1)*n
(в последнем случае последнее слогаемое — сумма арифметической прогрессии)
Для x=100 000 ряд для P1/Pk такой (k=1..30)
1,0 2,1 3,3 4,3 5,4 6,3 7,1 7,8 8,4 8,8 9,2 9,5 9,7 9,8 9,9 9,9 9,9 9,8 9,7 9,6 9,5 9,4 9,3 9,1 9,0 8,9 8,7 8,6 8,4 8,3
Что, по крайней мере качественно, совпадает с экспериментальными данными
Здравствуйте, Трурль, Вы писали:
Т>Простенькая задачка на оптимизацию
.
Соврал, не совсем простенькая. Поскольку в GMP используется несколько алгоритмов умножения разной сложности, получить аналитическую оценку не так просто.