Здравствуйте, 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 используется несколько алгоритмов умножения разной сложности, получить аналитическую оценку не так просто.