Performance analysis of arithmetic algorithms implemented in C++ and Python programming languages

A.K. Novokshonov

Abstract


This paper presents the results of the numerical experiment, which aims to clarify the actual performance of arithmetic algorithms implemented in C ++ and Python programming languages using arbitrary precision arithmetic. "Addition machine" has been chosen as a mathematical model for integer arithmetic algorithms. "Addition machine" is a mathematical abstraction, introduced by R. Floyd and D. Knuth. The essence of "addition machine" is the following: using only operations of addition, subtraction, comparison, assignment and a limited number of registers it is possible to calculate more complex operations such as finding the residue modulo, multiplication, finding the greatest common divisor, exponentiation modulo with reasonable computational efficiency. One of the features of this implementation is the use of arbitrary precision arithmetic, which may be useful in cryptographic algorithms.

Problems in programming 2016; 2-3: 26-31


Keywords


C++; Python; GMP; addition; subtraction; greatest common divisor; exponentiation; Fibonacci numbers

References


Tiobe.com. Tiobe Index | Tiobe - The Software Quality Company. [online] Available at: http://www.tiobe.com/tiobe_index [Accessed 10 Feb. 2016].

Pypl.github.io. PYPL PopularitY of Programming Language index. [online] Available at: https://pypl.github.io/PYPL.html [Accessed 10 Feb. 2016].

Floyd R. and Knuth D. Addition Machines. SIAM J. Comput. - 1990. - 19(2). - P. 329-340.

https://doi.org/10.1137/0219022

Anisimov A.V. Algorithmic Theory of Large Numbers. Modular Arithmetic of Large Numbers [in Ukrainian], Akademperiodika, Kyiv. - 2001.

Gmplib.org. The GNU MP Bignum Library. [online] Available at: https://gmplib.org/ [Accessed 10 Feb. 2016].

Prechelt L. An empirical comparison of C, C++, Java, Perl, Python, Rexx and Tcl // IEEE Computer. - 2000. - 33(10). - P. 23-29.

https://doi.org/10.1109/2.876288

Rivest R., Shamir A. and Adleman L. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM. - 1978. - 21(2). - P. 120-126.

https://doi.org/10.1145/359340.359342




DOI: https://doi.org/10.15407/pp2016.02-03.026

Refbacks

  • There are currently no refbacks.