## 2021, issue 4, p. 61-79

*Received **14.12.2021;
Revised 20.12.2021; Accepted 21.12.2021*

*Published **30.12.2021;
First Online 27.01.2022*

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

Previous | FULL TEXT (in Ukrainian) | Next

**Implementation of Multidigit
Multiplication Basing on Discrete Cosine ****
****and
Sine Transforms**

Andrii Tereshchenko ^{*}
, Valeriy Zadiraka

*V.M. Glushkov Institute of Cybernetics of
the NAS of Ukraine, Kyiv*

^{*}* Correspondence: This email address is being protected from spambots. You need JavaScript enabled to view it.*

**Introduction.** The emergence
of new parallel computing systems such as multi-core processors, clusters,
distributed systems, due to the solution of various applications in different
spheres. Among such problems are the calculation of systems of linear algebraic
equations with the number of unknown 33-35 million, the calculation of nuclear
reactor shells, modeling of physical and chemical processes, aerodynamics,
hydrodynamics, information security, and so on. This greatly expands the use of
multidigit arithmetic, due to the fact that ignoring rounding errors leads to
the fact that sometimes computer solutions are obtained that do not correspond
to the physical content. Multidigit multiplication operation is an integral
part of the exponentiation by module operation, the speed of which determines
the speed of asymmetric cryptographic software and hardware complexes.

This paper presents
algorithms for implementing the multiplication operation of two *N*-digit
numbers based on discrete cosine and sine transforms (DCT and DST) by
separating the calculation for the real and imaginary parts of the DFT.
Calculation of DCT and DST at the expense of additional bit shifts, additions
and subtractions reduces the algorithm complexity to linear complexity by the
number of integer multiplication operations.

**The purpose** of the article
is to reduce the number of multiplication operations to speed up the execution
time of the multiplication operation of two *N*-bit numbers based on
discrete transforms. Reduce the number of complex multiplication operations.
Reduce the overall computational complexity and find a modification in which
the calculation steps will correspond to DCT, DSP, IDCT and IDST. Use the
coefficients to take into account the rounding errors to exclude multiplication
operations on calculating DCT, DST, IDCT and IDST.

**Results.** The
relationship between DCT, DST and DFT of a real signal is considered, which
allows to separate calculations for real and imaginary parts of DFT of real
signals. The computational complexity is reduced almost twice at the expense of
use of DFT properties of real signals. It is shown that after optimization
steps of the algorithm calculation correspond to DCT, DST, IDCT and IDST. Using
additional coefficients, which allow to take into account rounding errors at
each step so that all calculations use integers. An analysis of the choice of
word length in the calculation is given. For each algorithm, examples of
calculation are given. Tables of dependence of the minimum lengths of the
coefficients on the length of the multidigit number and the length of the digit
(in bits) are given.

**Conclusions.** Multiplication
algorithms of two *N*-digit numbers based on discrete cosine and sine transforms
(DCT and DST) are presented in this paper. Separating the calculation for the
real and imaginary parts of the DFT allows to reduce the number of
multiplication operations by 33%. The use of additional coefficients and
calculation of DCT, DST, IDCT, IDST at the expense of bit shifts, additions and
subtractions reduces the complexity of the multiplication algorithm of two *N*-digit
numbers to linear complexity by the number of simple integer multiplication
operations. Based on comparative analysis, it is shown that the proposed method
of multiplication based on DCT and DST using integers begins to exceed the
Karatsuba method by the number of 32-bit multiplication operations when
multiplying numbers, starting with a length of 4096 bits.

**Keywords:** multidigit
multiplication, multidigit arithmetic, asymmetric cryptography, discrete cosine
transform, discrete sine transform, discrete Fourier transform, fast algorithm
for Fourier calculation.

**Cite as: **Tereshchenko
A., Zadiraka V. Implementation of Multidigit Multiplication Basing on Discrete
Cosine and Sine Transforms. *Cybernetics and Computer Technologies*. 2021.
**4**. P. 61–79. (in Ukrainian) https://doi.org/10.34229/2707-451X.21.4.7

**References**

1. Anisimov A.V. Multi-digit algorithmic theory. Multi-digit modular arithmetic. Kyiv: Akademperiodika. 2001. 153 P. (in Ukrainian) http://books.zntu.edu.ua/book_info.pl?id=21106

2. Zadiraka V., Oleksyuk О. Computer arithmetic of the multidigit number. Kyiv: Naukove vydannya, 2003. 263 p. (in Ukrainian)

3. Zadiraka V.K. Fourier transform computation theory. Kyiv: Naukova dumka, 1983. 213 p. (in Russian)

4. Zadiraka V.K., Tereshchenko A.M. Computer arithmetic of multidigit numbers in sequential and parallel computational models. Kyiv: Naukova dumka, 2021, 136 p. (in Ukrainian)

5. Kachko O.G.
Parallelization of algorithms for multiplying multiple precision numbers. *Vestnik
Ufimskogo gosudarstvennogo aviatsionnogo tehnicheskogo universiteta*. 2011. **Е
15**. **5** (45). P. 142–147. (in Russian) http://omega.sp.susu.ru/books/conference/PaVT2011/short/015.pdf

6. Nykolaichuk
Y.M., Kasianchuk M.M., Yakimenko I.Z., Ivasiev S.V. Effective method of modular
multiplication in the number-theoretic basis of Rademacher–Chrestenson. *Visnik
Natsionalnogo universitetu "Lvivska politehnika". Komp’yuterni
sistemi ta merezhi*. 2014. 806. P. 195–199. http://nbuv.gov.ua/UJRN/VNULPKSM_2014_806_31 (in Russian)

7. Khimich O.M., Sydoruk V.A.
Using of the mixed size in the mathematical model. *Matematichne ta
komp’yuterne modelyuvannya. SerIya: FIziko-matematichnI nauki. Zb. nauk. prats*.
2019. 19. P. 180–187. (in Ukrainian) https://doi.org/10.32626/2308-5878.2019-19.180-187

8. Karatsuba A.,
Ofman Yu., Multiplication of many-digital numbers by automatic computers. *Dokl.
Akad. Nauk SSSR*. 1962. **145** (2). P. 293–294. (in Russian) 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. Tereshchenko
A.M., Melnykova S.S., Hnatyv L.O., Zadiraka V.K., Koshkyna N.V. Calculation of
Multiplication, Using Walsh Transform. *Journal of Automation and Information
Sciences*. 2010. **42** (4). P. 37–45. https://doi.org/10.1615/JAutomatInfScien.v42.i4.40

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 (accessed: 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. Chycheva M.A. Effektivnyiy
algoritm diskretnogo kosinusnogo preobrazovaniya chetnoy dlinyi. *Kompyuternaya
optika*. 1998. 18. P. 147–149. (in Russian) https://doi.org/10.1080/713696822

19. Hnatyv L.O.,
Luts V.K. Integer Modified Sine-Cosine Transforms Type VII. A construction
Method and Separable Directional Adaptive Transforms for Intra Prediction with
8 × 8 Chroma Blocks in Image/Video Coding. *Cybernetics and Systems
Analysis*. 2021. **57** (1). P. 155–164. https://doi.org/10.1007/s10559-021-00339-9

* *

* *

*ISSN 2707-451X (Online) *

*ISSN 2707-4501 (Print) *

Previous | FULL TEXT (in Ukrainian) | Next