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