0

My question is about using prescaling for Heron's Algorithm as described in on page 4 in this textbook: http://assets.press.princeton.edu/chapters/s9487.pdf

I am able to understand that we are limiting our solution only to nonnegative numbers since we are searching for real roots. But I do not follow why this textbook has chosen the interval of $[\frac{1}{2}, 2]$ and the corresponding transformation of $$\tilde{y} = 4^k y$$ if $y\not\in[\frac{1}{2},2]$ for some integer $k$. Both the transformation and the interval appear arbitrarily chosen and I am wondering how to generalize and understand the scaling for other values and since the remainder of the chapter seems to require understanding this transformation.

Andrew Shedlock
  • 2,559
  • 3
    The idea is to reduce the problem to find the square root within the given interval. Every positive real number can be written in the given way such that $y$ is in the desired interval and the square root of $4^k$ is just $2^k$ – Peter Jul 20 '18 at 11:37

1 Answers1

1

Heron's algorithm converges quadratically, but only if your start value is not far away from the true root (in relative terms). By applying the algorithm to numbers $y$ in the interval $\bigl[{1\over2},2]$ and starting with $x_0=1$ we make sure that ${x_0/\sqrt{y}}$ is pretty close to $1$.

If the start value $x_0$ is (relatively) far away from the true root then during the first steps of the algorithm the relative error is only halved (and not squared) at each step (see page $6$ of the text). The suggested prescaling (which is for free in binary) allows to start right away with a "sensible" approximation to the true root.

Christian Blatter
  • 226,825
  • So if we were trying to find the square root of $9$, we would want to perform the transformation $\tilde{y} = 4^{-2}(y) = \frac{9}{16}$ and then use $x_0 = 1$ until we can find a fixed point using Heron's algorithm. After find the fixed point we should then multiply by $2^2$ to calculate the square root of 9? This would allow us to calculate the root quicker and we are using $2^k$ since it would just be a simple bit shift? – Andrew Shedlock Jul 20 '18 at 15:44
  • 2
    That's exactly what I tried to explain. – Christian Blatter Jul 20 '18 at 19:11