2021, випуск 4, c. 61-79

Одержано 14.12.2021; Виправлено 20.12.2021; Прийнято 21.12.2021

Надруковано 30.12.2021; Вперше Online 27.01.2022

https://doi.org/10.34229/2707-451X.21.4.7

Попередня  |  ПОВНИЙ ТЕКСТ  |  Наступна

 

УДК 519.6

Реалізація багаторозрядної операції множення на основі дискретних косинусних та синусних перетворень

А.М. Терещенко * ORCID ID favicon Big,   В.К. Задірака ORCID ID favicon Big

Інститут кібернетики імені В.М. Глушкова НАН України, Київ

* Листування: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.

 

Вступ. Поява нових паралельних обчислювальних систем таких, як багатоядерні процесори, кластери, розподілені системи, обумовлена вирішенням різних прикладних задач у різних галузях. Серед таких задач можна виділити задачі обчислення систем лінійних алгебраїчних рівнянь з кількістю невідомих 33–35 мільйонів, розрахунок оболонок ядерних реакторів, моделювання фізичних, хімічних процесів, аеродинаміки, гідроди­намі­ки, захисту інформації, тощо. Це значно розширює використання багаторозрядної арифметики, із-за того, що неврахування похибок заокруглення призводить до того, що іноді отримуються комп‘ютерні рішення, які не відповідають фізичному змісту. Багаторозрядна операції множення є складовою частиною операції піднесення до степеня за модулем, від швидкодії якої зале­жить швидкодія асиметричних криптографічних програмно-апаратних комплексів.

У даній роботі наведені алгоритми реалізації операції множення двох N-розрядних чисел на основі дискретних косинусних та синусних перетворень (ДКП та ДСП) за рахунок розділення обчислення для дійсної та уявної частин ДПФ. Обчислення ДКП та ДСП за рахунок додаткових бітових зсувів, додавань та віднімань зменшує складність основного алгоритму до лінійної складності за кількістю однорозрядних операцій множення над цілими числами.

Мета роботи. Зменшити кількість операцій множення для пришвидшення часу виконання операції множення двох N-розрядних чисел на основі дискретних перетворень. Зменшити кількість комплексних операцій множення. Зменшити загальну обчислювальну складність та знайти модифікацію, при якій кроки обчислення будуть відповідати ДКП, ДСП, ОДКП та ОДСП. Ввести коефіцієнти нормування для врахування похибки заокруглення, щоб виключити операції множення при обчисленні ДКП, ДСП, ОДКП та ОДСП.

Результати. Розглянуто взаємозв’язок між ДКП, ДСП та ДФП дійсного сигналу, що дозволяє розділити обчислення для дійсної та уявної частин ДПФ. Зменшена обчислювальна складність майже у два рази за рахунок використання властивостей ДПФ дійсних сигналів. Показано, що після оптимізації в кроки алгоритму відповідають ДКП, ДСП, ОДКП та ОДСП. Використано додатково коефіцієнти нормування, які дозволяють врахувати похибки заокруглення на кожному кроці таким чином, щоб всі обчислення відбувалися у полі цілих чисел. Надано аналіз вибору довжини слова при обчислені. Для кожного алгоритму наведено приклади обчислення. Надані таблиці залежності мінімальних довжин коефіцієнтів від довжини багаторозрядного числа та довжини розряду (у бітах).

Висновки. У роботі наведені алгоритми реалізації операції множення двох N-розрядних чисел на основі дискретних косинусних та синусних перетворень (ДКП та ДСП). Розділення обчислення для дійсної та уявної частин ДПФ дійсного сигналу дозволяє зменшити кількість операцій множення на 33 %. Використання додаткових коефіцієнтів та обчислення ДКП, ДСП, ОДКП, ОДСП за рахунок бітових зсувів, додавань та віднімань дозволяє зменшити складність алгоритму реалізації операції множення двох N-розрядних чисел до лінійної складності за кількістю операцій множення над однорозрядними числами. На основі порівняльного аналізу показано, що запропонований метод множення на основі ДКП та ДСП у полі цілих чисел починає випереджати метод Карацуби за кількістю 32-бітних операцій множення при множенні чисел, починаючи з довжини у 4096 бітів.

 

Ключові слова: багаторозрядне множення, багаторозрядна арифметика, асиметрична криптографія, дискретне косинусне перетворення, дискретне синусне перетворення, дискретне перетворення Фур’є, швидкий алгоритм обчислення Фур’є.

 

Цитувати так: Терещенко А.М., Задірака В.К. Реалізація багаторозрядної операції множення на основі дискретних косинусних та синусних перетворень. Cybernetics and Computer Technologies. 2021. 4. С. 61–79. https://doi.org/10.34229/2707-451X.21.4.7

 

