This article is cited in 1 paper

Part 3. Mathematical models

Fast algorithms for multiplication and division of natural numbers using cellular automata with locators

È. È. Gasanov^a, B. F. Khaybullin<sup>b

a</sup> Lomonosov Moscow State University, Faculty of Mechanics and Mathematics
^b Elius LLC

Abstract: For multiplication and division of $n$-digit natural numbers, algorithms with complexity of order $ n^{\log_2 3} $ and even order $ n^{\log n} $ are known. In this paper, an algorithm for multiplying $n$-digit natural numbers in $2n + 2$ cycles is proposed. Here, the digit of number a is understood as the number $ ]\log_2 a[ $. For division of natural numbers with remainder, an algorithm with a running time of $3n + 8$ cycles is proposed, where n is the digit of the quotient. The proposed algorithms use two-dimensional cellular automata with locators as calculators.

Keywords: multiplication of natural numbers, division of natural numbers, cellular automata with locators