Problem 255

Rounded Square Roots

We define the *rounded-square-root* of a positive integer `n` as the square root of `n` rounded to the nearest integer.

The following procedure (essentially Heron's method adapted to integer arithmetic) finds the rounded-square-root of `n`:

Let `d` be the number of digits of the number `n`.

If `d` is odd, set `x`_{0} = 210^{(d-1)⁄2}.

If `d` is even, set `x`_{0} = 710^{(d-2)⁄2}.

Repeat:

until `x`_{k+1} = `x`_{k}.

As an example, let us find the rounded-square-root of `n` = 4321.`n` has 4 digits, so `x`_{0} = 710^{(4-2)⁄2} = 70.

Since `x`_{2} = `x`_{1}, we stop here.

So, after just two iterations, we have found that the rounded-square-root of 4321 is 66 (the actual square root is 65.7343137…).

The number of iterations required when using this method is surprisingly low.

For example, we can find the rounded-square-root of a 5-digit integer (10,000 `n` 99,999) with an average of 3.2102888889 iterations (the average value was rounded to 10 decimal places).

Using the procedure described above, what is the average number of
iterations required to find the rounded-square-root of a 14-digit number
(10^{13}`n` 10^{14})?

Give your answer rounded to 10 decimal places.

Note: The symbols `x` and `x` represent the floor function and ceiling function respectively.

**
These problems are part of
Project Euler
and are licensed under
CC BY-NC-SA 2.0 UK
**