Задача 255: Скругленные квадратные корни
Мы определяем круглый квадратный корень положительного целого числа n в виде квадратного корня из n, округленного до ближайшего целого числа.
Следующая процедура (по существу, метод Херона, адаптированный к целочисленной арифметике) находит округленный квадратный корень из n: пусть d - число цифр числа n. Если d нечетно, задайте x0 = 2 × 10 (d-1) / 2. Если d четно, задайте x0 = 7 × 10 (d-2) / 2. Повторение:
пока xk + 1 = xk.
В качестве примера найдем закругленный квадратный корень n = 4321.n имеет 4 цифры, поэтому x0 = 7 × 10 (4-2) /2 = 70. Так как x2 = x1, остановимся здесь. Итак, после двух итераций мы обнаружили, что квадратный корень из 4321 равен 66 (фактический квадратный корень равен 65.7343137 ...).
Число итераций, требуемых при использовании этого метода, на удивление низкое. Например, мы можем найти закругленный квадратный корень из 5-значного целого числа (10 000 ≤ n ≤ 99,999) со средним значением 3.2102888889 итераций (среднее значение округлено до 10 знаков после запятой).
Используя описанную выше процедуру, каково среднее число итераций, необходимых для поиска округленного квадратного корня 14-значного числа (1013 ≤ n <1014)? Дайте ваш ответ округленным до десяти знаков после запятой.
Примечание: Символы ⌊x⌋ и ⌈x⌉ представляют функцию пола и функцию потолка соответственно.