|
|
|
NOTE: The integer square root algorithms tested by this program are described in greater detail in "Fast Integer Square Roots".
squint tests various
integer square root algorithms, including nbrUnsignedSQRT() in
LIBGPL's NBR_UTIL package.
Mostly I use the program for benchmarking the algorithms.
The default integer square root function is nbrUnsignedSQRT().
Other functions that can be specified on the command line are:
"alternate" - an alternate function used to test changes
that will, if they work, eventually be incorporated into
nbrUnsignedSQRT().
"crenshaw" - is Jack Crenshaw's integer square root function. His original column, "Integer Square Roots", appeared in Embedded Systems Programming, February 1, 1998. The web page is missing the images and code listings, however the code listings can be found at https://cms.edn.com/uploads/SourceCode/cren98_21.txt.
The algorithm is also explained in identical or more detail in chapter 4 of his book, Math Toolkit for Real-Time Development, later renamed Math Toolkit for Real-Time Programming. The code I used is the one presented in Listing 4 of his column and Listing 4.7 of his book. (If you know how to use Google, you can find chapter 4 online at Google books.)
"martin" - is Martin Buchanan's function, which bears some resemblance to Crenshaw's function. I used his 3rd integer square root function found at the Code Codex:
http://www.codecodex.com/wiki/Calculate_an_integer_square_root#C
(The 3rd function is identical to his second function, but with different variable names.)
"ross" - is my original (i.e., first) interpretation of Ross Fosler's algorithm:
"Fast
Integer Square Root" by Ross M. Fosler
Application Note TB040, DS91040A, © 2000 Microchip Technology Inc.
"tristan" - is Tristan Muntsinger's integer square root function, which is a variation of Ross Fosler's algorithm. Martin Buchanan included this function on the same Code Codex page:
The "crenshaw", "martin", and "tristan" functions were modified to
work at different precisions and were tested using 64-bit unsigned
longs. All the functions use the same, one-time determination of
precision as nbrUnsignedSQRT(). I don't yet understand
how they work, so my versions of Crenshaw's and Martin's functions
bail out when faced with odd-precision integers.
% squint [-debug] [-help]
[-repeat count] [-time]
number[,alt|crenshaw|martin|ross|tristan]
where
-debug- turns debug on.
-help- prints out a help message.
-repeat count- repeats the square root computation the specified number of times. A single computation takes too little time to make meaningful comparisons between algorithms. On my computer, calculating the square root of 1234567892 ten million times produced times under 2 seconds for the various algorithms; repeating the calculations 100 million times resulted in times in the 10-20-second range, thus providing more granularity for comparison purposes.
-time- measures and displays the time it takes to compute the square root (or count iterations of the computation if "-repeat count" is also given on the command line). Almost all output is suppressed to keep I/O from affecting the timing.
- number[,
alternate|crenshaw|martin|tristan]- prints the integer square root of the number. The optional argument after a comma (no spaces!) specifies an alternate, integer square root function (all of which are compiled into this program):
I use this capability for benchmarking different algorithms. You can abbreviate the names to any length, so I usually just specify one letter; e.g., "squint 144,m" will compute the square root of 144 using Martin's algorithm. If the optional argument is not present, the default function is LIBGPL's
- "alternate" - is an alternate function I use to test changes I'm going to make to
nbrUnsignedSQRT().- "crenshaw" - is Jack Crenshaw's integer square root function.
- "martin" - is Martin Buchanan's function.
- "ross" - is Ross Fosler's function.
- "tristan" - is Tristan Muntsinger's function.
nbrUnsignedSQRT(). The file prologue above lists the URLs for the named functions' documentation or code.