Methods of Combating the Accumulation of Rounding Error When Solving Problems of Trans-Computational Complexity

Abstract

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