2021, issue 2, p. 39-56
Received 12.03.2021; Revised 24.03.2021; Accepted 24.06.2021
Published 30.06.2021; First Online 01.07.2021
https://doi.org/10.34229/2707-451X.21.2.4
Previous | Full text (in Ukrainian) | Next
Generating Big Numbers for Testing Multi-Digit Arithmetic Algorithms
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 computational systems, such as multi-core processors, clusters, distributed systems, is due to the solution of various applied problems in various fields. The difference between devices for which parallel algorithms are implemented causes a variety of existing methods for parallelizing the calculation of multi-digit arithmetic operations. There is a problem of developing universal algorithms for implementing multi-digit arithmetic operations that are efficiently performed on various devices and on various systems.
Very often it is not possible to develop a new algorithm, since at this stage there is still no test data with which it is possible to analyze the result of calculation. Therefore, the task of preparing test data and results is no less important than the development of the algorithm itself. The quality of the prepared data determines the quality of the implemented algorithm and the time required to find and eliminate errors in the algorithm-program and its implementation.
In this paper, some simple dependencies are given, using which you can visually check the correctness of the calculation of multi-digit operations of addition, subtraction, multiplication, multiplication by modulo and exponentiation by modulo. Simple algorithms for generating input and output multi-digit data are presented. Using dependencies allows to check the integrity of the output when delegating computations to distributed systems such as cloud computing.
The purpose of the article is to show simple dependencies between the input data and the results of performing multi-digit operations of addition, subtraction, multiplication, multiplication by modulo and exponentiation by modulo. For the given dependencies, methods for generating input and output multi-digit numbers are shown, which can be used to check the correctness of the calculation of multi-digit operations, which significantly saves the time required for preparing test data.
Dependencies are provided in a generic way, which allows you to generate input data and results for devices that operate on words of different lengths (8, 16, 32, 64, 128, 256, etc. bits).
Results. The dependences between the input data and the results of performing multi-digit operations are analyzed. The provided dependencies are proved in the form of lemmas. The dependencies are presented in a general form, since to generate multi-digit sequences, it is needed to set two parameters: N – the number of digits in the multi-digit value and n – the length of the digits in bits. The examples show the generation of input data and results for various multi-digit operations.
Conclusions. The paper presents dependencies that are easy to remember and use for visual verification of the results of multi-digit calculations without using additional or special software or hardware, which allows to devote the saved time to developing new or more efficient modifications of multi-digit algorithms.
Keywords: multi-digit arithmetic, parallel computational model.
Cite as: Tereshchenko A., Zadiraka V. Generating Big Numbers for Testing Multi-Digit Arithmetic Algorithms. Cybernetics and Computer Technologies. 2021. 2. P. 39–56. (in Ukrainian) https://doi.org/10.34229/2707-451X.21.2.4
References
1. Zadiraka V., Oleksyuk О. Computer arithmetic of the multidigit number. Kyiv: Naukove vydannya, 2003. 263 p. (in Ukrainian)
2. 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
3. Nykolaichuk Y, Vozna N., Pitukh I. Design of specialized computer systems. Ternopilʹ: Terno-Hraf. 2010. 392 p. (in Ukrainian) http://library.kpi.kharkov.ua/uk/inftechnologies_nik
4. Khimich A. Supercomputer technologies and mathematical modeling of complex systems. Visnyk NAN Ukrayiny. 2018. 5. P. 69−72. (in Ukrainian) http://dspace.nbuv.gov.ua/handle/123456789/140740
5. Novokshonov A. Checking the integrity of arithmetic calculations. Materiali XIV Mizhnarodnoyi naukovo-praktichnoyi konferentsiyi «Teoretichni ta prikladni aspekti pobudovi programnih system». 2017. P. 149–154. (in Ukrainian)
6. Anisimov A.V. Multi-digit algorithmic theory. Multi-digit modular arithmetic. Kyiv: Vidavnichiy dim “Akademperiodika”. 2001. 153 P. (in Ukrainian) http://books.zntu.edu.ua/book_info.pl?id=21106
7. 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
8. Davis W.F. A class of efficient convolution algorithms. Applicat. Walsh Functions. 1972. March. P. 318–329.
9. 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
10. Anisimov A.V., Novokshonov A. Verifiable Arithmetic Computations Using Additively Homomorphic Tags. IEEE Advanced Trends in Information Theory. 2019. P. 93–96. https://doi.org/10.1109/ATIT49449.2019.9030485
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Previous | Full text (in Ukrainian) | Next