Picking an appropriate "guess" for Heron's Method and The Fast Reciprocal Method

Question

I've been thinking for a while about writing some code that would use Heron's Method and the Fast Reciprocal Method.

Heron's Method
This finds the approximation of $ \sqrt{S} $. The initial guess is $ G_0 $

The update formula is:

$$ G_{n+1} = \frac{1}{2}(G_n + \frac{S}{G_n}) $$

The heuristic for which is $ G_n^2 \approx S \Rightarrow G_n \approx \sqrt{S} $

Fast Reciprocal Method
This finds an approximation of $ \frac{1}{D} $

The update formula is:

$$ G_{n+1} = G_n(2 - DG_n) $$

The heruistic for which is $ DG_n \approx 1 \Rightarrow G_n \approx \frac{1}{D} $

The method's themselves are relatively easy but the problem that I am having is thinking of how I can devise a reasonable initial guess $ G_0 $.

This is the only part that I really need some help on because as most of you already know these methods can be very convergent but without a reasonable initial guess they may converge very slowly or diverge completely.

Any help on finding a method to find $ G_0 $ is highly appreciated.

Answer 1

If you can use frexp then do: for a number $x\ne0$, frexp gives you $u\in [1/2, 1)$ and $k$ such that $x=u2^k$. For the square root, you can take $G_0=2^{k/2}$. For the reciprocal, you can take $G_0=2^{-k}$. Use ldexp to obtain these powers of $2$.