Самое-самое быстрое возвдение в (фиксированную) степень

[fractalon]

Не смог точно определиться, в этот ли раздел стоит помещать тему или в математический. Так что извиняюсь, если что, перенесите.

Сразу скажу, что речь не пойдёт о создании нового алгоритма возведения в степень, а хочется просто научится вычислять функцию $N(a)$ - минимальное количество умножений, достаточное для возведения числа в a-тую степень.
Есть, конечно, всем известный алгоритм бинарного возведения, и он асимптотически оптимален, кажеться. Но для числа 27, к примеру, он даёт 7 умножений при любой реализации. А если представить $x^{27}$ как ${{x^3}^3}^3$, то можно управиться за 6 умножений. Точно так же для $a=125$ можно возводить бинарным алгоритмом за 11 умножений. А можно представить как ${{x^5}^5}^5$, после чего в пятую степень возводить бинарным алгоритмом. Получится 9 действий.
Кажеться, что вычисление $N(a)$ для данного $a$ - очень трудоёмкая задача, вряд ли полиномиальная. Но если рассмотреть, например, задачу нахождения всех $N(x)$ для целых $x<a$? Как использовать предыдущие вычисления чтобы найти действительно минимальное количество перемножений?

Это что-то вроде задачи перебора разбиений, но намного сложнее, потом что пусть, делая последнее перемножение, мы получаем ${x^b} {x^c} = {x^a}$. Тогда $N(a) \le N(b) + N(c) + 1$. Но мы можем получить и меньше $N(b) + N(c) + 1$ перемножений, оставив последний шаг тем же, то есть получая сначала $x^b$ и $x^c$. Ведь по ходу вычисления $x^b$ мы можем получить какие-то промежуточные степени, которые потом можно использовать для вычисления $x^c$, избавившись от каких-то перемножений.

То есть просто перебрать пары $(b,c)$ для $b+c=a$ не получится, нужно анализировать, какие степени вычисляются по ходу вычисления $x^b$ и $x^c$, смотреть, как можно провязать вычисление двух степеней... Это уже сумасшедшее время.

Что касается математики, то максимум, что мне удалось вывести на коленке за один вечер - это $N(a (b+c)) \le N(a) + N(b) + N(c) + 1$, самое элементарное. Дальше пока ничего.

Решил написать в раздел олимпиадного программирования, потому что интересует именно алгоритм. Повторюсь, не какой-то супермощный алгоритм возведения в степень (бинарного вполне хватает асимптотически ), а алгоритм точного вычисления $N(a)$.

Ну, и ещё я как ни увижу сложное задачу, думаю, не NP-ли она и не имеет ли связи со знаменитыми кликами, булевыми функциями и прочими...

-- 06.03.2015, 15:50 --

fractalon в сообщении #986525 писал(а):

Что касается математики, то максимум, что мне удалось вывести на коленке за один вечер - это $N(a (b+c)) \le N(a) + N(b) + N(c) + 1$, самое элементарное. Дальше пока ничего.

Пока не нашёл примера, где лучшим результатом была бы другая схема, то есть где последним перемножением было бы ${x^b} {x^c}$, но при вычислении $x^c$ использовалась вычисленная при определнии $x^b$ степень $x^d$, но такая, чтобы $d$ не делил ни $b$ ни $c$.

[venco]

Задача вычислительно сложная.
См: A003313