|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Evgenij Masherov 2:5020/175.2 16 Nov 2002 14:35:06
To : Alexander Lunkov
Subject : возведение в степень
--------------------------------------------------------------------------------
Fri Nov 01 2002 21:18, Alexander Lunkov wrote to All:
AL> Ищу алгоритм "быстрого" возведения в степень. Без +, *, exp. Сказали,
AL> что существует такой алгоритм.
Если требуется вовсе обойтись без названных операций - то придется
эмулировать, используя только битовые операции, какой-либо процессор. Ввиду
явной бесполезности такой задачи осмелюсь предположить, что + вполне дозволенЮ
экспонента - напротив, запрещена, а * использовать можно, но следует
минимизировать, что обычно и понимается под "быстрым возведением в степень".
Простой и понятный алгоритм для этого - двоичный.
Если мы возводим a^b, причем b=b(k)*2^k+b(k-1)*2^(k-1)+...+b(1)*2+b(0)
b(i) ноль или один,
то
a^b=a^(b(k)*2^k)*a^(b(k-1)*2^(k-1))*...*a^b(0)=(a^(2^k))^b(k)*...*a^b(0)=
(((..(a^2)^2...)^2)^b(k)*...*a*b(0)
Возведение в степень b(i) не представляет особых трудностей, поскольку
сводится либо к тождественной операции, если единица, либо к пропуску оной,
если ноль.
Возведение же в степень, равную степени двойки, производится последовательным
возведением в квадрат.
Следует отметить, что числа возрастают здесь весьма быстро, так что либо
операции делаются по модулю (т.е. после каждого умножения берется остаток от
деления на выбранный модуль), либо надо озаботиться длинной арифметикой
(длинное умножение - вещь не вполне тривиальная...). В ряде практических задач
(криптографии, скажем) нужно и то, и другое.
Подробное описание алгоритма можно найти во втором томе Кнута, там же есть и
конкурирующий с ним, основанный на разложении чисел на множители, несколько
более сложный. Возможны и схемы, привязанные к определенному показателю
степени.
Алгоритм может быть обобщен на отличный от двух показатель степени, возможно,
ценой увеличения затрат памяти. В частности, интересно было бы, ввиду падения
относительной стоимости деления, обобщить на троично-симметричное
представление, упомянутое ранее в этой же ветке.
Евгений Машеров АКА СанитарЖеня
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
