Об ускорении k-арного алгоритма вычисления НОД натуральных чисел

И. Амер, Ш.Т. Ишмухаметов

Казанский Приволжский федеральный университет, г. Казань, 420008, Россия

Полный текст PDF
DOI: 10.26907/2541-7746.2019.1.110-118

Для цитирования: Амер И., Ишмухаметов Ш.Т. Об ускорении k-арного алгоритма вычисления НОД натуральных чисел // Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки. – 2019. – Т. 161, кн. 1. – С. 110–118. – doi: 10.26907/2541-7746.2019.1.110-118.

For citation: Amer I., Ishmukhametov S.T. On acceleration of the k -ary GCD algorithm. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 2019, vol. 161, no. 1, pp. 110–118. doi: 10.26907/2541-7746.2019.1.110-118. (In Russian)

Аннотация

В работе исследованы методы ускорения вычисления наибольшего общего делителя натуральных чисел на основе k-арного алгоритма, разработанного в 1990 г. Д. Соренсоном. Основная идея k-арного алгоритма состоит в вычислении для заданных натуральных чисел A > B > 1 пары целых чисел x и y таких, что выполнено соотношение Ax + By ≡ 0 mod k, где параметр k выбирается взаимно простым с A и B. Тогда C = (Ax + By)/k примет значение, меньшее A, и следующая итерация выполняется с новой парой (B,C). k-арный алгоритм обеспечивает значительное уменьшение общего числа итераций по сравнению с классическим алгоритмом Евклида, однако общая производительность k-арного алгоритма проигрывает алгоритму Евклида.

Предложено использование заранее вычисленных таблиц параметров алгоритма и показано, что такой подход обеспечивает скорость, при которой k-арный алгоритм работает быстрее классического алгоритма Евклида.

Ключевые слова: наибольший общий делитель натуральных чисел, алгоритм Евклида, бинарный алгоритм, k-арный алгоритм

Благодарности. Работа выполнена за счет средств субсидии, выделенной Казанскому федеральному университету для выполнения государственного задания в сфере научной деятельности, проект № 1.13556.2019/13.1. Работа также частично поддержана РФФИ (проект № 18-47-16005).

Литература

1. Ишмухаметов Ш.Т. Методы факторизации натуральных чисел .– Казань: Изд-во Казан. ун-та, 2011. – 189 с.

2. Ишмухаметов Ш.Т., Маад К.А., Мубараков Б.Г. Вычисление коэффициентов Безу для k-арного алгоритма нахождения НОД // Изв. вузов. Матем. – 2017. – № 11. – C. 30–38.

3. Stein J. Computational problems associated with Racah algebra // J. Comput. Phys. – 1967.– V. 1, No 3. – P. 397–405. – doi: 10.1016/0021-9991(67)90047-2.

4. Knuth D. The Art of Computer Programming. V. 2: Seminumerical Algorithms. – Addison-Wesley, 1997. – xiv, 762 p.

5. Ishmukhametov S.T. Rubtsova R.G. A parallel computation of the GCD of natural numbers // Сб. тр. «Параллельные вычислительные технологии – XI международная конференция», ПаВТ'2017. – Казань, 2017. – P. 120–129.

6. Sorenson J. The k-ary GCD Algorithm: Computer Sciences Technical Report CS-TR-90-979. – Madison: Univ. of Wisconsin, 1990. – 20 p.

7. Sorenson J. Two fast GCD Algorithms // J. Algorithms. – 1994. – V. 16, No 1. – P. 110–144. – doi: 10.1006/jagm.1994.1006.

8. Jebelean T. A generalization of the binary GCD algorithm // Proc. Int. Symp. on Symbolic and Algebraic Computation, SSAC'93. – N. Y.: ACM, 1993. – P. 111–116. – doi: 10.1145/164081.164102.

9. Ishmukhametov S.T. An approximating k-ary GCD algorithm // Lobachevskii J. Math. – 2016. – V. 37, No 6. – P. 723–729. – doi: 10.1134/S1995080216060147.

10. Weber K. The accelerated integer GCD algorithm // ACM Trans. Math. Software. – 1995. – V. 21, No 1. – P. 111–122. – doi: 10.1145/200979.201042.

11. Maximov K.L., Ishmukhametov S.T. About algorithm of smooth numbers calculation // Res. J. Appl. Sci. – 2015. – V. 10, No 8. – P. 376–380.

12. Ishmukhametov S.T., Mubarakov B.G. On practical aspects of the Miller–Rabin Primality Test // Lobachevskii J. Math. – 2013. – V. 34, No 4. – P. 304–312. – doi: 10.1134/S1995080213040100.

Поступила в редакцию

15.06.18

Амер Исмаил, стажер-исследователь кафедры системного анализа и информационных технологий

Казанский (Приволжский) федеральный университет

ул. Кремлевская, д. 18, г. Казань, 420008, Россия

E-mail:  safadi121979@yahoo.com

Ишмухаметов Шамиль Талгатович, доктор физико-математических наук, профессор кафедры системного анализа и информационных технологий

Казанский (Приволжский) федеральный университет

ул. Кремлевская, д. 18, г. Казань, 420008, Россия

E-mail:  sishmukh@kpfu.ru

Контент доступен под лицензией Creative Commons Attribution 4.0 License.