УДК 519.6
В.К. ЗАДІРАКА,
Інститут кібернетики ім. В.М. Глушкова НАН України, Київ, Україна,
zvk140@ukr.net
А.М. ТЕРЕЩЕНКО,
Інститут кібернетики ім. В.М. Глушкова НАН України, Київ, Україна,
teramidi@ukr.net
ПАРАЛЕЛЬНІ МЕТОДИ ПРЕДСТАВЛЕННЯ ЧИСЕЛ
ДЛЯ ТЕСТУВАННЯ ОПЕРАЦІЙ БАГАТОРОЗРЯДНОЇ АРИФМЕТИКИ
Анотація. Запропоновано методи реалізації операції представлення багаторозрядного числа
у системі числення з іншою основою, потрібні для тестування арифметичних операцій
у разі використання паралельних процесорів. Розглянуто представлення числа
у системах числення на основі багаторозрядних операцій ділення та віднімання
або багаторозрядних операцій множення та додавання. Алгоритм з розбиттям числа
на групи цифр дає змогу враховувати довжину машинного слова та розподіляти обчислення між процесорами.
Проаналізовано складність за кількістю операцій, обсяг додаткової памя’ті для алгоритмів на основі ітераційного та рекурсивного методів.
Ключові слова: система числення, багаторозрядна арифметика, багаторозрядне додавання, багаторозрядне множення, паралельна модель обчислень.
ПОВНИЙ ТЕКСТ
СПИСОК ЛІТЕРАТУРИ
- Rivest R.L., Shamir A., Adleman L. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM. 1978. Vol. 21, N 2. P. 120–126. doi.org/10.1145/359340.359342 .
- Задірака В.К., Олексюк О.С. Комп’ютерна арифметика багаторозрядних чисел. Київ, 2003. 264 с.
- Задирака В.К. Теория вычисления преобразования Фурье. Киев: Наук. думка, 1983. 213 с.
- Задірака В.К., Терещенко А.М. Комп’ютерна арифметика багаторозрядних чисел у послідовній та паралельній моделях обчислень. Київ: Наук. думка, 2021. 136 с.
- Хіміч О.М., Сидорук В.А. Використання мішаної розрядності у математичному моделюванні. Математичне та комп’ютерне моделювання. Сер. Фіз.-мат. науки. 2019. Вип. 19. С. 180–187.
- Анісімов А.В. Алгоритмічна теорія великих чисел. Модулярна арифметика великих чисел. Київ: Академперіодика, 2001. 153 с.
- Николайчук Я.М., Касянчук М.М., Якименко І.З., Івасьєв С.В. Ефективний метод модулярного множення в теоретико-числовому базисі Радемахера–Крестенсона. Вісн. Нац. ун-ту «Львівська політехніка». Комп’ютерні системи та мережі. 2014. № 806. C. 195–199. URL: http://nbuv.gov.ua/UJRN .
- Knuth D. The art of computer programming. Vol. 2. Seminumerical Аlgorithms. 3rd ed. Ch. 4. Arithmetic. “Positional Number Systems.” Reading, Massachusetts: Addison–Wesley, 1997. Р. 194–213.
- Floyd R., Knuth D. Addition machines. SIAM Journal on Computing. 1990. Vol. 19, N 2. P. 329–340. doi.org/10.1137/0219022 .
- Анисимов А.В. Сложение без единиц переноса. Кибернетика и системный анализ. 1996. № 2. С. 3–15.
- Терещенко А.Н., Задирака В.К. Параллельное сложение на основе векторных операций. Штучний інтелект. 2018. № 2. С. 122–137. URL: http://dspace.nbuv.gov.ua/handle .