Square Roots
June 1, 2012
The only trick to the bisection method is to properly initialize lo and hi depending on whether n is less than or greater than 1. Then iteration proceeds, replacing either lo or hi with mid, until mid is sufficiently close to the square root:
(define (bisect n)
(let loop ((lo (if (< 1 n) 1. n)) (hi (if (< 1 n) n 1.)))
(let ((mid (/ (+ lo hi) 2)))
(cond ((< (abs (- (/ (* mid mid) n) 1)) 1e-14) mid)
((< (* mid mid) n) (loop mid hi))
(else (loop lo mid))))))
Heron’s method is simple:
(define (heron n) ; x' = (x + (n/x)) / 2
(let loop ((x 1.))
(display x) (newline)
(let ((x-prime (/ (+ x (/ n x)) 2)))
(if (< (abs (- (/ (* x x-prime) n) 1)) 1e-14)
(/ (+ x x-prime) 2)
(loop x-prime)))))
So is Newton’s:
(define (newton n) ; x' = x - (x^2 - n) / 2x
(let loop ((x 1.))
(display x) (newline)
(let ((x-prime (- x (/ (- (* x x) n) (+ x x)))))
(if (< (abs (- (/ (* x x-prime) n) 1)) 1e-14)
(/ (+ x x-prime) 2)
(loop x-prime)))))
We cheated with the optimized method, using powers of 4 and the range [1,4), because it is easier to multiply by 2 than by the square root of 2.
(define (optimize n) ; using heron's method
(if (< n 1) (* 1/2 (optimize (* n 4)))
(if (<= 4 n) (* 2 (optimize (/ n 4)))
(let ((x (/ (+ 1. n) 2)))
(let ((x (/ (+ x (/ n x)) 2)))
(let ((x (/ (+ x (/ n x)) 2)))
(let ((x (/ (+ x (/ n x)) 2)))
(let ((x (/ (+ x (/ n x)) 2)))
(let ((x (/ (+ x (/ n x)) 2)))
x)))))))))
Here are some examples:
> (bisect 125348)
354.045194855119
> (bisect 0.8)
0.8944271909999202
> (heron 125348)
354.04519485512014
> (heron 0.8)
0.894427190999916
> (newton 125348)
354.04519485512014
> (newton 0.8)
0.894427190999916
> (optimize 125348)
354.04519485512014
> (optimize 0.8)
0.894427190999916
You can run the program at http://programmingpraxis.codepad.org/RomAjszt.
There are other ways to compute the square root, though in practice it is hard to beat the optimized version of Heron’s method shown above. In the twelfth century, the Indian mathematician Bháscara Achárya developed an algorithm for computing square roots based on continued fractions, which was rediscovered five hundred years later by Lord William Brouncker; it is known as the Bháscara-Brouncker algorithm. In the eighteenth century, the Maclaurin series
has been found, though it is quite slow to converge and hence is seldom used.
Programming Praxis 
Not sure if this is something I can fix client-side (please let me know if so), but I recommend for future posts using a more appropriate font (or some TeX variant like you are using on the solutions page for this exercise) when presenting numeric symbology.
For instance, the differentiation symbol used on the denominator of Newton’s method is barely visible. So at first glance, it looked like you made a typo and we were to perform “x_{k+1} = x_{k} – 1”.
Maybe its just the italics that makes it hard to read, but if future exercises use any equations not so familiar to us (unliked Newton’s method), it would be disappointing to work with incorrect equations simply because the typesetting was too difficult to read.
Just my two cents, and keep up the great exercises!
P.S. I would like to see some of these solutions come up with a clever approximation seed used for the Alexandrian/Babylonian method. Wikipedia has a good example, but I would be interested if there are any better solutions geared towards computer algebra.
Ardnew: Regarding math: WordPress, where I host the blog, does a bad job with math. They provide LaTeX with the dollarsign-latex command, but then it doesn’t resize with the text, so it looks more-or-less ugly depending on the text size. And it uses LaTeX inline mode even in displays, which is just wrong, as you will notice on the solution page of this exercise. Writing out math using HTML characters can work either well or poorly depending on the browser — it looks much better on my browser at home, where I generally write these exercises, than at work (both are Chrome, but they render quite differently); when I have trouble, I increase the text size in the browser. The proper solution is jsmath, but that requires me to host my own web site, which I prefer not to do, as I prefer to spend my limited time writing exercises than administering a web site (and since my site generates no revenue, I prefer to use the free hosting at WordPress). Thanks for the suggestion, but I think my best advice is just to increase the text size in your browser (or squint). If that doesn’t work, I have noticed that printing the exercise often provides a much better visual experience than reading it on-screen. And if you are still unclear, you can always view source (but be prepared to gag at all the junk that WordPress adds).
The clever approximation method that you mention usually takes the number of digits in x, divides by 2 (integer division) and subtracts 1, then sticks a 2 on front of that many zeroes if the original number of digits was even and a 6 on front of that many zeros if the original number of digits was odd. For instance, our example 125348 has six digits, then 6/2-1 = 2 so we have two zeroes, and the approximation is 200. A similar procedure is followed when x is less than 1. Fancier approximation methods have more starting points in the “lookup table” than 2 or 6. But the effect of a clever approximation is seldom more than a reduction of a single step in the iteration, and since the cost of computing the clever approximation is about the same as the cost of a single step, there is generally little saving. Where good approximations can work is where the range of x is sufficiently restricted (say, 32-bit integers) that a good approximation can save two or three steps in the iteration. If you use the “optimized” method mentioned in the exercise that restricts x to the range 1 ≤ x < 2 (or 4), it might be possible with some experimenting to find a clever approximation that actually does pay for itself; perhaps you would like to study this topic and report back to the rest of us.
Note that heron and newton are essentially the same (they generate the same iterates in exact arithmetic).
my version, i didn’t implement the last one because i was unclear of the algorithm.
http://pastebin.com/3YVeMVCY
[…] I discuss this algorithm, and three other algorithms for calculating square roots, at my blog. […]
[…] I discuss this algorithm, and three other algorithms for calculating square roots, at my blog. […]
[…] 牛顿的方法在整数上工作得很好： class=”lang-python prettyprint-override”> def isqrt(n): x = n y = (x + 1) // 2 while y < x: x = y y = (x + n // x) // 2 return x [/code] 这将返回x * x不超过n的最大整数x。如果你想检查结果是否恰好是平方根，只需执行乘法来检查n是否是一个完美的正方形。 我讨论这个算法，以及另外三个计算平方根的算法my blog […]
[…] I discuss this algorithm, and three other algorithms for calculating square roots, at my blog. […]
[…] I discuss this algorithm, and three other algorithms for calculating square roots, at my blog. […]
[…] I discuss this algorithm, and three other algorithms for calculating square roots, at my blog. […]
[…] I discuss this algorithm, and three other algorithms for calculating square roots, at my blog. […]
[…] I discuss this algorithm, and three other algorithms for calculating square roots, at my blog. […]
[…] I discuss this algorithm, and three other algorithms for calculating square roots, at my blog. […]
[…] Discuto este algoritmo, y otros tres algoritmos para calcular raíces cuadradas, en mi blog. […]
[…] I discuss this algorithm, and three other algorithms for calculating square roots, at my blog. […]