Re:Did any processor implement an integer square root instru...
by masswerk on Sunday April 07, 2024 @11:12AM
(#39961291)
Compare the integer square root algorithm used in "Spacewar!" [1]. So, even by 1960 it should have been possible to implement a square root step instructions for each bit, much like division or multiplication shifts, and progress from this to full-fledged automatic operations by the use of a sub timing network. (I guess, it really depends on the economics of the individual use case, whether the effort does pay off or not, as you would amass a few additional hardware modules to accomplish this.)
[1] https://www.masswerk.at/spacewar/inside/insidespacewar-pt6-g...
n2_new = (n_old + (1 << bit))^2 = n2_old + (n_old << (bit + 1)) + (1 << (bit*2))
Then compare it with the source operand, and if it's greater or equal: 1) set the bit in the result 2) update n2_old with n2_new
It can be done in n/2 or perhaps n clock cycles with a suitable microcode instruction set and ALU. With some effort it can be optimized to reduce n to the index of the leftmost set bit in the operand.