p = 0, r = b,
p = а − 2b, r = a − b,
p = 4 (a − b), r = 2a − b,
первый случай — единственный, в котором квадратный корень из n сравним с 1 по модулю 4; два других дают квадратный корень, сравнимый с 3 по модулю 4. При выходе из цикла равенство
b = ар + b2
с учетом соотношений p < a, b < a дает n < 2a2 и, следовательно, при выходе из цикла a2 > n/2. Равенство
ар = n − b2
дает p = (n − b2)/a < n/а.
Если окажется, что n/а < a, то непременно p < а и цикл закончен. Чтобы цикл остановился, необходимо, чтобы a2 > n/2, и цикл заведомо останавливается, если a3 > n.
Следовательно, все зависит от положения n по отношению к степеням двойки. Существует такое целое n, что
4q < n < 4q+1.
Возможны два случая. Во-первых, может выполняться неравенство
4q = 22q < n < 22q+1,
и тогда для k = q число a2 = 22q > n/2 может быть значением остановки, но в этом нет уверенности. С другой стороны, если
22q+1 < n < 22q+2,
то единственное значение a, удовлетворяющее условию a2 > n/2, есть a = 2q+1, и для этого значения имеем a2 > n, что гарантирует остановку. Поскольку r = a − b, то а = r + b > r и, следовательно, a2 > n.
Во втором случае
r = 2a − b и b < а, откуда а < 2a − b = r.
Таким образом, все три распознаваемые программой случая являются единственными возможными исходами программы, и каждый из них может произойти.
Таким образом, перед нами — очень забавный алгоритм, который дает значение квадратного корня, и который определяет случай, когда n не является корнем, но в этом случае не дает никакой дополнительной информации.
Программа заведомо останавливается при а = 2q+1, так что число шагов цикла не больше q − 1 (начиная с 4), причем q — логарифм квадратного корня из n по основанию 2. Таким образом, получилась программа порядка In n, что дает ту же сложность, что и обычный алгоритм, действующий кусками по две цифры. Но для этого последнего алгоритма нужен еще первый цикл, чтобы найти порядок величины n.
Головоломка 19.
Соотношение f(a, b) = f(b, a) следует из самой инициализации p и q:
p := max (a, b); q := min (a, b).
Эти две функции симметричны по a и b, и поэтому точно так же симметрична f. При анализе программы мы ограничены действиями, происходящими внутри цикла. Величины r и s являются вспомогательными переменными, которые не оставляют никакой проблемы. Трудность вызывают преобразования, проделываемые над p и q. Чтобы ясно увидеть эту трудность, осуществим введение новых переменных без разрушения старых. Перепишем наш цикл:
ПОКА q ≥ eps ВЫПОЛНЯТЬ
r := (q/p)2; s := r/(r + 4)
p' := (2 * s + 1) * p; q' := s * q
p := p'; q := q'
ВЕРНУТЬСЯ
Рассмотрим действия этой программы, производимые над данными a, b с одной стороны и над ac, bc с другой.