Power of n and nth root of multi-digit numbers based on recurrent relations

Power of n and nth root of multi-digit numbers based on recurrent relations

It is described the method of raising to a power of n and the method of getting nth root of multi-digit numbers basing on recurrent relations. Described methods are general methods of square, cube and general methods of square, cube roots. The method of getting nth root of multi-digit numbers is bas...

Повний опис

Збережено в:
Бібліографічні деталі
Дата:2017
Автор: Tereshchenko, A.N.
Формат: Стаття
Мова:rus
Опубліковано: Інститут програмних систем НАН України 2017
Теми:
Онлайн доступ:https://pp.isofts.kiev.ua/index.php/ojs1/article/view/135
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:Problems in programming

Репозитарії

Problems in programming
id pp_isofts_kiev_ua-article-135
record_format ojs
resource_txt_mv ppisoftskievua/1c/2b13a9de003fa5c5d6843848bca82f1c.pdf
spelling pp_isofts_kiev_ua-article-1352024-12-15T19:07:12Z Power of n and nth root of multi-digit numbers based on recurrent relations Возведение в степень n и вычисление корня степени n больших чисел на основе рекуррентных соотношений Піднесення до степеня n та обчислення кореня степені n великих чисел на основі рекурентних співвідношень Tereshchenko, A.N. УДК 519.6 It is described the method of raising to a power of n and the method of getting nth root of multi-digit numbers basing on recurrent relations. Described methods are general methods of square, cube and general methods of square, cube roots. The method of getting nth root of multi-digit numbers is based on the method of getting power of n. The method of getting nth root does not use trivial division. While nth root and power of n of multi-digit numbers are calculated the powers up to n-1 are cal-culated at the same time. The methods are bitrate where next bit (n bits – on getting nth root) of original bit sequence is handled on iteration. Описываются метод возведения в степень n и метод вычисления корня степени n больших чисел на основе рекуррентных соотношений. Описанные методы являются обобщением методов возведения в степени 2, 3 и методов вычисления квадратного и кубического корней. Метод вычисления корней степени n больших чисел основан на методе вычисления степени n. Метод вычисления корней степени n не использует операции деления. При возведении большого числа X в степень n или вычислении корня степени n одновременно с нахождением результата вычисляются значения всех степеней до n-1. Методы являются побитовыми, где на каждой итерации обрабатывается следующий бит (n бит − при вычислении корня) исходной битовой последовательности. Описується метод піднесення до степеня n та метод обчислення кореня степені n великих чисел на основі рекурентних співвідношень. Описані методи є узагальненням методів піднесення до степенів 2, 3 і методів обчислення квадратного та кубічного коренів. Метод обчислення кореня степені n великих чисел оснований на методі обчислення степені n. Метод обчислення кореня степені n не використовує операції ділення. При піднесення великого числа X до степені n та обчисленні кореня степені n одночасно зі знаходженням результату обчислюється значення всіх степенів до n-1. Методи є побітовими, де на кожній ітерації оброблюється наступний біт (n біт − при обчисленні кореня) початкової бітової послідовності. Інститут програмних систем НАН України 2017-06-14 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/135 PROBLEMS IN PROGRAMMING; No 2 (2015) ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 2 (2015) ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 2 (2015) 1727-4907 rus https://pp.isofts.kiev.ua/index.php/ojs1/article/view/135/128 Copyright (c) 2017 ПРОБЛЕМИ ПРОГРАМУВАННЯ
institution Problems in programming
baseUrl_str https://pp.isofts.kiev.ua/index.php/ojs1/oai
datestamp_date 2024-12-15T19:07:12Z
collection OJS
language rus
topic

spellingShingle

Tereshchenko, A.N.
Power of n and nth root of multi-digit numbers based on recurrent relations
topic_facet


