Ннууоооочень быстрое возведение в степень - ? , Давно что-то не было задачек и головоломок в этом разделе...

Возведение в огромную целую степень огромных целых чисел (по модулю) -- достаточно распространенная "стандартно-билиотечная" операция в многих средах разработки, т.к, она используется в реализациях схем шифрования с открытым ключом, распространения ключей и электронной цифровой подписи.

Известен достаточно быстрый алгоритм возведения в целую степень, работающий за время O(log N) (где N - показатель степени):
1. Показатель степени представляется в виде суммы степеней двойки (таких будет не более log2 N)
2. Последовательным возведением в квадрат вычисляются сомножители, соответствующие степеням с показателем 2^k (разумеется, их тоже потребуется не более, чем log2 N)
3. Сомножители, соответствующие участвующим в разложении показателя степеням двойки перемножаются (это еще не более, чем log2 N операций)

Пример:

15 = 1 + 2¹ + 2² + 2³ = 1 + 2 + 4 + 8
a¹⁵ = a¹*a²*a⁴a⁸ = a^{1 + 2 + 4 + 8}

Посчитаем умножения:
а) степени двойки
1. получим a²
2. из уже имеющегося a² получим a⁴
3. из уже имеющегося a⁴ получим a⁸
б) перемножение
4. из уже имеющихся a и a² получим a³
5. из уже имеющихся a³ и a⁴ получим a⁷
6. из уже имеющихся a⁷ и a⁸ получим a¹⁵
итого для возведения в степень 15 потребовалось 6 операций умножения

Однако, показатель степени 15 замечателен тем, что он является первым (наименьшим) показателем, для которого возможен более быстрый (в штуках умножений) способ:

a¹⁵ = a⁵ * a⁵ * a⁵
a⁵ = a * (a²)²
требующий всего пяти умножений.

Вот их перечисление, для наглядности:

1. получим a²
2. получим a⁴
3. получим a⁵
4. получим a¹⁰
5. получим a¹⁵

Задача состоит в том, чтобы для заданного показателя степени N найти самый быстрый способ возведения числа в N-ю степень. Одно умножение (оно по модулю некоего ограниченного числа) будем считать операцией константной (единичной) сложности.

Ограниченный вариант задачи (для компилятора С, оптимизирующего выражение вида a*a*a*a*...*a ): N ограничено сверху величиной 2³¹-1.

Kew, этот способ был известен еще 100 лет назад и сейчас описан практически в любой околоалгоритмической книжке.

Сообщение отредактировано: shm - 30.09.13, 21:43

Имеется ввиду, способ находить более короткие чем разложение по степеням двойки последовательности операций?

Самый быстрый способ, ЕМНИП, NP-полная задача

Ну и что, что NP-полная. Пригодиться то в деле сможет только степень до 1000 ну или до 10000.
Первый шаг думаю так: берёте и считаете минимальное кол-во умножений для степеней от 1 до 6..7.
Получаете последовательность натур. чисел.
С ней идёте в OEIS. Вдруг там найдёте.
Если да, то проверьте на других степенях.
Если нет, то придётся самому алгоритм ваять...

Я пробовал когда то решить эту задачу. Обнаружил, что для степеней меньших 256 иногда удаётся сэкономить 1, и совсем редко 2 умножения. Учитывая, сколько времени у меня занимало решение для степеней больше 100 (и использование памяти), я решил, что экономия в среднем 1 процента умножений (пусть даже для больших степеней поучится 2 процента) не стоит таких затрат.

Обычно экономия достигалась, когда удавалось разложить степень в вид M*N+K (K=0,1,2), и M, N содержали мало единиц.

Добавлено 02.10.13, 04:20
Такая экономия имеет смысл при вычислении фиксированных степеней, которые обычно малы. На них как правило сократить число умножений не получается.
Большие степени обычно каждый раз разные, и поиск оптимального алгоритма съест всю возможную экономию.

Цитата Славян @ 01.10.13, 18:03

Пригодиться то в деле сможет только степень до 1000 ну или до 10000.

Вы всегда додумываете то, о чем не говорилось? На всякий случай выделю основное:

Цитата Kew @ 30.09.13, 14:51

Ограниченный вариант задачи (для компилятора С, оптимизирующего выражение вида a*a*a*a*...*a ): N ограничено сверху величиной 2³¹-1.

Добавлено 02.10.13, 05:32

Цитата amk @ 02.10.13, 04:17

Обнаружил, что для степеней меньших 256 иногда удаётся сэкономить 1, и совсем редко 2 умножения.

Где-то читал, что выигрыш может достигать 1.5

Добавлено 02.10.13, 05:35

Цитата OpenGL @ 02.10.13, 05:32

Где-то читал, что выигрыш может достигать 1.5

Ну как "где-то". Не где-то, а на нашем форуме в этой теме:

Цитата albom @ 24.09.08, 13:39

Если изходить из теоремы Браура, то метод, основанный на возведение в квадрат, в среднем будет требовать в 1.5 раза больше умножений.

Правда, что за теорема - пока не понял.

Цитата OpenGL @ 02.10.13, 05:32

Где-то читал, что выигрыш может достигать 1.5

Цитата OpenGL @ 02.10.13, 05:32

Не где-то, а на нашем форуме в этой теме:

Там рассматривалось очень хорошая степень: 65535 = 3*5*17*257. Каждый из сомножителей содержит ровно 2 единицы. Соответственно для подстепеней требуемое число умножений равно 2, 3, 5 и 9, в сумме 19 (против 30 обычным способом). К сожалению, такие хорошие числа скорее исключение, чем правило.

