1.9. Добування квадратного кореня

Частота появи в програмах - 1-1,5%. Зазвичай реалізується програмним шляхом, але іноді і апаратним.

Y _{n +1} = 1/2 (Y _n + X / Y _n)       Y _{n +1}   - Y _n   

X = 2 Y ₀ = 1 Y ₁ = 1.5 Y ₂ = ...

Вище розглянутий алгоритм переробимо так, щоб добування квадратного кореня можна було виконувати подібно поділу з тією відмінністю, що "дільник" - змінне число.

Нехай Y _i-1 = 0.Y _-1 Y _-2 ... Y _{- (i-1).} М и знайшли (i -1) наближення.

Знайдемо q _i = X - (Y _{i -1} + 2 ^{- i) 2} = q ^{i -1} - 2 ^{- (i -1)} [Y _{i -1} + 2 ^{- (i +1)]}

q ₀ = X q ₁ = q ₀ - 2 ⁰ 0.01

Для отримання залишку q _i треба з попереднього залишку відняти зрушені на (i -1) розряд вправо знайдене наближення до кореня, в якому в двох молодших розрядах додано комбінацію (01). Якщо q _i > 0, i-я цифра чергового наближення повинна бути обрана рівній одиниці. Якщо q _i <0, то чергова цифра дорівнює нулю. У разі q _i <0 треба відновити попередній додатній залишок аналогічно алгоритму розподілу з відновленням залишків.

Як q ₀ беремо підкорінний вираз Х, з якого має бути вирахувано 0.01. Якщо скористатися алгоритмом розподілу без відновлення залишків з використанням ДК, то можна і при реалізації добування кореня уникнути процедури відновлення залишків.

Якщо при цьому вийде від’ємний залишок, то ми додамо до нього число, в якому в двох молодших розрядах записано 11. Наведене вище прищепило нагадує процес ділення по 2 варіанту. Можна організувати процес і по 1 варіанту. При цьому замість зсуву дільника вправо будемо зсувати залишки вліво.