Инвариант быстрого возведения в степень
Четный показатель степени уменьшается вдвое после возведения основания в квадрат, а явное произведение переносит множитель с нечетного шага.
Как можно быстро уменьшать показатель степени, не меняя вычисляемую степень?
- Отслеживание base, exponent и product как полного состояния процесса
- Возведение основания в квадрат при делении четного показателя степени пополам
- Перенос одного множителя base в product на нечетном шаге
- Сохранение величины product, умноженной на base в степени exponent, в качестве инварианта
При каждом вызове product × base^exponent равняется исходной запрошенной степени. Если exponent четный, замена base его квадратом и деление exponent пополам сохраняет эту величину. Если exponent нечетный, умножение product на base и вычитание единицы из exponent сохраняет ее взамен.
Процесс останавливается, когда exponent достигает нуля, поскольку оставшаяся степень равна 1, а product уже содержит ответ. Программа с историей записывает полное состояние при каждом вызове, поэтому каждый четный и нечетный переход можно проверить напрямую.
- Вывод
- —
- Значение
- —
- Диагностика
- —
Первая программа возвращает 1594323. Вторая возвращает ((2 10 1) (4 5 1) (4 4 4) (16 2 4) (256 1 4) (256 0 1024)).
Проследите за решением even? перед каждым переходом. На четных шагах base возводится в квадрат, а exponent делится пополам, на нечетных шагах product поглощает base, а exponent уменьшается на единицу. Записанные состояния охватывают точно выбранные целочисленные входные данные.
Измените программу и сравните результат.
Запустите fast-expt для 5 в степени 11. До запуска перечислите, является ли каждый шаг показателя степени четным или нечетным.
Показать подсказку
Нечетный шаг вычитает единицу, делая следующий показатель степени четным. Четный шаг делит его пополам.