Возведение натуральных чисел по модулю в большие степени по схеме Горнера

Пусть задано выражение вида

 

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

 

i

x 2i , (1.2)

 

где 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), при использовании модульной

 

арифметики, следует, что:

 

k -1

i

y =a x mod m =aåi =0 X i 2

 

mod m =

 

ç

=éæa20

 

X 0 mod m ö÷æça21

 

X1 mod m ÷öçæa2

 

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 не требуется вычислять заново, с самого

 

начала, так как его можно получить следующим образом:

 

 

i

çæ a2

 

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. Выход.

 

Вычислительная сложность схемы Горнера равна O( log3 ( x) ).

 

Пример 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. Трассировочная таблица

 

 

Шаги в цикле   Условие i < k   Значение xi   r   y до цикла - шаг i=1 да шаг i=2 да шаг i=3 да 256 mod 29=24 48 mod 29=19 шаг i=4 да 576 mod 29=25 475 mod 29=11 шаг i=5 нет - Выход из цикла

Ответ: y = ax mod m = 11.

 

 

Дополнительные примеры для решения:

 

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 также представляется в двоичном виде:

 

i

k -1

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. Поясните второй вариант метода возведения числа в степень.