рефераты конспекты курсовые дипломные лекции шпоры
- Раздел Компьютеры
- /
- Вычисление степеней, возведение сравнений в степень
Реферат Курсовая Конспект
Вычисление степеней, возведение сравнений в степень
Вычисление степеней, возведение сравнений в степень - раздел Компьютеры, МЕТОДЫ И СРЕДСТВА ЗАЩИТЫ КОМПЬЮТЕРНОЙ ИНФОРМАЦИИ Многие Результаты Теории Сравнений Связаны С Остатками Высоки...
Многие результаты теории сравнений связаны с остатками высоких степеней чисел, поэтому обсудим интересную задачу эффективного вычисления xn по заданным x и n, где n – положительное целое число. Пусть, например, нам предложили вычислить x16; мы могли бы просто начать с x и умножить его на себя последовательно 15 раз. Однако тот же ответ можно получить всего за четыре умножения, если последовательно вычислить x2, x4, x8, x16, возводя в квадрат каждый из промежуточных результатов.
Та же идея применима, вообще говоря, при произвольном значении n. А именно, запишем n в двоичной системе счисления и заменим в этой записи каждую цифру “1” парой букв SX, а каждую цифру “0” – буквой S, после чего вычеркнем крайнюю левую пару букв SX. Результат[3] превращается в правило вычисления 
, если букву “S” интерпретировать как операцию возведения в квадрат, а букву “X” – как операцию умножения на x. Например, если n = 23, то его двоичным представлением будет 10111; строим последовательность SX S SX SX SX, удаляем из нее начальную пару SX и в итоге получаем следующее правило ычисления: S SX SX SX. Согласно этому правилу мы должны возвести x в квадрат, затем снова возвести в квадрат, затем умножить на x, возвести в квадрат, умножить на x, возвести в квадрат и, наконец, умножить на x”; при этом мы последовательно вычисляем x2, x4, x5, x10, x11, x22, x23.
Этот бинарный метод очень древний; он появился раньше 200 г. до н. э. в Древней Индии; однако в течение последующих 2000 лет этот метод,по-видимому, больше ни разу не упоминался!
Бинарный метод “S и X” вычисления xn не требует никакой дополнительной оперативной рабочей памяти, за исключением памяти для хранения значения x и текущего промежуточного результата, поэтому такой метод удобен для схемной реализации на двоичной машине. Его можно также без труда запрограммировать как для двоичной, так и для десятичной машины; но при его реализации необходимо считывать двоичное представление числа n слева направо, в то время как обычно такое считывание удобно производить справа налево. Используя, например, двоичную ЭВМ, мы можем сдвигать последовательно двоичное представление числа n вправо на один бит, пока в результате не получим нуль; работая с десятичной ЭВМ, мы можем делить на 2 (или, что то же, умножать на 5 или на 
), чтобы вызвать сдвиг двоичного представления справа налево. Вот почему часто более удобен следующий алгоритм, основанный на прочтении числа справа налево.
Алгоритм. (Бинарный метод возведения в степень, основанный на считывании справа налево.) При помощи этого алгоритма вычисляется xn, где n – положительное число. (Здесь x принадлежит произвольной алгебраической системе, в которой определена ассоциативная операция умножения с единичным элементом 1.)
1. [Начальная установка.] Установить N ¬ n, Y ¬ 1, Z ¬ x.
2. [Разделить N пополам.] (В этот момент выполняется соотношение xn = Y·ZN.) Установить 
и одновременно определить, было ли старое значение N четно или нечетно. Если N было четным, перейти к выполнению шага 5.
3. [Умножить Y на Z.] Установить Y ¬ Y * Z.
4. [N = 0?] Если N = 0, то выполнение алгоритма закончено; ответ равен Y.
5. [Возвести Z в квадрат.] Установить Z ¬ Z * Z и вернуться в шаг 2.
Число умножений, необходимых для выполнения алгоритма, равно ëlog2 nû + j(n), где j (n) – число единиц в двоичном представлении числа n. Это на одно умножение больше, чем в бинарном методе, основанном на считывании “слева направо”, о котором шла речь в начале пункта, вследствие того факта, что первое выполнение шага 3 состоит просто-напросто в умножении на 1.
Предположим вновь, что имеется сравнение
a º b (mod m).
Как мы только, что выдели можно умножить это сравнение на себя, получив
a2 º b2 (mod m).
Вообще можно, умножив это сравнение на себя нужное количество раз, получить
an º bn (mod m)
для любого целого положительного числа n.
Многие результаты теории сравнений связаны с остатками высоких степеней чисел, поэтому покажем, как можно продолжить процесс возведения в степень. Предположим, например, что мы хотим найти остаток сравнения
389 (mod 7).
Одним из путей для выполнения этого является повторное возведеие в квадрат. Для возведения в степень воспользуемся вышеприведенным алгоритмом. Запишем показатель степени в двоичной системе счисления: 8910 = 10110012. Поэтому, правило вычисления будет следующим: S SX SX S S SX. Последовательно находим:
3 º 3 (mod 7),
32 º 9 º 2 (mod 7),
34 º 4 (mod 7),
35 º 12 º 5 (mod 7),
310 º 25 º 4 (mod 7),
311 º 12 º 5 (mod 7),
322 º 25 º 4 (mod 7),
344 º 16 º 2 (mod 7),
388 º 4 (mod 7),
389 º 12 º 5 (mod 7).
Таким образом, 389 mod 7 = 5.
– Конец работы –
Эта тема принадлежит разделу:
МЕТОДЫ И СРЕДСТВА ЗАЩИТЫ КОМПЬЮТЕРНОЙ ИНФОРМАЦИИ
Факультет электронной техники... Кафедра Автоматизированные системы обработки информации и управления...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Вычисление степеней, возведение сравнений в степень
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
| Твитнуть |
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Реклама
Информация в виде рефератов, конспектов, лекций, курсовых и дипломных работ имеют своего автора, которому принадлежат права. Поэтому, прежде чем использовать какую либо информацию с этого сайта, убедитесь, что этим Вы не нарушаете чье либо право.
© copyright 1999 - 2024 allRefs.net. Все права защищены. Страница сгенерирована за: 0.019 сек.
Новости и инфо для студентов