Multiplier-Free Divide, Square Root, and Log Algorithms [DSP Tips and Tricks]

Many signal processing algorithms require the computation of the ratio of two numbers, the square root of a number, or a logarithm. These operations are difficult when using fixed point hardware that lack dedicated multipliers, such as low-cost microcontrollers, application specific integrated circuits (ASICs), and field programmable gate arrays (FPGAs). This article presents straightforward, multiplier free algorithms that implement both division and square roots, based on a technique known as dichotomous coordinate descent (DCD) (See [1] as a starting point, where several articles by the same authors are referenced.) We also make available a multiplier-free logarithm algorithm. All these algo rithms are based on iterative methods, which compute the successive ele ments of a sequence of approximate solutions, just like the Gauss-Seidel, Jacobi, and conjugate gradient methods [2]. We begin our discussion with a scheme for computing the ratio of two real numbers.