Division of a Natural Number by Two: A Cellular Automata-Based Approach

Cellular automata are mathematical models for systems that consist of large numbers of simple identical components with local interactions. The simple components act together to produce complicated patterns of behavior that are especially suitable for modeling natural systems. Division by two or halving has been of special importance among the division operations and investigated separately in the literature. One of the most important factors in performing division operations is the speed of calculations. This paper proposes a new method, DN2, for dividing a natural number by two to speed up the calculations. Then, using the parallel property of block cellular automaton, a method for implementing DN2, called D2CA, with two rules is presented. Experimental results indicate that D2CA has an average of 28.11% less execution time than the Replacement algorithm. Also, some mathematical properties of D2CA are analyzed, and as a case study, the application of D2CA in cryptography is investigated.