УДК 519.6
format Article
author Tereshchenko, A.N.
author_facet Tereshchenko, A.N.
author_sort Tereshchenko, A.N.
title Power of n and nth root of multi-digit numbers based on recurrent relations
title_short Power of n and nth root of multi-digit numbers based on recurrent relations
title_full Power of n and nth root of multi-digit numbers based on recurrent relations
title_fullStr Power of n and nth root of multi-digit numbers based on recurrent relations
title_full_unstemmed Power of n and nth root of multi-digit numbers based on recurrent relations
title_sort power of n and nth root of multi-digit numbers based on recurrent relations
title_alt Возведение в степень n и вычисление корня степени n больших чисел на основе рекуррентных соотношений
Піднесення до степеня n та обчислення кореня степені n великих чисел на основі рекурентних співвідношень
description It is described the method of raising to a power of n and the method of getting nth root of multi-digit numbers basing on recurrent relations. Described methods are general methods of square, cube and general methods of square, cube roots. The method of getting nth root of multi-digit numbers is based on the method of getting power of n. The method of getting nth root does not use trivial division. While nth root and power of n of multi-digit numbers are calculated the powers up to n-1 are cal-culated at the same time. The methods are bitrate where next bit (n bits – on getting nth root) of original bit sequence is handled on iteration.
publisher Інститут програмних систем НАН України
publishDate 2017
url https://pp.isofts.kiev.ua/index.php/ojs1/article/view/135
work_keys_str_mv AT tereshchenkoan powerofnandnthrootofmultidigitnumbersbasedonrecurrentrelations
AT tereshchenkoan vozvedenievstepenʹnivyčisleniekornâstepeninbolʹšihčiselnaosnoverekurrentnyhsootnošenij
AT tereshchenkoan pídnesennâdostepenântaobčislennâkorenâstepenínvelikihčiselnaosnovírekurentnihspívvídnošenʹ
first_indexed 2025-07-17T10:04:08Z
last_indexed 2025-07-17T10:04:08Z
_version_ 1838410461871079424
fulltext Теоретичні та методологічні основи програмування © А.Н. Терещенко, 2015 ISSN 1727-4907. Проблеми програмування. 2015. № 2 13 УДК: 519.6 А.Н. Терещенко ВОЗВЕДЕНИЕ В СТЕПЕНЬ n И ВЫЧИСЛЕНИЕ КОРНЯ СТЕПЕНИ n БОЛЬШИХ ЧИСЕЛ НА ОСНОВЕ РЕКУРРЕНТНЫХ СООТНОШЕНИЙ Описываются метод возведения в степень n и метод вычисления корня степени n больших чисел на ос- нове рекуррентных соотношений (n>1). Описанные методы являются обобщением методов возведения в степени 2, 3 и методов вычисления квадратного и кубического корней. Метод вычисления корней степени n больших чисел основан на методе вычисления степени n. Метод вычисления корней степени n не использует операции деления. При возведении большого числа X в степень n или вычислении кор- ня степени n одновременно с нахождением результата вычисляются значения всех степеней до n-1. Ме- тоды являются побитовыми, где на каждой итерации обрабатывается следующий бит (n бит − при вы- числении корня) исходной битовой последовательности. Введение Криптографические операции осно- ваны на элементарных операциях таких, как сложение, умножение, возведение в степень больших чисел, получение остатка по модулю большого числа и т. д. Длина секретного ключа влияет на криптостой- кость ассиметричных криптографических программно-аппаратных комплексов. В свою очередь длина ключа влияет на быстродействие всей системы, поэтому выбор длины ключа зависит от быстродей- ствия каждой криптографической опера- ции, а значит, зависит и от быстродействия элементарных арифметических операций, на основе которых построены криптогра- фические операции. Оптимизации быстро- действия элементарных операций таких, как умножение больших чисел, возведение в степень по модулю большого числа и т. д. уделяется много внимания [1–4]. Цель работы – обобщение для лю- бой степени n выше третей метода [5] возведения в квадрат и куб большого чис- ла, а также метода вычисления квадрат- ного и кубического корней больших чисел без использования каких-либо операций деления (практический диапазон > 1024 битовых разрядов). Постановка задачи Пусть , 0m n  – целые числа, поло- жительное число U представлено m бита- ми, а число W представлено mn  битами:     1 0 2 m j j jm uU ,      1 0 2 mn j j jmn wW . Возведение числа mU длиной в m бит в степень n и вычисление корня сте- пени n числа mnW  длиной в mn  бит можно представить следующим образом:       n mm n m uUU 11 2          n i ii m in m i n uUC 0 11 2 ,    n n mm n mn VRW     n n mmm vVR 11 2    n n i ii m in m i nm vVCR       0 11 2 , где )!(! ! ini n Сi n   ,      2 0 1 2 m j j jm uU ,      2 0 1 2 m j j jm vV ,     1 0 2 m j j jm rR . На основании вышеприведенных методов построим итерационные по- битовые алгоритмы. 1. Возведение в любую степень n  nmU числа mU длиной в m бит. Теоретичні та методологічні основи програмування 14 2. Вычисление целочисленных кор- ня mV и остатка mR с длинами в m бит любой степени n числа mnW  длиной в mn  бит без использования деления. Провести анализ сложности по чис- лу битовых операций этих алгоритмов. Определения и обозначения Большими числами будем называть числа, длина которых в битах превышает разрядность машинного слова, то есть свыше 32 бит. Для реализации операций с такими числами обычный набор команд процессора недостаточен и необходимо использование специальных алгоритмов и методов. В данной работе большие числа представлены в виде битовых последова- тельностей. Далее в тексте под обработкой битовых последовательностей подразуме- вается обработка больших чисел. Для лучшего представления матери- ала предлагается обратная нумерация би- тов в последовательности. В этом случае индекс самого старшего бита равен нулю, а индекс самого младшего бита равен длине последовательности в битах минус 1. Такое представление удобно, так как анализ начинается со старшего бита, а длина последовательности не важна, так как к проанализированной битовой после- довательности могут добавляться младшие биты. Такой подход является одним из преимуществ использования данного ме- тода, так как он дает возможность полу- чить при необходимости точность вычис- ления больше заданной при нахождении корней больших степеней от больших чи- сел, используя один и тот же алгоритм. Таким образом, битовая последова- тельность записывается в обычном поряд- ке, т. е. самый старший бит располагается слева, и в этом случае младшие биты до- бавляются с правой стороны. Далее приве- ден пример битовой последовательности длиной в 8 бит: 76543210 xxxxxxxx , что равносильно выражению:  4 3 5 2 6 1 7 0 2222 xxxx 06 2 5 3 4 222 xxxx  . Введем следующие обозначения. 10121 , 21111001  представление числа 121 в десятичной и двоичной системах счисле- ния. i  номер итерации, нумерация начинают- ся с нуля ( 0i ). iX  битовая последовательность. iY  квадрат последовательности iX . iZ  куб последовательности iX . iii ZYX ,, , 0i ,  битовые последователь- ности длиной в 1i , )1(2 i и )1(3 i бит, соответственно. Длины последовательнос- тей 0Y и 0Z равны 1 и являются исключе- ниями. iii ZYX ,, вычисляются на итерации i на основе 111 ,,  iii ZYX , полученных на предыдущей 1i итерации. jjj zyx ,,  j -ые биты в последовательно- стях ZYX ,, соответственно. 0ix  операция сравнения выражений с левой и правой сторон. Можно записать следующие выра- жения для квадрата и куба числа X : ...3210 xxxxX  , ...76543210 2 yyyyyyyyYX  , ...11108876543210 3 zzzzzzzzzzzzZXYX  1,0  mi  индексу i последовательно присваиваются значения 0, 1, …, 1m , m . 1ix  операция присвоения зна- чения выражению с левой стороны значе- ния с правой стороны. Необходимо отли- чать от операции 1ix , где значения с ле- вой и правой сторон не изменяются по за- вершению операции. В выражении 1 ii значение i увеличивается на 1 после окончания операции. Знак  может использоваться несколько раз в одной опе- рации для того, чтобы сократить запись и показать, что одинаковые значения при- сваиваются различным элементам. Так две операции 10 X , 10 Y можно заменить Теоретичні та методологічні основи програмування 15 одной 100  YX . Символы  и  также могут использоваться одновременно в одной операции: 2102 1015122 X , что обо- значает вычисление выражения 122  , результат которого 105 , 2101 представлен в двух системах счисления, и которое запи- сывается в 2X .      .124;12:1 .4;2:0 101011 01011 XYYXXx YYXXx  операция вычисления выражений по условию. Если 1 0x  , то выполняются операции 1 0 2X X  ; 401 YY . Если 1 1x  , то выполняются операции 1 0 2 1X X   ; 1 0 14 2 1Y Y X     . Порядок выполнения операций в выражениях (формулах, алгоритмах и таб- лицах) определяется символами ‘;‘ и ‘,‘. Выражение разбивается на группы символом ‘;‘. Последовательность групп в выражение выполняется в обычном поряд- ке  слева направо. Операции внутри груп- пы разделяются запятой и выполняются в обратном порядке – справа налево. Если операцию обозначить номером ее выпол- нения, то получим строку, определяющую порядок выполнения операций: 2, 1; 6, 5, 4, 3; 8, 7. Выражения далее отличаются: 0i ; 1ix , 1i . 0i , 1ix ; 1i . В первом выражении значение один присвоится элементу с индексом 1, а во втором  с индексом 0, так как порядок выполнения операций отличается: 1; 3, 2. 1, 2; 3. Возведение в квадрат и вычисление квадратного корня Возведение в квадрат. Рассмотрим последовательное по- лучение формул для вычисления битовых последовательностей iX и iY , 1,0  mi . Рассмотрим возведения в квадрат 1-битового числа 0x )0( i . Начальная итерация: 00 xX  ,   0 2 0 2 00 xxXY  . Добавим к биту 0x справа младший бит 1x и рассмотрим формулы для вычис- ления квадрата из полученной битовой по- следовательности ( 1i ): 10101 2 xXxXX  , (1)      2 10 2 10 2 11 2 xXxXXY  2 110 2 0 224 xxXX    100 1224 xXY   110 1)22(4 xXY  . Окончательно получаем: 1 0 1 14 (2 1)Y Y X x      . (2) Для различных значений 1x , форму- лы (1), (2) принимают следующий вид:      .124;12:1 .4;2:0 101011 01011 XYYXXx YYXXx (3) Обратим внимание, что в формуле (1) коэффициенты 4 и 2 в выражении 124 101  XYY стоят с разных сто- рон: «4» показывает сдвиг на 2 бита, при этом «2» является коэффициентом при 1X . Такая запись используется далее, чтобы отделить битовые сдвиги от коэффициен- тов при анализе полученных выражений. Рассмотрим возведение в квадрат 3- битовой последовательности 210 xxx , т. е. добавим еще один младший разряд справа ( 2i ): 212102102 22 xXxxxxxxX  ,  2 21 2 210 2 22 )2()( xXxxxXY  2 221 2 1 224 xxXX  211 )122(4 xXY 221 )12(4 xXY  . (4) Окончательно получаем: 2 1 2 24 (2 1)Y Y X x      . Теоретичні та методологічні основи програмування 16 У предыдущего выражения все ин- дексы больше на 1 по сравнению с (2). По аналогии с формулами (4) для битовой последовательности 3210 xxxx можно получить формулы для 3X и 3Y : 3232103 2 xXxxxxX  , 3223 )12(4 xXYY  . Для вычисления 1mY воспользуем- ся рекуррентными соотношениями. Лемма 1. Битовые последователь- ности iY , 1,0  mi можно получить на основе 1iX , 1iY и бита ix : iiiii xXxxxxX   2... 1110 , iiii xXYY   )12(41 , 1,0  mi . Доказательство. Добавим к бито- вой последовательности 1iX справа бит ix по аналогии с (4): iiiii xXxXX   211 ,   2 1 2 1 2 )2()( iiiiii xXxXXY   2 1 2 1 224 iiii xxXX iii xXY   )122(4 11 . Окончательно получаем: iiii xXYY   )12(41 . Лемма доказана. Возведение в квадрат битовой по- следовательности 32103 xxxxX  можно представить в виде следующих последова- тельных шагов: 010 0xyy  , 10103210 01000 xxyyyyyy  , 2103210543210 010000 xxxyyyyyyyyyy  , 76543210 yyyyyyyy 3210543210 0100000 xxxxyyyyyy  . (5) На каждом шаге второе слагаемое равно нулю, если младший бит нулевой. Более удобно выражения (5) представля- ются в виде классического столбика, пока- занного на рис. 1. 76543210 3210 210 10 0 0 0 0 0 yyyyyyyy xxxx xxx xx x  Рис. 1. Схема возведение в квадрат на основе предложенного метода Согласно выражений (5) строка со- стоит из нулей, если бит 0ix . На рис. 2 показан пример возведение в квадрат чи- сел 1110=10112 и 1510=11112 : 1 1 0 1 10011110 10101 1001 000 10 3 2 1 0      x x x x 1 1 1 1 10000111 10111 1011 101 10 3 2 1 0      x x x x Рис. 2. Примеры вычисления квадрата на основе предложенного метода Алгоритм 1. Пошаговое описание алгоритма возведения в квадрат (табл. 1). ВХОД: X – битовая последова- тельность, m – длина последовательности X ( 2m ). ВЫХОД: 2XY  ( 2 ii XY  , 1,0  mi ). 1. Найти самый старший ненулевой бит последовательности ...3210 xxxxX  . 2. Начальная итерация 0i ; 100 YX . 3. 1 ii . 4. Найти iX на основе значения ix : Теоретичні та методологічні основи програмування 17        .2:1 .2:0 1 1 iiii iii xXXx XXx 5. Найти iY на основе значения ix (см. (3)):        .124:1 .4:0 1 1 iiii iii XYYx YYx 6. Если бит ix не последний, то перейти к шагу 3. Таблица 1. Пример выполнения Алгоритма 1 при вычислении квадрата числа 1011 21011 (см. рис. 2) Шаг Операция 1 Старший бит ненулевой 2 0i ; 100  YX 3 1i 4;5 Так как 01 x , то 2101 10221 X ; 2101 100441 Y 6 Бит 1x не последний, перейти к шагу 3 3 2i 4; 5 Так как 12 x , то 2 10 22 2 1 5 101X      ; 2 10 24 4 2 5 1 25 11001Y        6 Бит 2x не последний, перейти к шагу 3 3 3i 4;5 Так как 13 x , то 3 10 25 2 1 11 1011X      ; 3 1025 4 2 11 1 121Y        21111001 6 Бит 3x последний, завершить рабо- ту алгоритма Вычисление квадратного корня. Для вычисления корней небольших чисел с допустимой погрешностью достаточно небольшое число итераций. Для получе- ния корней больших чисел известными методами необходимо многошаговое вы- числение с использованием операций умножения, деления больших чисел, вы- числения факториала и т. д., что услож- няет по времени операцию вычисления корней. Алгоритм 2 вычисления квадратно- го корня похож на Алгоритм 1 возведения в квадрат, за исключением того, что про- исходит последовательное вычитание из последовательности 765432103 yyyyyyyyY  вместо добавления. Схема позволяет найти остаток 33 XR  , где 32103 xxxxX  , 3 0 1 2 3 4 5 6 7R r r r r r r r r . Алгоритм 2. Пошаговое описание алгоритма вычисления квадратного корня. ВХОД: Y – битовая последователь- ность, m – длина последовательности Y ( 3m ). ВЫХОД:  2 YX  , 2XYR  (  2 ii YX  ,  2iii XYR  ,         2 1 ,0 m i ). iR  промежуточная битовая последова- тельность длиной в  12 i бит на каждой итерации i . 1. Если длина битовой последовательности Y не делится на 2 нацело, то добавить старший нулевой бит слева. Разбить по- следовательность ...76543210 yyyyyyyyY  . на пары бит. 2. Найти самую старшую ненулевую бито- вую пару. 3. Начальная итерация 0i ; 100  xX , 100 yyR  ; 000 XRR  (см. рис. 3, 4). 4. 1 ii . 3 2 1 0 76543210 3210 210 10 0 76543210 0 0 0 0 x x x x rrrrrrrr xxxx xxx xx x yyyyyyyy      Рис. 3. Схема вычисления квадратного корня 76543210 yyyyyyyy Теоретичні та методологічні основи програмування 18 1 1 0 1 0100 10101 1001 000 10 11011110 3 2 1 0      x x x x Рис. 4. Пример вычисления квадратного корня числа 12310 5. 121  ii XX . 6. 12  ii XdY . 7. 1221 4   iiii yyRR 8. Если ii dYR  , то 1ix , iii dYRR  , иначе 0ix (см. рис. 3, 4). 9. Если биты 122 ii yy не последние, то пе- рейти к шагу 4. По окончании алгоритма iX будет содержать целую часть от квадратного корня, а iR  остаток (табл. 2). Таблица 2. Пример выполнения Алгорит- ма 2 при вычислении квадратного корня числа 10 2123 1111011 (см. рис. 4) Шаг Операция 1 2 1 Добавить старший нулевой бит слева и разбить последовательность Y 11101101 на пары бит 2 Самая старшая битовая пара нену- левая 3 Начальная итерация 0i ; 100  xX ; 1020 101 R ; 0110 R 4 1i 5 2101 113121 X 6 2101 1015132 dY 7 2101 113340 R 8 Так как 53 , то 01 x ( 21 X ) 9 Биты 42yy не последние, перейти к шагу 4 Окончание табл. 2 1 2 4 2i 5 2102 1015122 X 6 2102 10019152 dY 7 2102 111014243 R 8 Так как 914 , то 12 x , 2102 1015914 R 9 Биты 54yy не последние, перейти к шагу 4 4 3i 5 2103 101111125 X 6 3 10 22 11 1 21 10101dY      7 3 10 25 4 3 23 10111R      8 Так как 2123 , то 13 x , 2103 1022123 R 9 Биты 76 yy последние, завершить работу алгоритма Возведение в куб и вычисление кубического корня Возведение в куб. Рассмотрим по- следовательное получение формул для вы- числения битовых последовательностей iX и iZ , 1,0  mi . Начнем рассмотрение с возведения в куб 1-битового числа 0x )0( i . Началь- ная итерации будет следующей: 00 xX  ,   0 2 0 2 00 xxXY  ,   0 3 000 3 00 xxXYXZ  . Рассмотрим формулу для получе- ния куба из 1X )1( i :  3 10 3 10 3 11 )2()( xXxXXZ  3 1 2 101 2 0 3 0 23438 xxXxXX  110100 23438 xxXxYZ    1000 123438 xXYZ            1 0 00 0 1)12(3 12243 8 x X XY Z Теоретичні та методологічні основи програмування 19    11100 1312438 xXXYZ  . С учетом формулы (2) окончатель- но получаем: 11101 )133(8 xXYZZ  . (6) Рассмотрим получение куба 3-бито- вой последовательности 210 xxx , т. е. доба- вим еще один младший разряд справа )2( i :  3 21 3 210 3 22 )2()( xXxxxXZ  3 2 2 212 2 1 3 1 23438 xxXxXX    2111 123438 xXYZ 1 1 1 2 1 3 4 3 4 3 8 3 2 3 1 Y X Z x X                    . Окончательно получаем формулу, похожую на (6): 22212 )133(8 xXYZZ  . По аналогии с предыдущей форму- лой можно получить формулы для битовой последовательности 3210 xxxx для 3Z )3( i : 33323 )133(8 xXYZZ  . Лемма 2. Битовые последователь- ности iZ , 1,0  mi можно получить из битовых последовательностей 1iX , 1iY , 1iZ и бита ix , используя следующие формулы: iiiii xXxxxxX   2... 1110 , iiii xXYY   )12(41 , iiiii xXYZZ   )133(81 , 1,0  mi . Доказательство. Добавим к бито- вой последовательности 1iX справа ix . Выражение iiii xXYY   )12(41 сле- дует из леммы 1. Находим формулу для куба новой последовательности аналогично (6):   3 1 3 1 3 )2()( iiiiii xXxXXZ   32 1 2 1 3 1 23438 iiiiii xxXxXX     iiii xXYZ 123438 111             i i ii i x X XY Z 1323 34343 8 1 1 1     i i ii i x X XY Z            1123 1223 8 1 1 . Окончательно получаем: iiiii xXYZZ   )133(81 . Лемма доказана. Алгоритм 3. Пошаговое описание алгоритма вычисления куба числа. ВХОД: X – битовая последова- тельность, m – длина последовательности X ( 2m ). ВЫХОД: 3XZ  , 2XY  ( 3 ii XZ  , 2 ii XY  , 1,0  mi ). 1. Найти самый старший ненулевой бит последовательности ...3210 xxxxX  . 2. Начальная итерация 0i ; 1000  ZYX . 3. 1 ii . 4. Найти iX на основе ix :        .2:1 .2:0 1 1 iiii iii xXXx XXx 5. Найти iY на основе ix :        .124:1 .4:0 1 1 iiii iii XYYx YYx 6. Найти iZ на основе ix :        .1338:1 .8:0 1 1 iiiii iii XYZZx ZZx 7. Если ix не последний бит, то перейти к шагу 3. Особенностью данного алгоритма является то, что параллельно с вычисле- нием куба числа находим также квадрат числа (табл. 3). Теоретичні та методологічні основи програмування 20 Таблица 3. Пример выполнения Алгоритма 3 при вычислении куба числа 10 211 1011 Шаг Операция 1 Старший бит ненулевой 2 0i ; 1000  ZYX 3 1i 4;5;6 Так как 01 x , то 2101 10221 X ; 2101 100441 Y ; 1 10 21 8 8 1000Z     7 Бит 1x не последний, перейти к шагу 3 3 2i 4;5;6 Так как 12 x , то 2102 1015122 X ; 2102 110012515244 Y ;  )153253(882Z 10 2125 1111101  7 Бит 2x не последний, перейти к шагу 3 3 3i 4;5;6 Так как 13 x , то 2103 101111125 X ;  103 1211112425Y 21111001 ;  )11131213(81253Z 10 21331 10100110011  7 Бит 3x последний, завершить ра- боту алгоритма Сравнивая Алгоритм 1 (табл. 1) и Алгоритм 3 (табл. 3) можно заметить, что каждая итерация i Алгоритма 3 имеет на один шаг больше. Алгоритм 4. Пошаговое описание алгоритма вычисления кубического корня. ВХОД: Z – битовая последова- тельность, m – длина последовательности Z ( 4m ). ВЫХОД:  3 ZX  , 2XY  , 3XZR  (  3 ii ZX  ,  3 ii YX  , 3 iii XZR  ,         3 1 ,0 m i ). iR  промежуточная битовая последова- тельность длины в  13 i бит на каждой итерации. 1. Если длина битовой последовательности Z не делится на 3 нацело, то добавляются старшие нулевые биты слева. Разбить на тройки бит ...876543210 zzzzzzzzzZ  . 2. Найти самую старшую ненулевую бито- вую тройку. 3. Начальная итерация 0i ; 100  Xx , 100  ZY , 2100 zzzR  ; 000 ZRR  . 4. 1 ii . 5. 121  ii XX . 6. 12  ii XdY ; iii dYYY   41 . 7. 133  iii XYdZ . 8. 231331 8   iiiii zzzRR . 9. Если ii dZR  , то 1ix , iii dZRR  , иначе 0ix , iii dYYY  (см. рис. 3, 4). 10. Если биты 23133  iii zzz не последние, то перейти к шагу 4. По окончании алгоритма iX будет содержать целую часть от кубического корня, а iR  остаток. Таблица 4. Пример выполнения Алгоритма 4 при вычислении кубического корня числа 3 10 2 10 101353 10101001001 (11 ) 2 11    Шаг Операции 1 2 1 Добавить старший нулевой бит слева и разбить 001001101010Z на тройки бит 2 Самая старшая битовая тройка ненулевая 3 Начальная итерация 0i ; 10 x , 1000  ZYX ; 1101020 R Теоретичні та методологічні основи програмування 21 Окончание табл. 4 1 2 4 1i 5 2101 113121 X 6 2101 1015132 dY ; 1 2 21 4 5 9 1001Y      7 1 10 23 9 3 5 1 13 1101dZ        8 1 10 21 8 5 13 1101R      9 Так как 1313 , то 01 x ( 21 X ), 1 10 29 5 4 100Y     10 Биты 543 zzz не последние, пе- рейти к шагу 4 4 2i 5 2 10 22 2 1 5 101X      6 2 10 22 5 1 9 1001dY      ; 2 2 24 4 9 25 11001Y      7 2 10 23 25 3 5 1 61 111101dZ        8 2 10 213 8 1 105 1101000R      9 Так как 61105 , то 12 x , 2 10 2105 61 44 101100R     10 Биты 876 zzz не последние, пе- рейти к шагу 4 4 3i 5 2103 101111125 X 6 3 10 22 11 1 21 10101dY      ; 3 2 225 4 21 121 1111001Y      7  111312133dZ 10 2331 101001011  8 3 10 244 8 1 353 101100001R      9 Так как 331353 , то 13 x , 3 10 2353 331 22 10110R     10 Биты 11109 zzz последние, завер- шить работу алгоритма Сравнивая Алгоритм 2 (табл. 2) и Алгоритм 4 (табл. 4) можно заметить, что каждая итерация i Алгоритма 4 имеет на один шаг больше. Возведение в степень n и вычис- ление корней степени n Возведение до степени n . Найдем сначала общую итерационную формулу для вычисления степени числа выше тре- тей. Теорема 1. Выражение nD nBA )(  вычисляется на основе значений меньших степеней 1nD , 2nD , ... , 2D , 1D и имеет вид:     n i ini n innn DCBABAD 1 1)1()( B DC DCDC A nn n n n n n nn               112 2211 )1()1( ... , где nDBA ,,, – целые числа, ,, BA 0, nD , )!(! ! ini n Ci n   , ...1  nn BB BB  2... . Доказательство. Найдем сначала выражения для 1 11    i n i n CC , 2,0  ni , в общем виде:    1 11 i n i n CC        ))!1(1()!1( )!1( )!1(! )!1( ini n ini n        )!()!1()1( )!1()1( )!1(!)1( )!1()1( iniin nin inii ni        )!1()!1( )!1()1( )!1(!)1( )!1()1( ini nin inii ni     )!1()!1( )!1())1()1(( ini nini     ))!1(()!1( )!1( ini nn 1 ))!1(()!1( !    i nC ini n . Выражение вида 11 11    i n i n i n CCC , 1,0  ni , соответствует значениям треу- гольника Паскаля для строк 1n и n . Найдем выражение для 1-й степени: BAD  . Найдем выражение для 2-й степени: Теоретичні та методологічні основи програмування 22  2222 2)( BABABAD BAA  )12(2 . Сделаем замену A на BD  : BDABBDA  )12()122( 22 . Найдем выражение для 3-й степени:  )(23 BADD  )())12(( 2 BABDA BDAABDA  )12()12( 23 . Сделаем замену A на BD  :  )()12(3 BDBDA  BDBBD )12()( 2  BBDDBDA 23 )()12(  BDDBDDA )12()2( 223 BDDA  )133( 23 . Используем методом математичес- кой индукции. Найдем выражение n -й степени на основании значения 1n -й степени:   )()( 1 BADBAD nn                             B DC DCDC A nn n n n n n nn 22 1 3 32 1 21 11 )1()1( ...                    AB DC DCDC A nn n n n n n nn 22 1 3 32 1 21 1 )1()1( ... B DC DCDC A nn n n n n n nn                            22 1 3 32 1 21 11 )1()1( ... . Сделаем замену A на BD  : nA                          )( )1( )1(.. 2 2 1 3 32 1 21 1 BDBDC DCDC n n n n n n n n                           BDC DCDC BA n n n n n n n n n 2 2 1 3 32 1 21 1 1 )1( )1(...                          B D DC DCDC A n n n n n n n n n 2 22 1 3 22 1 11 1 )1( )1(.. BAn  1 . С учетом того, что BBD n  1)( равносильно BD n  1)1( (  21 ... BBn B по условию), сделаем замену 1nA на 1)1(  nD и воспользуемся формулой Ньютона    n i ini n in DCD 0 )1()1( , )!(! ! ini n C i n   :                    B DDC DCDC A nn n n n n n nn 222 1 3 22 1 11 1 )1()1( ... B DC DCD nn n n n n n                   12 1 2 21 1 1 )1()1( ... . Сгруппируем по степени D : B DC DCC DCC DC A n n n n n n n n n n nn n n n                                         1 2 1 2 22 1 3 1 3 22 1 1 1 11 1 )1( )1()1( )()1( ...)( )1( . С учетом выражения  i nC 1 11 1    i n i n CC , 1,0  ni окончательно по- лучаем: B DC DC DCDC A nn n n n n n n n n n n                     112 223 2211 )1()1( )1( ... . Теорема доказана. Рассмотрим полученные выраже- ния: BAD  , BDAD  )12(22 , BDDAD  )133( 233 . Выражения для больших степеней находятся аналогично, используя треу- гольник Паскаля (см. рис. 5): Теоретичні та методологічні основи програмування 23 1721353521717 16152015616 151010515 146414 13313 1212 111 10 n Рис. 5. Вычисление треугольника Паскаля knС , , nk ,0 , 7,0n BDDDAD  )1464( 2344 , BDDDDAD  )1510105( 23455 , B DD DDD AD             1615 20156 2 345 66 , B DDD DDD AD             172135 35217 23 456 77 . Алгоритм 5. Пошаговое описание алгоритма вычисления степени n числа X (табл. 5). ВХОД: X – битовая последова- тельность, n – степень, m – длина после- довательности X ( 1m ). ВЫХОД: k k XD  , nk ,1 . 1. Найти самый старший ненулевой бит последовательности ...3210 xxxxX  . 2. Начальная итерация 0i : Для k от 1 до n . 3. 1kD . 4. Конец цикла по k . 5. Для i от 1 до 1m 6. 1b . 7. Для j от 1 до n 8. 2bb ; bDD jj  . 9. Если 0ix , то 10. 1sign , jC  . 11. Для k от 1j до 1 шаг 1 Таблица 5. Пример выполнения Алгоритма 5 при вычислении 4-й степени числа 10 25 101 Шаг Операция 1 2 1 Старший бит ненулевой 2;3;4 0i ; 14321  DDDD 5;6;7 1i ; 1b ; 1j 8 221 b ; 2211 D 9 Так как 02 x , то пропустить шаги 10–15 16;17;7 2j 8 210 100422 b ; 2103 100441 D 9 Так как 02 x , то пропустить шаги 10–15 16;17;7 3j 8 10 24 2 8 1000b    ; 3 10 21 8 8 1000D     9 Так как 02 x , то пропустить шаги 10–15 16;17;7 4j 8 10 28 2 16 10000b    ; 4 10 21 16 16 1000D     Теоретичні та методологічні основи програмування 24 Продолжение табл. 5 1 2 9;16;17 Так как 02 x , то пропустить шаги 10–15 5;6;7 2i ; 1b ; 1j 8 221 b ; 2101 100422 D 9 Так как 03 x , то продолжить следующий шаг 10 10 1sign , 1C 11 Так как 1011 k , то про- пустить шаги 1214 15 2101 1015114 D 16;17;7 2j 8 10 22 2 4 100b    ; 2 10 24 4 16 10000D     9 Так как 03 x , то продолжить следующий шаг 10 10 1sign , 2C 11 Так как 1112 k , то про- должить шаг 12 12 2 10 216 1 2 5 26 11010 ;D       1 )112( 12    C 13 1sign 14;15 2 10 226 1 1 25 11001D      16;17;7 3j 8 10 24 2 8 1000b    ; 3 10 28 8 64 1000000D     9 Так как 03 x , то продолжить следующий шаг 10 10 1sign , 3C 11 Так как 1213 k , то про- должить шаг 12 12 3 1064 1 3 25 139D       210001011 ; 3 )123( 23    C 13 1sign 11 Так как 1k , то продолжить шаг 12 Окончание табл. 5 1 2 12 3 10139 1 3 5 124D       21111100 ; 1 )113( 13    C 13 1sign 14;15 3 10 2124 1 1 125 1111101D      16;17;7 4j 8 10 28 2 16 10000b    ; 4 10 216 16 256 100000000D     9 Так как 03 x , то продолжить следующий шаг 10 10 1sign , 4C 11 Так как 1314 k , то про- должить шаг 12 12  125412564D 10 2756 1011110100  ; 6 )134( 34    C 13 1sign 11 Так как 12 k ,то продолжить шаг 12 12  25617564D 10 2606 1001011110  ; 4 )124( 26    C 13 1sign 11 Так как 11k ,то продолжить шаг 12 12  5416064D 10 2626 1001110010  ; 1 )114( 14    C 13 1sign 14;15 4 10626 1 1 625D      21001110011 16;17;18 Завершить работу алгоритма Теоретичні та методологічні основи програмування 25 12. kjj DCsignDD  ; )1(    kj kC C . 13. signsign  . 14. Конец цикла по k . 15. 1 signDD jj . 16. Конец если. 17. Конец цикла по j . 18. Конец цикла по i . По завершении алгоритма 51 D , 252 D , 1253 D , 6254 D . Оптимизация за счет исключе- ния операций деления. Значения коэф- фициента С – небольшие числа в табл. 5. Если значения С вычислить раньше, то можно исключить часть операций умно- жения и все операции деления в табл. 5. На Шаге 12 Алгоритма 5 выражение )1(    kj kC C можно избежать, исполь- зуя коэффициент kjC , в выражении kkjjj DCsignDD  , , где j , k – номе- ра строки и элемента строки в треуголь- нике Паскаля (см. рис. 5), что исключает операции деления в Алгоритме 5. Далее в табл. 6 показаны наиболь- шие значения коэффициентов в каждой строке треугольника Паскаля (см. рис. 5). С учетом того, что 322 4294967296 , можно утверждать, что 32 2 1 , 2       n n C при 34n в табл. 6. Возведение в степень n числа вычисляется на основании меньших степеней 1n , 2n , … 2, 1, 0, то при возведении в степень 35n умножение на 1, kjC в Алгоритме 5 является одно- словной операцией, что значительно уменьшает сложность по числу однослов- ных операций. Из табл. 6 также видно, что при возведении в степень до 5n значе- ния коэффициентов очень маленькие: 1, 2, 3, 4, 5, 6, …. В этом случае операций умножения можно избежать полностью, заменив их несколькими дополнительны- ми операциями многословного сложения. Анализ сложности по числу би- товых операций. Довольно непросто найти общую сложность Алгоритма 5, так как присутствуют битовые операции сдви- га, побитового сложения и вычитания, ум- ножения однословного числа на битовую последовательность. Попробуем вычис- лить число битовых операций и операций умножения на однословное число. Лемма 3. Число операций одно- словного умножения в Алгоритме 5 можно выразить следующей формулой 2 )1( mn n   , где m – длина в битах после- довательности, которая возводится в сте- пень n . Таблица 6. Наибольшее значение        2 1 , n n C в каждой строке треугольника Паскаля (рис. 5) n Значение n Значение n Значение n Значение 0 1 10 252 20 184756 30 155117520 1 1 11 462 21 352716 31 300540195 2 2 12 924 22 705432 32 601080390 3 3 13 1716 23 1352078 33 1166803110 4 6 14 3432 24 2704156 34 2333606220 5 10 15 6435 25 5200300 35 4537567650 6 20 16 12870 26 10400600 36 9075135300 7 35 17 24310 27 20058300 8 70 18 48620 28 40116600 9 126 19 92378 29 77558760 Теоретичні та методологічні основи програмування 26 Доказательство. Строки 1,0n содержат единицы, которые заменяются операцией сложения, поэтому эти строки не рассматриваются. Анализируя Алго- ритм 5 и треугольник Паскаля, очевидно, что коэффициенты со строки 2n тре- угольника Паскаля при возведении в сте- пень 4 например, будут использоваться три раза. С учетом того, что первый и по- следний коэффициенты – единицы, сле- дующее выражение описывает число од- нословных операций при возведении в 2, 3, 4, 5-ю степени: 2-я степень: mm 11  ; 3-я степень: mm 3)21(  ; 4-я степень: mm 6)321(  ; 5-я степень: mm 10)4321(  ; 6-я степень: mm 15)54321(  ; где m – длина битовой последовательно- сти. Коэффициенты при m описывают- ся формулой 2 )1( n n  для арифметичес- кой прогрессии. Умножив на m , получаем искомое выражение. Лемма доказана. Лемма 4. Число операций битового сложения и вычитания в Алгоритме 5 мож- но выразить следующей формулой: m m m n n    2 )1( 2 )1( , где m – длина в битах последовательнос- ти, которая возводится в степень n . Доказательство. Битовая последо- вательность длины m при возведении в степень n будет иметь длину nj бит. С учетом того, что значение nD может быть получены на основе значений меньших степеней 1nD , 2nD , …, D , 1 (согласно теоремы 1) и, рассматривая шаги 11–14, число бытовых операций сложения и вы- читания можно выразить формулой для арифметической прогрессии: 1 2 )1(  m n n . Рассмотрим число операций для различных длин m : 1m : 11 2 )1(  n n . 2m : 12 2 )1(  n n . …. 1m : 1)1( 2 )1(  m n n . m : 1 2 )1(  m n n . Не учитывая второе слагаемое +1, видим, что значения формируют также арифметическую прогрессию с постоян- ным коэффициентом 2 )1( n n  . Сумма та- ких значений может быть выражена сле- дующей формулой: m m m n n    2 )1( 2 )1( . Лемма доказана. Вычисление корня n -й степени. Алгоритм 6. Пошаговое описание алгоритма вычисления корня n -й степени числа Q (табл. 7). ВХОД: Q – битовая последова- тельность, n – степень ( 0n ), m – длина последовательности Q ( nm  ). ВЫХОД:  n QD 1 ;  1 k kD D , nk ,2 ;  nDQR 1  остаток. iR  промежуточная битовая последова- тельность длиной в  1in бит на каждой итерации i . 1. Если длина последовательности Q не делится на n нацело, то добавляются n n m m        старших нулевых бит слева. Разбить ......... 121110  nnnn qqqqqqQ на секции длиной в n бит. 2. Найти самую старшую ненулевую бито- вую секцию. 3. Начальная итерация 0i :Для k от 1 до n . 4. 1kD . 5. Конец цикла по k . Теоретичні та методологічні основи програмування 27 6. 1100 ...  nqqqR ; 0 0 nR R D  . 7. Для i от 1 до        n m 1 . 8. 2b ; bDD  11 ; 111 DT . 9. Для j от 2 до n 10. 2bb ; bDD jj  ; jj DT  . 11. 1sign . 12. Для k от 1j до 1 шаг 1 13. kkjjj TCsignTT  , . 14. signsign  . 15. Конец цикла по k . 16. 1 signTT jj . 17. Конец цикла по j . 18. 111 ....   nnininiii qqqbRR . 19. Если ni TR  , то 20. nii TRR  ; 0nT . 21. Для j от 1 до n 22. jj TD  . 23. Конец цикла по j . 24. Конец если. 25. Конец цикла по i . Таблица 7. Пример выполнения Алгорит- ма 6 при вычислении корня 4-ой степени числа 4 10 2 10 10640 1010000000 (5 ) 3 5    , 10m , 4n Шаг Операция 1 2 1 Длина последовательности 21010000000 не кратна четы- рем. Добавить два старших ну- левых бита 2001010000000 2; 3; 4 0i ; 14321  DDDD 5; 6 1020 20010 R ; 1120 R 7 1i 8 2b ; 211 D ; 2101 11312 T 9 2j Продолжение табл. 7 1 2 10 210 100422 b ; 2 10 21 4 4 100D     ; 42 T 11 1sign 12 1k 13 2 10 24 1 2 3 10 1010T       ( 22,2 C ) 14 1sign 15; 16 2102 100191110 T 17; 9 3j 10 10 24 2 8 1000b    ; 2103 1000881 D ; 83 T 11 1sign 12 2k 13 3 10 28 1 3 9 35 100011T       ( 33,3 C ) 14 1sign 12 1k 13 3 10 235 1 3 3 26 11010T       ( 32,3 C ) 14 1sign 15;16 3 10 226 1 1 27 11011T      17; 9 4j 10 10 28 2 16 10000b    ; 4 10 21 16 16 10000D     ; 164 T 11 1sign 12 3k 13  104 124274116T 21111100 ( 44,4 C ) 14 1sign 12 2k 13  104 70961124T 21000110 ( 63,4 C ) 14 1sign 12 1k 13 4 10 270 1 4 3 82 1010010T       ( 42,4 C ) Теоретичні та методологічні основи програмування 28 Продолжение табл. 7 1 2 14 1sign 15; 16 4 10 282 1 1 81 1010001T      17; 18 2 2 10 22 16 1000 40 11000R      19 Так как 8140 , то пропустить шаги 20, 21, 22, 23, 24 25; 7 2i 8 2b ; 221 D ; 2101 101514 T 9 2j 10 10 22 2 4 100b    ; 2 10 24 4 16 10000D     ; 162 T 11 1sign 12 1k 13 2 10 216 1 2 5 26 11010T       ( 22,2 C ) 14 1sign 15; 16 2 10 226 1 1 25 11001T      17; 9 3j 10 10 24 2 8 1000b    3 10 28 8 64 1000000D     ; 643 T 11 1sign 12 2k 13  2531643T 10 2139 10001011  ( 33,3 C ) 14 1sign 12 1k 13  5311393T 10 2124 1111100  ( 32,3 C ) 14 1sign 15; 16 3 10 2124 1 1 125 1111101T      17; 9 4j 10 10 28 2 16 10000b    ; 4 1016 16 256D     Окончание табл. 7 1 2 2100000000 ; 2564 T 11 1sign 12 3k 13  125412564T 10 2756 1011110100  ( 44,4 C ) 14 1sign 12 2k 13  25617564T 10 2606 1001011110  ( 63,4 C ) 14 1sign 12 1k 13  5416064T 10 2626 1001110010  ( 42,4 C ) 14 1sign 15; 16  116264T 10 2625 1001110001  17; 18  016402R 10 2640 1010000000  19 Так как 625640 , то продол- жить шаг 20 20 2 10 2640 625 15 1111R     ; 04 T 21;22; 23 51 D , 252 D , 1253 D , 6254 D 24; 25 Завершить алгоритм Результат вычисления корня 4-й степени равен 101 5D , остаток 102 15R . Лемма 3 применима также к Алго- ритму 6. Число однословных операций умножения для вычисления квадратного и кубического корней соответствует выра- жениям m и m3 , это говорит о том, что сложность вычисления данных корней по числу таких операций имеет линейную сложность. Теоретичні та методологічні основи програмування 29 Вывод В работе описаны метод возведения в степень n (Алгоритм 5) и метод вычис- ления корня степени n (Алгоритм 6) больших чисел на основе рекуррентных соотношений ( 1n ). В Теореме 1 доказа- но, что методы возведения в степени 2 и 3 являются частными случаями обобщенно- го метода возведения в степень n большо- го числа. Проведен анализ сложности по числу битовых операций сложения, вычи- тания и умножения алгоритма возведения в степень n в зависимости от длины в би- тах m исходного большого числа и степе- ни n . Сравнивая алгоритмы, видно, что Алгоритм 6 вычисления корня степени n больших чисел основан на Алгоритме 5 вычисления степени n с небольшими из- менениями. Показано, каким образом ис- ключаются операции деления в предло- женных алгоритмах. Спецификой описан- ных алгоритмов является то, что при воз- ведении большого числа X в степень n или вычислении корня степени n одно- временно с нахождением результата вы- числяются значения всех степеней до 1n , что можно эффективно использовать в «Гибком алгоритме возведения в степень по модулю» для предварительного вычис- ления степеней. Методы по своей природе являются побитовыми, поэтому рекомен- дуется использование методов для вычис- ления степеней, не превышающих 35 ( 35n ), так как в этом случае длина в би- тах коэффициентов треугольника Паскаля не превышает длины машинного слова в 32 бита, что позволяет минимизировать использование многословных операций. В работе приведены схема возведения в квадрат и схема вычисления квадратного корня. В работе доказаны 4 леммы. В виде таблиц продемонстрированы примеры вы- полнения описанных алгоритмов для раз- личных степеней. 1. Кнут Д. Искусство программирования для ЭВМ: Пер. с англ. / Под ред. Бабенко. – М.: Мир, 1977. – 2. – 734 с. 2. Задірака В., Олексюк О. Ком’пютерна арифметика багаторозрядних чисел. – К., Наук. видання. – 2003. – 263 с. 3. Карацуба А.А., Офман Ю.П. Умножение многоразрядных чисел на автоматах // ДАН CCCP, 145 (1962). – С. 293–294. 4. Березовский А.И., Задирака В.К., Шевчук Л.Б. О тестировании быстродействия ал- горитмов и программ выполнения основ- ных операций для ассиметричной крипто- графии // Кибернетика и системный ана- лиз. – 1999. – № 5. – С. 61–68. 5. Терещенко А.Н. Быстрое вычисление квад- ратного и кубического корней без исполь- зования операций умножения и деления // Искусственный интеллект. – 2006. – № 3. – С. 783–792. Получено 12.09.2014 Об авторе: Терещенко Андрей Николаевич, кандидат физико-математических наук. Место работы автора: ООО “СимКорп - Украина” Старший инженер-программист Киев, Стусса 35/37. E-mail: teramidi@ukr.net mailto:teramidi@ukr.net

Схожі ресурси