Digital division for fast computing.

Digital division for fast computing

For a person working with only pencil and paper, dividing one large number into another can be a tedious struggle. The situation isn't much better for digital computers. Faced with 150-digit or larger numbers often encountered in applications such as message encryption, computers can also get bogged down. But a newly discovered mathematical technique may bring computer division up to speed.

Computer multiplication is already fast. Even while two numbers to be multiplied are being fed into the computer, standard methods allow the machine to start generating the answer immediately. In contrast, conventional techniques for division require a computer to "know" both numbers in full before beginning to divide one number into the other. For some large, fast computers, this bottle-neck is severe enough that to save time, the divisor is first divided into one, and then this result is multiplied by the dividend to give the answer.

The trick to speeding up computer division, says computer scientist Ernest F. Brickell of Bell Communications Research in Morristown, N.J., is to shift into a different number system at the right moment. In this arrangement, while all numbers are initially expressed in the ones and zeros (bits) of the binary number system, the results of a division are temporarily registered in a larger number system that also includes twos. After all the computations are finished, the final answers can easily be converted back into binary numbers.

This allows the computer to begin finding an answer even while the numbers to be divided are being read in. Only the first few bits of the divisor and the dividend are needed to start the process. A computer, after a very brief delay at the start, finishes such a computation in the same time it takes to read in the numbers.

The idea of temporarily shifting to a different number system isn't new, says Brickell. What is new is its use for speeding up division.

Brickell and his colleagues are now designing a computer chip that implements this division method. Details of Brickell's algorithm have yet to be published, and Bell Communications Research is applying for a patent on the process. Although this scheme may initially be most useful in cryptography, where high-precision division involving very large numbers is often needed, other applications are also likely to be developed.