УДК 519.6
В.К. ЗАДІРАКА,
Інститут кібернетики ім. В.М. Глушкова НАН України, Київ, Україна,
zvk140@ukr.net
А.М. ТЕРЕЩЕНКО,
Інститут кібернетики ім. В.М. Глушкова НАН України, Київ, Україна,
teramidi@ukr.net
ЗНАХОДЖЕННЯ СУМИ БАГАТОРОЗРЯДНИХ ЧИСЕЛ
У ПАРАЛЕЛЬНІЙ МОДЕЛІ ОБЧИСЛЕННЯ
Анотація. Запропоновано новий метод реалізації операції знаходження суми двох і більше багатослівних доданків
у паралельній моделі обчислення, який дає змогу звести знаходження суми великої кількості багатослівних доданків
до операції знаходження двох багатослівних доданків за рахунок збереження знаків переносів для багатослівних чисел,
ефективної в паралельній моделі обчислення на основі методу «прогнозування знаків переносів між групами слів».
Запропоновано також алгоритми реалізації операції знаходження суми доданків на одному процесорі та k процесорах.
Наведено аналіз складності таких алгоритмів.
Ключові слова: багаторозрядна арифметика, багаторозрядне додавання, знак переносу, паралельна модель обчислення.
ПОВНИЙ ТЕКСТ
СПИСОК ЛІТЕРАТУРИ
- 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. https://doi.org/ 10.1145/359340.359342.
- Анісімов А.В. Алгоритмічна теорія великих чисел. Модулярна арифметика великих чисел. Київ: Академперіодика, 2001. 153 с. URL : http://books.zntu.edu.ua/book_info.pl?id=21106.
- Задірака В., Олексюк О. Комп’ютерна арифметика багаторозрядних чисел. Київ: Наук. видання, 2003. 263 с.
- Задирака В.К. Теория вычисления преобразования Фурье. Киев: Наук. думка, 1983. 213 с.
- Задірака В.К., Терещенко А.М. Комп'ютерна арифметика багаторозрядних чисел у послідовній та паралельній моделях обчислень. Київ: Наук. думка, 2021. 136 с.
- Николайчук Я.М., Касянчук М.М., Якименко І.З., Івасьєв С.В. Ефективний метод модулярного множення в теоретико-числовому базисі Радемахера–Крестенсона. Вісн. Нац. ун-ту «Львівська політехніка». Комп’ютерні системи та мережі. 2014. № 806. C. 195–199. URL: http://nbuv.gov.ua/UJRN/VNULPKSM_2014_806_31.
- Хіміч О.М., Сидорук В.А. Використання мішаної розрядності у математичному моделюванні. Математичне та комп’ютерне моделювання. Серія: Фіз.-мат. науки. Зб. наук. праць. 2019. Вип. 19. С. 180–187. https://doi.org/10.32626/2308-5878.2019-19.180-187.
- Анисимов А.В. Сложение без единиц переноса. Кибернетика и системный анализ. 1996. № 2. С. 3–15.
- Floyd R., Knuth D. Addition machines. SIAM Journal on Computing. 1990. Vol. 19, N 2. P. 329–340. https://doi.org/10.1137/0219022.
- McGeoch C. Parallel addition. The American Mathematical Monthly. 1993. Vol. 100, N 9. P. 867–871. URL: http://www.jstor.org/stable/2324666.
- Терещенко А.Н., Задирака В.К. Параллельное сложение на основе векторных операций. Искусственный интеллект. 2018. № 2. С. 122–137. URL: http://dspace.nbuv.gov.ua/ handle/123456789/162381.
