3 ms·
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.
by scythe 4y ago
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).
- selfmodruntime 4y agoI‘m sorry, can you show an example of where this helps in the usage of Heron‘s Method?
- scythe 4y agoHere are the results for numbers up to 50: http://codepad.org/NBmpZGpT 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.
- jameshart 4y agoYou 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.