Возведение натуральных чисел по модулю в большие степени по схеме Горнера
Пусть задано выражение вида
y = a x mod m , (1.1)
где a ÎN - основание степени,
x ÎN - степень выражения,
m ÎN - числовой модуль, число, нормирующее выражение в диапазоне
[0..m−1],
mod - знак операции взятия остатка от деления делимого ax на делитель
m,
y ÎN - результат вычисленного выражения, лежащий в диапазоне
[0..m−1],
N - множество натуральных чисел.
Пусть все операции производятся над натуральными числами, целочисленно, без округлений.
При непосредственном вычислении значение выражения ax может
выйти за размеры машинного слова (значения которого могут лежать в диапазоне [0..232−1]) уже при малых значениях a и x, например при a = 3 и x = 21. Поэтому необходимы другие механизмы получения результата, полагая, что будет использоваться модульная арифметика.
Схема Горнера обладает следующими особенностями:
- выражение (1.1) вычисляется при ограничениях на диапазон натуральных чисел для ПЭВМ (промежуточные результаты берутся по модулю);
- каждая операция разбивается на подмножество эквивалентных;
- используется, в отличие от последовательного возведения числа a в степень x, меньше операций умножения из-за разложения степени выражения (1.1) на сумму степеней числа 2.
Десятичное число x можно представить в виде суммы единиц, десятков, сотен, тысяч и т.д., то есть в виде десятичного полинома:
x= x0?100 + x1?101 + x2?102 + . . .+ xk-1?10k-1,
где xi= [0..9] - является десятичным числом,
i = 0, k - 1 , k ÎN - число, такое,
что x ≤ 10k. Например, десятичное число 50921 можно записать в виде полинома:
5092110 = 5? 104 + 0? 103 + 9? 102 + 2? 101 + 1? 100 (слева направо: 5 в разряде
десятков тысяч, 0 - в разряде тысяч, 9 - в разряде сотен, 2 - в разряде десятков, а 1 - в разряде единиц).
Аналогично, можно представить число x в виде двоичного числа
(двоичного полинома):
x= x0? 20 + x1? 21 + x2? 22 + . . .+ xk-1? 2k-1 или
k -1
x =å
i=0
|
где xi = {0, 1} - двоичное число,
i = 0, k - 1 , k ÎN - число двоичных разрядов,
необходимое для представления числа x (x ≤ 2k). Например, двоичное число
10111 можно записать в виде полинома:
101112 = 1*104 + 0*103 + 1*102 + 1*101 + 1*100 (слева направо: 1 в разряде десятков тысяч, 0 - в разряде тысяч, 1 - в разряде сотен, 1 - в разряде десятков, а 1 - в разряде единиц).
Тогда из формул (1.1) и (1.2), при использовании модульной
арифметики, следует, что:
|
|
mod m =
|
X 0 mod m ö÷æça21
| |
X 2 mod m ö÷...çæa2
k -1
X k -1 mod m ÷öùmod m.
(1.3)
êëè
øè øè ø è
øúû
Здесь xi задают i-ые двоичные разряды степени x.
В схеме Горнера выражение y вычисляется с меньших номеров
двоичных разрядов в сторону возрастания степени i. Член r = çæ a2i X i mod m ÷ö
è ø
( i = 0, k - 1 ) из (1.3) при xi = 1 не требуется вычислять заново, с самого
начала, так как его можно получить следующим образом:
|
mod m ÷ö =çæ a
2i -1
2 mod m ÷ö
mod m , по значению предыдущего шага.
è ø è ø
Алгоритм работы схемы Горнера.
Опишем алгоритм схемы Горнера по шагам. На вход: числа a, x, m ÎN.
На выходе: y ÎN или сообщение о неприменимости алгоритма.
1. Ввод с консоли значения основания степени a, степени x и модуля m.
2. Если m = 0, то деление на ноль, выход.
3. Если a = 0, то результат равен y = 0, переход к пункту 9.
4. Если a = 1 или x = 0, то результат равен y = 1, переход к пункту 9.
5. Производим поиск для числа x верхней границы, являющейся степенью числа 2: число k ÎN такое, что x ≤ 2k, то есть k ≥ log2 x.
5.а) Пусть r = 20 и k = 0; пока k < 32 (максимальное число разрядов
в машинном слове) и r ≤ x, то возводим 2 в степень k: r = 2k и увеличиваем k
на единицу.
5.б) Если k = 0 или k > 32, то задача не решается в установленных условиях, выход (число 32 обозначает максимальную степень двойки для машинного слова, то есть число 232 задает максимальное число различных значений, которые можно сохранить в машинном слове). Иначе пункт 6.
6. Пусть r = a. Если степень x нечетна (остаток от деления на 2 равен единице), то y = a, иначе y = 1.
7. Для всех i = 1, k - 1 выполняем следующие действия:
7.а) r = [(r mod m)·(r mod m)] mod m = r2 mod m;
7.б) если i-ый бит числа x равен единице xi = 1, то y = (y · r) mod m.
8. Вывод результата y. Выход.
| |
Пример 1.13. Необходимо число a = 2 возвести в степень x = 25 и привести результат по модулю m = 29.
Тогда k, удовлетворяющее неравенству k > log2 x, равно 5.
Число x представимо в двоичной форме как x = 2510 = 11 0012. Это число является нечетным.
На шаге 6 получаем, что r = a = y = 2.
Далее представим шаг в виде трассировочной табл. 1.10:
Таблица 1.10. Трассировочная таблица
|
Дополнительные примеры для решения:
1) a = 7, x = 5, m = 31. Найти
2) a = 3, x = 7, m = 29. Найти
y = a x mod m
y =ax mod m
3) a = 5, x = 11, m = 14. Найти
y =ax mod m
Существует другой вариант схемы Горнера возведения целых чисел в
большие степени. Степень x также представляется в двоичном виде:
|
x =åxi 2
, x Î{0, 1}. В отличие от первого варианта схемы Горнера
i=0
последовательно рассматриваются двоичные разряды числа x в направлении понижения номера разряда. Тогда возведение в степень можно выполнить по
следующей схеме:
k -1 i
y =a x mod m =aåi =0 xi 2 mod m =
=[(...((((aX k -1)2 mod m ×aX k -2 )2 mod m ×aX k -3 )2 ... ×aX1)2 mod m ×aX 0 ]mod m.
Пример 1.14. Вычислим y = ax mod m при a = 9, x = 5, m = 31. Число x в двоичном виде можно представить как x = 510 = 1012. Тогда y = ax mod m =
= ((( a X 2 )2 mod m · a X1 )2 mod m · a X 0 ) mod m =
= (((a1)2 mod m ·a0)2mod m ·a1) mod m =
= ((a2 mod m)2 mod m · a) mod m = (92 mod 31)2 mod 31 · 9) mod 31 =
= (192 mod 31 · 9) mod 31 = 180 mod 31 = 25.
Ответ: y = ax mod m = 25.
Опишем второй вариант схемы Горнера. Пусть первые 6 шагов совпадают с алгоритмом первого варианта схемы Горнера.
…
7. Пусть результат y = 1, переменная цикла i = k − 1 и r = a2 mod m.
8. Если xi = 1 (i-ый разряд числа x равен 1), то y = (y2 · r) mod m,
иначе y = y2 mod m.
9. Вычислить i = i − 1. Если i > 1, то перейти к шагу 8.
10. Если x0 = 1 (учесть последний бит числа x), то y = (y · a) mod m.
11. Вывод результата y. Выход.
Пример 1.15. Вычислим y = ax mod m при a = 5, x = 13, m = 11. Число x в двоичном виде можно представить как x = 1310 = 11012.
Пусть y = 1. Представим вычисления шагов 8-9 в виде трассировочной
табл. 1.11.
Таблица 1.11. Трассировочная таблица
| Шаг, i | xi | y |
| x3 = 1 | (1 · 11) mod 14 = 11 | |
| x2 = 1 | (112 · 11) mod 14 = (9 · 11) mod 14 = 1 | |
| x1 = 0 | 1 mod 14 = 1 |
На шаге 10 будет учтен последний бит числа x: y = (y ·
= (1 · 5) mod 14 = 5.
Ответ: y = ax mod m = 5.
a x0 ) mod m =
Вычислите по второму варианту дополнительные примеры, представленные выше.
Примечания.
Для программной реализации алгоритма схемы Горнера требуется осуществлять перевод степени x из десятичной формы представления в двоичную. При вводе числа x и его сохранении в машинной переменной оно
уже будет представлено в двоичной форме. Поэтому можно не переводить числа, а для работы с отдельными разрядами (битами) двоичного числа использовать программные методики, описанные в приложении.
Вопросы для самопроверки.
1. Для чего нужна схема Горнера?
2. Как работает схема Горнера?
3. Какими особенностями обладает схема Горнера?
4. Как можно представить число в виде степеней основания счисления?
5. Что дает разложение степени в схеме Горнера в двоичное представление?
6. Какие ограничения накладываются на входные значения схемы Горнера?
7. Как можно выполнить перевод числа с длиной в машинное слово из десятичной в двоичную систему счисления?
8. Как можно выполнить возведение двойки в степень с помощью команд ЭВМ?
9. Какие математические операции используются в схеме Горнера?
10. Поясните второй вариант метода возведения числа в степень.