The Best Square Root Method Algorithm

codeproject.com

3 points·jfaucett··3 comments

I really wish this article had explained how each method works. It's going to take me some time to analyze each method to see whether any of them are the method I was taught in elementary school.

It extracts the square root to any desired precision one digit at a time and it looks a lot like long division. In binary you get one bit at a time and there is no guesswork so it goes pretty quickly.

I found the method I was taught at https://en.wikipedia.org/wiki/Methods_of_computing_square_ro... under the heading Digit-by-digit calculation.

It does not appear that this matches any of the methods tested. A long time ago I implemented it in assembly for integers. It should be possible to write a floating point version but my programming experience has been in embedded systems and I never needed floating point. I would need to study floating point representation but don't have much interest.

I did a similar comparison last year, but mine was for an embedded system with no FPP (MSP430). I was able to shave more than half of the average execution time compared to the (highly optimized TI) math library function. The only drawback to my method was that it would fail for input values greater than 255. Fortunately my application was guaranteed to never supply an input value greater than 240.

Reply on news.ycombinator.com