Hacker News Reader

Comment by btilly | Hacker News Reader

I have a better proposal than the last line. Just repeat Heron's method, using the approximate square root.

In the article they find that sqrt(33) is approximately 5.75 = 5 3/4. Square that and we get 25 + 2 * 15/4 + 9/16 = 33 1/16 = g.

Now we want n / g = 33 / 5.75 = 33 / (23 / 4) = 132 / 23 = 5 17/23.

Average that with g and we get (5 3/4 + 5 17/23)/2 = (5 69/92 + 5 68/92)/2 = 5 137/184 = 5.74456217... The actual answer is 5.74456264...

What's going on here is that we're using Newton's method, and doubling the number of digits of accuracy every time. By contrast the Taylor series is only adding a fixed number of digits for each term. So "do the simple stupid thing, take feedback, iterate" is far better "do the complex thing right the first time".

That's a lesson from math that is widely applicable everywhere. Such as for running startups.

View on HN

The slightly easier version is to use Heron's method, but know the squares of half-integers. They are: 2.25, 6.25, 12.25, 20.25, 30.25, 42.25, 56.25, 72.25, 90.25. You might notice there is a similar pattern to these as the familiar odd-number increments in the sequence of integer squares. It also happens that (n + 1/2)^2 = n(n + 1) + 0.25

The iterated method tends to double the number of bits of accuracy at each iteration. Moving from integers to half-integers gives you one more bit of accuracy on average. When you apply the first iteration, this becomes two extra bits.

This already gives accuracy within 0.2% in one step for any integer (except 3 and 5, with errors of 1.0104% and 0.6231% respectively).

I‘m sorry, can you show an example of where this helps in the usage of Heron‘s Method?

Here are the results for numbers up to 50:

http://codepad.org/NBmpZGpT

The advantage simply comes from getting a better initial guess in some cases. When the test number is halfway between two perfect squares, the advantage is maximized -- for 30 we get 5.5 for the one method and 5.47727~ for the other, with a true value of 5.47722~. For some numbers, like 35, the integer square is closer than the half-integer, so the results are the same, but these are also the numbers with the best approximations to start with.

You don't actually even have to know the squares of half integers, though.

Like, if you're looking for sqrt(30) and you're trying to decide 'should I use 5 or 6 as my first estimate?'... you don't actually care, just pick 5.5. You're looking for a decent estimate, and in that situation you can tell 5.5 is going to be a better one than either 5 or 6, without actually knowing or caring what 5.5^2 actually is.

Likewise if you're going for sqrt(33) you could take a reasonable guess that 5.75 will be a better starting estimate than either 5.5 or 6, just by gauging roughly where 33 sits on the logarithmic scale between 25 and 36.

The point of Heron's method, though, is that no matter your starting estimate, it is guaranteed to be even closer to the right answer. So even if your mental logarithmic estimate is really well attuned and you think 'yeah, 33 looks like about 5.74 squared', Heron can refine that to 5.7446.

Reply on news.ycombinator.com