Index O'Stuff
Home Compression Arithmetic CodingBurrows-Wheeler Transform Huffman Coding LZSS Coding LZW Coding Run Length Encoding Misc. Programming School ProjectsThesis Project crypt(3) Source Hamming Codes Bit Manipulation Libraries Square Root Approximation Library Sort Library Trailing Space Trimmer and Tab Remover Command Line Option Parser Humor Dictionary O'Modern TermsThe Ten Commandments of C Style Other Stuff TOPS Success StoryFree Win32 Software External Links SPAN (Spay/Neuter Animal Network)Los Angeles Pet Memorial Park Mirrors
Pages at geocitiesPages at dipperstein.com Obligatory Links
Visits since I started counting: |
Square Root Approximation LibraryThis is the results of yet another adventure that started with me reading something and wanting to know more about it. July 30, 2003 John N. Power (jpower@bcpl.net) posted a message to the PICList which mentioned the ENIAC (Electronic Numerical Integrator and Computer) and it's square root algorithm. John published a paper on the algorithm, which may be found at http://www.bcpl.net/~jpower/ezsqrt.pdf. Additional searches revealed a Brian Shelburne's well written How the ENIAC took a Square Root. Both papers make it clear how the algorithm works, the latter even provides some improvements. Something just made me want to code it up and play with it. I knew the ENIAC algorithm was not the most efficient algorithm, and wanted to compare it to two other methods that I knew about: bisection and successive approximation. So I ended up writing simple code for comparison testing. I am releasing my implementations of the ENIAC square root algorithm and all the other approximation methods under the LGPL. A zipped archive of the source files and all the necessary build information may be obtained here. The source is ANSI-C source that I compiled under Linux and Windows 98 using gcc and GNU make, but it should be easily ported to any other ANSI-C environment. ENIAC AlgorithmMy general laziness and the fact that Brian Shelburne's paper did such a good job of explaining the ENIAC algorithm are preventing me from describing the algorithm. My source implements his algorithm with only one deviation. Brian Shelburne noted that the sum of odd multiples of 100 is also a square. This generalizes to the sum of odd multiples of a square being a square. Most modern computers perform binary math, which is not well suited to multiplying and dividing by 100. In an attempt to ease computation, I experimented by trying odd multiples of 64 and 256, allowing multiplications and divisions to be converted to shifts. As it turns out, there are only three multiplications and divisions. The time saved by changing the square used is less significant than the time saved by allowing quicker convergence to an answer. The smaller the square multiple used, the faster the algorithm converges (64 converges faster than 100). However, the smaller the multiple, the less accurate the result. If you play with the source, you might want to tweak the multiple (radix) defined in sqrt.h. Successive Approximation AlgorithmSuccessive approximation is an iterative algorithm for approximating the
square root of a number. The algorithm is based on the following
observations: Using equation (3) repeatedly allows an approximation for the square root of N to be continuously refined. The refinement of the approximation may be stopped once the difference between successive approximations is less than some threshold. Bisection AlgorithmBisection is another iterative process used to approximate the square
root of number. The algorithm works by repeatedly reducing the range of
values which the square root of a value is known to exist in. Given an
initial value N and an approximate square root guess of x,
the bisection algorithm is implemented using the following steps: *NOTE: For N between 0 and 1, set the lower bound to 0 and the upper bound to 1. If you have any further questions or comments, you may contact me by e-mail. My e-mail address is: mdipper@alumni.engr.ucsb.edu |
Home
Last updated on August 30, 2007