2021, випуск 2, c. 39-56

Одержано 12.03.2021; Виправлено 24.03.2021; Прийнято 24.06.2021

Надруковано 30.06.2021; Вперше Online 01.07.2021

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

Попередня  |  Повний текст  |  Наступна

 

УДК 519.6

Генерування великих чисел для тестування алгоритмів багаторозрядної арифметики

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

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

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

 

Вступ. Поява нових паралельних обчислювальних систем таких, як багатоядерні процесори, кластери, розподілені системи, обумовлена вирішенням різних прикладних задач у різних галузях. Відмінність пристроїв, для яких реалізуються паралельні алгоритми, зумовлює розмаїття існуючих методів розпаралелювання обчислення операцій багаторозрядної арифметики. Існує проблема розробки універсальних алгоритмів реалізації операцій багатороз­рядної арифметики, які виконуються ефективно на різних пристроях та різних системах.

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

У даній роботі наведені деякі прості залежності, використовуючи які можна візуально перевірити правильність обчислення багаторозрядних операцій додавання, віднімання, множення, множення за модулем та піднесення до степеня за модулем. Наведені прості алгоритми генерування вхідних та вихідних багаторозрядних даних. Використання залежностей також дозволяє перевіряти цілісність вихідних даних при делегуванні обчислень у розподілені системи, такі, як хмарні обчислення.

Мета роботи. Показати прості залежності між вхідними даними та результатами виконання багаторозрядних операцій додавання, віднімання, множення, множення за модулем та піднесення до степеня. Для наведених залежностей показано методи генерації вхідних та вихідних багаторозрядних чисел, які можуть використовуватися для перевірки правильності обчислення багаторозрядних операцій, що значно зберігає час, необхідний для підготовки тестових даних.

Залежності надані у загальному вигляді, що дозволяє генерувати вхідні дані та результати для пристроїв, які оперують словами різної довжини (8, 16, 32, 64, 128, 256, і. д. бітів).

Результати. Проаналізовано залежності між вхідними даними та результатами виконання багаторозрядних операцій. Надані залежності доведені у вигляді лем. Залежності надані у загальному вигляді, так як для генерації багаторозрядних послідовностей потрібно задати два параметри: N – кількість розрядів у багаторозрядному числі та n – довжина розрядів у бітах. На прикладах показана генерація вхідних даних та результатів для різних багаторозрядних операцій.

Висновки. У роботі наведені залежності, які легко запам’ятати та використати для візуальної перевірки результатів багаторозрядних обчислень без використання додаткового або спеціального програмного або апаратного забезпечення, що дозволяє приділити збережений час для розробки нових або більш ефективних модифікацій багаторозрядних алгоритмів.

 

Ключові слова: багаторозрядна арифметика, паралельна модель обчислення.

 

Цитувати так: Терещенко А.М., Задірака В.К. Генерування великих чисел для тестування алгоритмів багаторозрядної арифметики. Cybernetics and Computer Technologies. 2021. 2. С. 39–56. https://doi.org/10.34229/2707-451X.21.2.4

 

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

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

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

           3.     Николайчук Я.М., Возна Н.Я., Пітух І.Р. Проектування спеціалізованих комп’ютерних систем. Тернопіль: Терно-Граф, 2010. 392 с. http://library.kpi.kharkov.ua/uk/inftechnologies_nik

           4.     Хіміч О.М. Cуперкомп’ютерні технології та математичне моделювання складних систем. Вісник НАН України. 2018. 5. С. 69−72. http://dspace.nbuv.gov.ua/handle/123456789/140740

           5.     Новокшонов А.К. Контроль цілісності арифметичних обчислень. Матеріали XIV Міжнародної науково-практичної конференції «Теоретичні та прикладні аспекти побудови програмних систем». 2017. С. 149–154.

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

           7.     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

           8.     Davis W.F. A class of efficient convolution algorithms. Applicat. Walsh Functions. 1972. March. P. 318–329.

           9.     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

       10.     Anisimov A.V., Novokshonov A. Verifiable Arithmetic Computations Using Additively Homomorphic Tags. IEEE Advanced Trends in Information Theory. 2019. P. 9396. https://doi.org/10.1109/ATIT49449.2019.9030485

 

 

ISSN 2707-451X (Online)

ISSN 2707-4501 (Print)

Попередня  |  Повний текст  |  Наступна

 

 

 

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

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

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