Paeth’s Method (Square Roots, Part VII)

March 13, 2018

In Graphics Gems [1], Paeth proposes a fast (but quite approximate) method for the rapid computation of hypotenuse,

\displaystyle h=\sqrt{x^2+y^2}.

The goal here is to get rid of the big bad \sqrt{} because it is deemed “too expensive”—I wonder if that’s still actually true. First, he transforms the above equation:

Read the rest of this entry »


Square roots (Part VI)

February 20, 2018

I’ve discussed algorithms for computing square roots a couple of times already, and then some. While sorting notes, I’ve came across something interesting: Archytas’ method for computing square roots.

Archytas’ method is basically the old Babylonian method, where you first set

a=1,

b=n,

and iterate

\displaystyle a'=\frac{a+b}{2},

\displaystyle b'=\frac{n}{a'}=\frac{2n}{a+b},

until desired precision is achieved (or the scribe is exhausted).

Read the rest of this entry »


The infinite radicals of Ramanujan

November 29, 2016

What if I asked you to find the numerical value of

\displaystyle \sqrt{1+2\sqrt{1+3\sqrt{1+4\sqrt{1+5\sqrt{1+6\sqrt{\cdots}}}}}} ?

If you have difficulty figuring out what this thing is, don’t worry. You’re not the only one. This question is one the problems posed by Srinivasa Ramanujan, one of the most brilliant and, well, mysterious mathematicians of all time. In fact, it was head enough that Ramanujan had to give the answer a few months later.

Read the rest of this entry »


Square Roots (Part V)

November 15, 2016

Last week we examined the complexity of obtaining k in the decomposition n=2^k+b for some integer n. This week, we’ll have a look at how we can use it to speed-up square root extraction. Recall, we’re interested in k because

2^k \leqslant 2^k+b < 2^{k+1},

with 0 \leqslant b < 2^k, which allows us to get easy bounds on \sqrt{n}. Better, we also have that

\sqrt{2^k} \leqslant \sqrt{2^k+b} \leqslant \sqrt{2^{k+1}},

and we know how to compute \sqrt{2^k}=2\frac{k}{2} (somewhat efficiently! Let’s combine all this and see how it speeds up things.

Read the rest of this entry »


Square Roots (part IV)

November 8, 2016

In a previous post, we noticed that

\sqrt{2^k} \leqslant \sqrt{n} = \sqrt{2^k+b} \leqslant \sqrt{2^{k+1}},

where 0 \leqslant b < 2^k, could be used to kick-start Newton's (or another) square root finding algorithm. But how fast can we find k and b in this decomposition?

Read the rest of this entry »


Yet Another Square Root Algorithm (part III)

October 4, 2016

Finding good, fast, and stable numerical algorithms is usually hard, even for simple problems like the square root, subject we’ve visited a number of times. One method we haven’t explored yet, is using the Taylor series. The Taylor series for \sqrt{n} around a is given by:

\displaystyle \sqrt{n}=\sqrt{a}+\frac{1}{2}\frac{n-a}{\sqrt{a}}-\frac{1}{8}\frac{(n-a)^2}{a^{3/2}}+\frac{1}{16}\frac{(n-a)^3}{a^{5/2}}+\cdots

Can we exploit that to compute efficiently, and with some precision, square roots?

Read the rest of this entry »


OB Sqrt

December 22, 2015

I have discussed the problem of efficient square root calculation quite a few times. And yet, while reading Rudman’s The Babylonian Theorem, I found yet another square root algorithm. The Old Babylonian square root algorithm. Let’s have a look on how it works.

wood

Read the rest of this entry »