2024, issue 2, p. 47-56
Received 13.03.2024; Revised 20.04.2024; Accepted 28.05.2024
Published 09.06.2024; First Online 14.06.2024
https://doi.org/10.34229/2707-451X.24.2.5
Previous | FULL TEXT (in Ukrainian) | Next
Methods of Combating the Accumulation of Rounding Error When Solving Problems of Trans-Computational Complexity
Valerii Zadiraka *
, Inna Shvidchenko *
V.M. Glushkov Institute of Cybernetics of NAS of Ukraine, Kyiv
* Correspondence: This email address is being protected from spambots. You need JavaScript enabled to view it., This email address is being protected from spambots. You need JavaScript enabled to view it.
Introduction. The main attention is paid to the need to take into account estimates of rounding errors when solving problems of transcomputational complexity. Among such tasks, one can highlight the tasks of calculating systems of linear algebraic equations with the number of unknowns in the tens of millions, digital signal processing, calculating nuclear reactors, modeling physical and chemical processes, aerodynamics, information protection, etc.
Ignoring the rounding error when solving them leads to the fact that sometimes we obtain computer solutions that do not correspond to the physical content of the problem.
The purpose of the article. It is shown how, using estimates of rounding errors, to build computational algorithms resistant to rounding errors. At the same time, the following are taken into account: the rounding rule, the calculation mode, the quality of rounding error estimates (non-improving estimate, asymptotic estimate, imputed estimate).
If computing resources are available, it is advisable to use asymptotic and probabilistic estimates as they are more accurate compared to majorant estimates.
The results. It is shown how the estimates of rounding errors are used in modern computer technologies to obtain ε-solution of the following problems of applied mathematics:
– calculation of integrals from fast oscillating functions;
– solving problems of digital signal processing;
– calculating the discrete Fourier transform;
– multi-bit arithmetic;
– computer steganography.
The greatest attention is paid to T-effective algorithms for calculating the discrete Fourier transform and solving the problems of spectral and correlation analysis of random processes. These classes of problems are included as components in solving problems of two-key cryptography and computer steganography.
Conclusions. The importance of taking into account estimates of rounding errors in modern computer technologies for solving a number of classes of computational and applied mathematics problems is shown.
Keywords: rounding error, computer technology, discrete Fourier transform, integration of fast oscillating functions, information security.
Cite as: Zadiraka V., Shvidchenko I. Methods of Combating the Accumulation of Rounding Error When Solving Problems of Trans-Computational Complexity. Cybernetics and Computer Technologies. 2024. 2. P. 47–56. (in Ukrainian) https://doi.org/10.34229/2707-451X.24.2.5
References
1. Zadiraka V.K., Shvidchenko I.V. ε-solution of the problem. Collection of materials of the problem-scientific interdisciplinary conference “Information problems of computer systems, law, power engineering, design and management” (ISCM-2022)”, July 14–15, 2022. Nadvirna, 2022. P. 29–32. (in Ukrainian).
2. Zadiraka V.K. The theory of computing the Fourier transform. Kyiv: Naukova dumka, 1983. 216 p. (in Russian).
3. Zadiraka V.K., Tereshchenko A.M. Computer Arithmetics of Multi-Digits Numbers in Sequential and Parallel Calculation Models. Kyiv: Naukova Dumka, 2021. 136 p. (in Ukraine). https://books-nasu.org.ua/computer-arithmetics-of-multi-digits-numbers-in-sequential-and-parallel-calculation-models/
4. Sergienko I.V., Zadiraka V.K., Lytvyn O.M. Elements of the General Theory of Optimal Algorithms. Springer, 2021. P. 378. https://doi.org/10.1007/978-3-030-90908-6
5. Zadiraka V.K., Luts L.V., Shvidchenko I.V. Theory of integrals computing from fast oscillating functions. Kyiv: Naukova Dumka, 2023. 472 p. (in Ukrainian). https://doi.org/10.15407/978-966-00-1843-3
6. Zadiraka V.K., Melnikova S.S. Digital processing of signals. Kyiv: Naukova dumka, 1993. 294 p. (in Russian)
7. Weinstein C. Roundoff noise in floating point fast Fourier transform computation. IEEE Transactions on Audio and Electroacoustics. 1969. 17 (3). P. 209–215. https://ieeexplore.ieee.org/document/1162049
8. Welch P. A fixed-point fast Fourier transform error analysis. IEEE Transactions on Audio and Electroacoustics. 1969. 17 (2). P. 151–157. https://ieeexplore.ieee.org/document/1162035
9. Zadiraka V.K., Babych M.D., Berezovskyi A.I., Besarab P.M., Hnativ L.O., Liudvychenko V.O. T-efficient algorithms for the approximate solution of computational and applied mathematics problems. Kyiv-Ternopil: “Zbruch”, 2003. 261 p. (in Ukrainian).
10. Zadiraka V.K., Shvidchenko I.V. Using Rounding Errors in Modern Computer Technologies. Cybernetics and Computer Technologies. 2021. 3. P. 43–52. (in Ukrainian) https://doi.org/10.34229/2707-451X.21.3.4
11. Gold B., Rader C. Digital processing of signals. М.: Sovetskoe radio, 1973. 368 p. (in Russian).
12. Zadiraka V.K., Shvidchenko I.V. The influence of the quality of the estimation of the rounding error of the steganographic algorithm on its resistance. Mathematical and computer modelling. Series: Physical and mathematical sciences. 2015. 12. P. 101–112. (in Russian). http://mcm-math.kpnu.edu.ua/article/view/52691/48742
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Previous | FULL TEXT (in Ukrainian) | Next