Цитата OpenGL @ 02.10.13, 05:32

Правда, что за теорема - пока не понял.

Вероятно, эта (хотя она не теорема, а гипотеза).

Length of shortest addition chain for n
http://oeis.org/A003313

Блеск!

Цитата Pavlovsky @ 16.10.13, 06:05

Length of shortest addition chain for n

Не впечатлило. Я добрался до 187 (думал, что до 255, но оказалось меньше), не которые степени имеют несколько оптимальных вариантов. Серьёзного выигрыша ни на одной из этих степеней не получил.

Почти все найденные оптимальные варианты являются произведением двух сомножителей с малым числом единиц плюс, может быть, малое число, участвующее в вычислении одного из сомножителей. По крайней мере среди оптимальных почти всегда есть составное.

Короткая записка, которую я при этом написал для себя

Простые показатели, вычисляемые быстрее, чем по классической схеме

23=20+3=18+5, 31=30+1=27+4=22+9, 43=40+3=34+9, 59=51+8=56+3, 61=60+1,
83=80+3, 103=102+1, 107=99+8=104+3=13*8+3=(3*4+1)*8+3, 109=108+1,
127=126+1, 149=144+5, 151=150+1, 163=160+3=(2+3)*32+3, 167=166+1,
173=172+1, 179=163+16=170+9=176+3=(3+8)*16+3, 181=180+1,

Показатели, составные решения которых хуже прямого вычисления,
(являющегося оптимальным)

33=3*11=32+1, 49=7*7, 65=5*13, 121=11*11, 129=3*43, 133=7*19, 145=5*29

Составные показатели, не имеющие среди оптимальных составного решения

77=7*11=(5+4)*8+5=(9+8)*4+9

Составные показатели, оптимальноe решениe которых лучше классического,
но для которого выделяется не минимальный сомножитель

165=3*5*11=5*33

Вывод, который можно сделать, анализируя проверенные степени - в
случае составного показателя степени за редким исключением среди
оптимальных решений находится либо классическое поразрядное вычисление,
либо выделение из показателя минимального простого множителя, и
последовательное возведение в эти степени.
Второе наблюдение - поиск перебором зависит от количества делителей
числа. Так для простых чисел поиск оптимальных стратегий вычислений
обычно происходит довольно быстро, и вариантов бывает не так много, как
для составных.
В любом случае, для не слишком больших показателей (проверены
показатели вплоть до до 186) оптимизация позволяет сэкономить не более
1-2 умножений, что составляет 10-15% от числа умножений классического
метода.

С увеличением степени выигрыш увеличивается, но и поиск оптимальной цепочки занимает всё больше времени.
Не вполне уверен (не проверял), но похоже, что в оптимальных цепочках в образовании каждой следующей степени участвует последняя из уже достигнутых степеней. Это может ускорить поиск цепочки

Сообщение отредактировано: amk - 16.10.13, 14:54

Цитата amk @ 16.10.13, 14:47

Не впечатлило. Я добрался до 187 (думал, что до 255, но оказалось меньше)

Вот блин, а я думал, что там и до многих тысяч всё рассчитали...

Цитата amk @ 16.10.13, 14:47

Не впечатлило. Я добрался до 187 (думал, что до 255, но оказалось меньше), не которые степени имеют несколько оптимальных вариантов. Серьёзного выигрыша ни на одной из этих степеней не получил.

Почти все найденные оптимальные варианты являются произведением двух сомножителей с малым числом единиц плюс, может быть, малое число, участвующее в вычислении одного из сомножителей. По крайней мере среди оптимальных почти всегда есть составное.

Будьте осторожнее в своих исследдованиях. Задача NP-полная. Вот так случайно найдете эффективный алгоритм и рухнет целое направление в математике.

Добавлено 17.10.13, 03:20

Цитата Славян @ 16.10.13, 18:31

Вот блин, а я думал, что там и до многих тысяч всё рассчитали...

По ссылке есть таблица до 10001 (Десять тысяч один).

Я вчера запустил поиск для 191, еле дождался результата. Число простое, но найдено на удивление много вариантов. Достигнутая экономия - два умножения (11 против 13).
Среди оптимальных цепочек не все можно построить на основе последней достигнутой степени.

Добавлено 17.10.13, 04:26
Сейчас посмотрел этот список.
Судя по нему выигрыш составляет:
в 1124 случаях ничего;
в 2558 - экономится 1 умножение;
в 3245 - 2;
в 1765 - 3;
в 953 - 4;
в 322 - 5;
в 24 - 6;
в 10 - 7.
В среднем выигрыш составляет 11.22%, при максимуме 31.82%

Добавлено 17.10.13, 04:35

Цитата Pavlovsky @ 17.10.13, 03:19

Будьте осторожнее в своих исследдованиях. Задача NP-полная. Вот так случайно найдете эффективный алгоритм и рухнет целое направление в математике.

Ну я, когда писал программу сразу догадался о NP-полноте. Поэтому просто ищу оптимум перебором с возвратами. Ограничивая длину цепочки текущим оптимумом и взяв в качестве начальной обычную последовательность.

Я ещё как-то вручную исследовал эту задачу на предмет короткого вычисления с ограниченной памятью (классический алгоритм требует максимум двух ячеек). Для вычисления в стеке калькуляторов Б3-34, МК-52.