Complexity analysis of multidigit multiplication operation for implementtation in parallel computational model

A.N. Tereshchenko

Abstract


It is analyzed on computing operation of multidigit multiplication of N-digit values based on standard method in parallel computational model the complexity of number of operations of simple additions and multiplications for two cases: when number of available processors is unlimited, and when number of available processors is limited and multiply N.

References


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

Schonhage A., Strassen V. Schnelle Multiplikation grossen Zahnel // Computing. – 1971. – 7, N 3–4. – P. 281–292.

Шенхаге А., Шрассен В. Быстрое умножение больших чисел // Кибернетика. – 1972. – Вып. 2. – С. 87–98.

Cooley J.W., Tukey J.W. An algorithm for the machine calculation of complex Fourier Series // Math Compt. – 1965. Apr. – P. 257–301.

Березовский А.И., Задирака В.К., Шевчук Л.Б. О тестировании быстродействия алгоритмов и программ выполнения основных операций для асимметричной криптографии // Кибернетика и системный анализ. – 1999. – № 5. – С. 61–68.

Терещенко А.Н. Умножение больших N-разрядных чисел с вычислением только N-разрядных ДПФ // Компьютерная математика. – 2008. – № 1. – С. 122–130.


Refbacks

  • There are currently no refbacks.