2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки





Начать новую тему Ответить на тему
 
 Самое-самое быстрое возвдение в (фиксированную) степень
Сообщение06.03.2015, 16:46 


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

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

 Профиль  
                  
 
 Re: Самое-самое быстрое возвдение в (фиксированную) степень
Сообщение06.03.2015, 17:06 
Заслуженный участник


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 2 ] 

Модераторы: Toucan, maxal, Karan, PAV, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group