|
   |
© 2000 Pedro Freire |
|
|
|
|
© 2000 Pedro Freire |
This is an addendum to the second part of the square root algorithm. It holds submissions and suggestions sent by readers. I have reviewed these, but I did not take the time with them that I took with my algorithms (unless they were faster, and none has shown up so far). This means there may be errors or inaccuracies. It also means this page will only show such algorithms without analysing them further. Please contact the authors for more information.
When I published my square root algorithm, there was a north-american university professor who replied to me. Unfortunately he replied to a temporary e-mail address I used to advertise the algorithm on the Usenet News, and when I got back to review his message, it had already been deleted by the system.
I do remember however, the basis of his argument. My algorithm is iterative. True. And the most advanced algorithms today are sequential: which in fact makes them faster. But... sequential algorithms use several operations that are inherently iterative, or too expensive to implement sequentially in hardware: let's take multiplication as an example.
Multiplication is inherently iterative: for each binary digit in one of the operands, we add or don't add the other operand (properly shifted) to the result. This operation can be implemented by a circuit based in Moore tables, which makes it extremely fast (typically 1 clock cycle), but takes up lots of silicon space. The first Alpha processor implemented multiplication in this way, and half of this circuit's silicon space (and hence half its cost) was taken by the multiplication operation.
This means that the basic operations in existing sequential square root algorithms are not all that fast themselves. The basic operations used in my algorithm are ANDs, ORs, additions and subtractions which can easily be implemented in 1 clock cycle each. Furthermore, the iteration loop can also be unfolded in order to have only half the number of iterations or less.
It would have been nice to be able to argument with this professor about these issues, but by losing his message, I lost all and any contact of him. If you're him, please contact me!
