3.9.1 Изчисляване на корен втори

Calculation of Root Second

Функцията корен втори

се отнася към ирационалните и е определена като реална само за положителни стойности на аргумента. Представеният по-долу алгоритъм, е разработен за числа с ляво фиксирана запетая, представени в знакопроменлива двоична бройна система без излишък {-1, +1}, т.е. междинните стойности на функцията Z ще се изобразяват чрез тази бройна система. Алгоритъмът произтича от естественото последователно уточняване на стойността на функцията чрез пробите и грешките.

И така, приближеното значение на корена, изчислено с точност до i-тия разряд след запетаята, се изобразява така:

където цифрите с позиционни номера от (-1) до (-i) са (+1) или (-1). В разряда с номер нула (0) (цялата част на числото) в горния запис стои цифрата (+1), тъй като става дума за положителни стойности на функцията.

Текущото приближение, определено с (3.9.1.1) трябва да удовлетворява условието

т.е. прибавянето или изваждането на единица към приближението в последно определения му i-ти разряд, определя границите на интервала, в който ще се доуточнява стойността на функцията. Ясно е, че след като броят на разрядите, с които е изобразено приближението, нараства, то този интервал ще се стеснява. След повдигането в степен, от (3.9.1.2) се получава следното:

което може да се изрази така:

След интерпретиране на горния израз, се въвеждат означенията

Използвайки тези означения, (3.9.1.3) приема вида:

Приема се, че в края на i-тата итерация са известни приближението Z_i и величините B_i и C_i, като за тях са възможни два случая:

1. Ако цифрата е единица

то (i+1)-вото приближение на функцията има вида:

а величините C_i+1 и B_i+1 ще имат вида:

Новите стойности на тези величини трябва да удовлетворяват условието (3.9.1.5), според което, след заместване на новите стойности може да се установи, че:

2. Ако цифрата е минус единица

то (i+1)-вото приближение на функцията ще има вида:

а величините C_i+1 и B_i+1 ще имат вида:

Чрез условието (3.9.1.5) по аналогичен начин може да се установи, че:

Чрез частните изводи (3.9.1.6) и (3.9.1.7) се стига до общия извод за определяне на поредната цифра на функцията:

Аналогично, обобщавайки частните резултати за величините С и В, се получава техният общ вид:

Със завършване на (i+1)-вата итерация започва (i+2)-рата, при което, условието от вида (3.9.1.5), е автоматически изпълнено. Ето защо, за да е изпълнено това условие на всяка стъпка, е достатъчно то да е изпълнено в началния момент.

В началния момент (i=0) е известно (вижте (3.9.1.1)), че z₀=+1 и тогава

Замествайки тези резултати в (3.9.1.5), лесно може да се установи следното:

0 ≤ X ≤ 4 ,

което е отнапред изпълнено, тъй като аргументът X е положително число с ляво фиксирана запетая. При това се получава така, че B₀ е отрицателно число с (2.n+1) разряди, което следва да е записано в допълнителен код:

Така допълнителният код е съставен от (n+1) старши единици (знаков разряд плюс n цифри) и цифрите на кода на аргумента X в младшите n разряда.

След завършване на n-тата итерация, C_n се превръща в C_n=Z_n, т.е. в закръглената стойност на квадратния корен.

Алгоритъмът завършва според (3.9.1.9) с изместване на един разряд наляво и запис на единица в младшия разряд. За изобразяване на резултата в двоична бройна система {0,1} всички цифри (-1) в резултата се заменят на нули, а всички (+1) - с единици.

Апаратната реализация на така изложения алгоритъм за коренуване лесно може да се осъществи в логическата структура на едно устройство за деление, след подходяща модификация. Тук на фигура 3.9.1.1 е показана такава структура, а изпълнението на операцията както за числа с ляво фиксирана запетая, така и с дясно фиксирана запетая, е демонстрирано с подходящи примери в книга[2].

Не представлява проблем изпълнението на това изчисление и върху числа представени във форма с плаваща запетая.

Фиг. 3.9.1.1. Логическа структура на устройство за коренуване

Показаната логическа структура съдържа (n+2)-разряден суматор

СМ[ (-1), … (-(n+2)) ] ,

n-разрядните регистри:

регистър на резултата Рг.Z,

регистър на аргумента Рг.Х

и регистър на приближението Рг.А, който е допълнен отдясно с два допълнителни разряда, както и други помощни възли.

Представеното устройство работи по следния алгоритъм: след изчисляване на поредното приближение B_i на изхода на суматора СМ, като поредна цифра z_(-i) на резултата, в Рг.Z се приема логическата инверсия на най-старшия пренос p_-1. Едновременно с това се извършва изместване наляво на един разряд на съдържанието на Рг.Z. В същото време, при условие, че е имало пренос (p_-1=1), в Рг.А по управляващия сигнал УС6, се записва новото приближение. Ако не е имало пренос (p_-1=0), съдържанието на Рг.А не се променя.

Следващата итерация започва с едновременно изместване на 2 разряда наляво на конкатенираното съдържание на Рг.А и Рг.Х, при което суматорът извършва изчислението (3.9.1.10). В регистър Рг.Z се съдържа допълнителният код на умаляемото. При това, текущото приближение на резултата Z, е постоянно допълнено отдясно с две единици. Следва запис на цифрата z _-(i+1) и запис на полученото приближение в Рг.А, ако е имало пренос от най-левия разряд.

Записът в Рг.А по сигнала УС6 е условен, тъй като по същество зависимостта (3.9.1.10) се реализира по метода "без възстановяване на остатъка".

Описаните микрооперации се повтарят циклически n пъти, колкото са разрядите на аргумента, т.е. докато се получи сигналът (признакът) EQ=1 за нулиране на брояча на циклите Бр.Ц.

В изходно положение логическите възли в структурата на устройството имат следното начално съдържание:

(Бр.Ц) = n ;

(Рг.Z) = 111 ... 111 ;

(Рг.А) = 0 ;

(Рг.Х) = Х .

Изложеният алгоритъм за функциониране на представеното устройство е илюстриран с множество числени примери в книга [2].

Следващият раздел е:

Глава 4. Логическа структура на запомнящи устройства ( Logical structure of storage devices )