Об использовании техники отложенного переноса в арифметике длинных целых чисел
Аннотация
Описаны варианты использования техники отложенного переноса (ТОП) для ускорения вычисления произведения длинных целых чисел. Применение ТОП позволяет сократить накладные расходы, связанные с необходимостью обработки межразрядных переносов, возникающих в процессе вычислений. Проведено исследование эффективности данной техники для модифицированного метода сдвигов и сложений и метода Карацубы. Разработаны методы программной реализации алгоритмов умножения, обладающие высокой эффективностью и переносимостью на различные вычислительные средства. Получены теоретические оценки числа инструкций умножения, сложения и доступа к памяти, необходимых для программной реализации алгоритмов. Выполнена экспериментальная оценка эффективности методов с ТОП по сравнению с базовыми методами сдвигов и сложений и методом Карацубы. Эксперименты показали высокую эффективность алгоритмов с ТОП, в том числе и в сравнении с уже существующими решениями на базе программной библиотеки GMP. Применение техники отложенного переноса позволило увеличить производительность вычислений по модифицированному методу сдвигов и сложений (для 1024-битных чисел) на 18%, а по методу Карацубы на 31% (по сравнению с линейной реализацией модифицированного метода сдвигов и сложений). Рассмотренные алгоритмы умножения длинных целых чисел с применением ТОП могут быть эффективно использованы при создании переносимых (без ассемблерных вставок) программных библиотек компьютерной алгебры.
Литература
2. Brent R.Р., Zimmermann P. Modern Computer Arithmetic. N.-Y.: Cambridge University Press, 2010.
3. Карацуба А.А., Офман Ю.П. Умножение многозначных чисел на автоматах // ДАН СССР. 1962. Т. 145. № 2. С. 293—294.
4. Comba P.G. Exponentiation Cryptosystems on the IBM PC // IBM Systems J. 1990. No. 29. Pp. 526—538.
5. Карацуба А.А. Сложность вычислений // Труды МИАН. 1995. Т. 211. С. 186—202.
6. Куляс М.Е. О синтезе программ умножения длинных целых чисел // Программная инженерия. 2017. № 2. С. 66—75.
7. Weimerskirch A., Paar C. Generalization of the Karatsuba Algorithm for efficient Implementation // Cryptology ePrint Archive. 2006. Rep. 224 [Электрон. ресурс] http://eprint.iacr.org/2006/224 (дата обращения 10.10.2017).
8. Khachatrian G., Kuregian M., Ispiryan K., Massey J. Faster Multiplication of Integers for Public-key Applications // Selected Areas in Cryptography. 2001. V. 2259. P. 245—254.
9. Kovtun V.Yu., Okhrimenko A.O. Integer Squaring Algorithm with Delayed Carry Mechanism // Безпека iнформацii. 2013. V 19. No. 3. Pp. 188—192.
10. Scott M. Missing a Trick: Karatsuba Variations // Cryptology ePrint Archive. 2015. Rep. 1247 [Электрон. ресурс] http://eprint.iacr.org/2015/1247 (дата обращения 10.10.2017).
11. Paoloni G. How to Benchmark Code Execution Times on Intel IA-32 and IA-64 Instruction Set Architectures 2010. [Электрон. ресурс] http://www.intel.com/content/dam/www/ public/us/en/documents/white-papers/ia-32-ia-64-benchmarkcode-execution-paper.pdf (дата обращения 12.10.2017).
12. Granlund T. The GMP development team: GNU MP: The GNU Multiple Precision Arithmetic Library [Электрон. ресурс] http://gmplib.org (дата обращения 12.10.2017).
---
Для цитирования: Куляс М.Е. Об использовании техники отложенного переноса в арифметике длинных целых чисел // Вестник МЭИ. 2018. № 6. С. 96—102. DOI: 10.24160/1993-6982-2018-6-96-102.
#
1. Knut D.E. Iskusstvo Programmirovaniya. T. 2. Poluchislennye Algoritmy. M.: Vil'yams, 2007. (in Russian).
2. Brent R.R., Zimmermann P. Modern Computer Arithmetic. N.-Y.: Cambridge University Press, 2010.
3. Karatsuba A.A., Ofman YU.P. Umnozhenie Mnogoznachnyh Chisel na Avtomatah. DAN SSSR. 1962; 145;2: 293—294. (in Russian).
4. Comba P.G. Exponentiation Cryptosystems on the IBM PC. IBM Systems J. 1990;29:526—538.
5. Karatsuba A.A. Slozhnost' Vychisleniy. Trudy MIAN. 1995; 211:186—202. (in Russian).
6. Kulyas M.E. O Sinteze Programm Umnozheniya Dlinnyh Tselyh Chisel. Programmnaya Inzheneriya. 2017;2: 66—75. (in Russian).
7. Weimerskirch A., Paar C. Generalization of the Karatsuba Algorithm for Efficient Implementation. Cryptology ePrint Archive. 2006; 224 [Elektron. Resurs] http://eprint.iacr. org/2006/224 (Data Obrashcheniya 10.10.2017).
8. Khachatrian G., Kuregian M., Ispiryan K., Massey J. Faster Multiplication of Integers for Public-key Applications. Selected Areas in Cryptography. 2001;2259:245—254.
9. Kovtun V.Yu., Okhrimenko A.O. Integer Squaring Algorithm with Delayed Carry Mechanism. Bezpeka informatsii. 2013;19;3:188—192.
10. Scott M. Missing a Trick: Karatsuba Variations. Cryptology ePrint Archive. 2015;1247 [Elektron. Resurs] http:// eprint.iacr.org/2015/1247 (Data Obrashcheniya 10.10.2017).
11. Paoloni G. How to Benchmark Code Execution Times on Intel IA-32 and IA-64 Instruction Set Architectures 2010. [Elektron. Resurs] http://www.intel.com/content/dam/www/ public/us/en/documents/white-papers/ia-32-ia-64-benchmarkcode-execution-paper.pdf (Data Obrashcheniya 12.10.2017).
12. Granlund T. The GMP development team: GNU MP: The GNU Multiple Precision Arithmetic Library [Elektron. Resurs] http://gmplib.org (Data Obrashcheniya 12.10.2017).
---
For citation: Kulyas M.Е. On Using the Carry-Save Technique in the Arithmetic of Long Integer Numbers. MPEI Vestnik. 2018;6: 96—102. (in Russian). DOI: 10.24160/1993-6982-2018-6-96-102.