Список літератури

           1.     Анісімов А.В. Алгоритмічна теорія великих чисел. Модулярна арифметика великих чисел. Київ: Академперіодика, 2001. 153 с. http://books.zntu.edu.ua/book_info.pl?id=21106

           2.     Задірака В., Олексюк О. Комп’ютерна арифметика багаторозрядних чисел. Київ: Наукове видання, 2003. 263 с.

           3.     Задирака В.К. Теория вычисления преобразования Фурье. Киев: Наук. думка, 1983. 213 с.

           4.     Задірака В.К., Терещенко А.М. Комп‘ютерна арифметика багаторозрядних чисел у послідовній та паралельній моделях обчислень. Киев: Наук. думка, 2021. 136 с.

           5.     Качко Е.Г. Распараллеливание алгоритмов умножения чисел многократной точности. Вестник Уфимского государственного авиационного технического университета. 2011. Е 15, № 5 (45). С. 142–147. http://omega.sp.susu.ru/books/conference/PaVT2011/short/015.pdf

           6.     Николайчук Я.М., Касянчук М.М., Якименко І.З., Івасьєв С.В. Ефективний метод модулярного множення в теоретико-числовому базисі Радемахера – Крестенсона. Вісник Національного університету "Львівська політехніка". Комп’ютерні системи та мережі. 2014. N 806. C. 195–199. http://nbuv.gov.ua/UJRN/VNULPKSM_2014_806_31

           7.     Хіміч О.М., Сидорук В.А. Використання мішаної розрядності у математичному моделюванні. Математичне та комп’ютерне моделювання. Серія: Фізико-математичні науки. Зб. наук. праць. 2019. 19. С. 180–187. https://doi.org/10.32626/2308-5878.2019-19.180-187

           8.     Карацуба А.А., Офман Ю.П. Умножение многоразрядных чисел на автоматах. ДАН CCCP. 1962. 145 (2). С. 293–294. http://mi.mathnet.ru/dan26729

           9.     Cooley J.W., Tukey J.W. An algorithm for the machine calculation of complex Fourier Series. Math Compt. 1965. 19. P. 257–301. https://doi.org/10.1090/S0025-5718-1965-0178586-1

       10.     Schonhage A., Strassen V. Schnelle Multiplikation großen Zahlen. Computing. 1971. 7 (3–4). P. 281–292. https://doi.org/10.1007/BF02242355

       11.     Pitassi D.A. Fast convolution using the Walsh transform. Applications of Walsh Functions. April, 1971. P. 130–133. https://doi.org/10.1109/TEMC.1971.303141

       12.     Терещенко А.Н., Мельникова С.С., Гнатив Л.А., Задирака В.К., Кошкина Н.В. Реализация операции умножения с использованием преобразования Уолша. Проблемы управления и информатики. 2010. № 2. С. 102–126.

       13.     Montgomery P.L. Modular Multiplication Without Trial Division. Math. Comp. 1985. 44. P. 519–521. https://doi.org/10.1090/S0025-5718-1985-0777282-X

       14.     Cook S.A. On the Minimum Computation Time of Functions. 1966 PhD thesis. Harvard University Department of Mathematics. http://cr.yp.to/bib/1966/cook.html (звернення: 14.12.2021)

       15.     Ahmed N., Natarajan T., Rao K.R. Discrete cosine transform. IEEE Trans. Comput. 1974. C–23 (1). P. 90–93. https://doi.org/10.1109/T-C.1974.223784

       16.     Jain A.K. A fast Karhunen–Loève transform for a class of random processes. IEEE Trans. on Communications. 1976. 24. 1023. https://doi.org/10.1109/TCOM.1976.1093409

       17.     Gluth R. Regular FFT–related transform kernels for DCT/DST – based polyphase filter banks. Proc. IEEE ICASSP. Toronto, Canada, May 1991. P. 2205–2208. https://doi.org/10.1109/ICASSP.1991.150852

       18.     Чичева М.А. Эффективный алгоритм дискретного косинусного преобразования четной длины. Компьютерная оптика. 1998. №. 18. С. 147–149. https://doi.org/10.1080/713696822

       19.     Гнатів Л.О., Луц В.К. Цілочислові модифіковані синус-косинусні перетворення типу VII. Метод побудови і роздільні направлені адаптивні перетворення для intra-прогнозування з блоками яскравості 8 x 8 у кодуванні зображень/відео. Кібернетика та системний аналіз. 2021. Т. 57, № 1. С. 178–190.

 

 

ISSN 2707-451X (Online)

ISSN 2707-4501 (Print)

Попередня  |  ПОВНИЙ ТЕКСТ  |  Наступна

 

 

 

© Вебсайт та оформлення. 2019-2022,

Інститут кібернетики імені В.М. Глушкова НАН України,

Національна академія наук України.