Табл. 4.3. Тестовые данные полинома Р{х)

Рис. 4.5. График функции извлечения квадратного корня

4.5. квадратный корень

Иррациональная функция извлечения квадратного

корня у = -\f X является обратной по отношению к функции возведения в квадрат у = х и определена для всех неотрицательных действительных чисел х. График функции представляет собой монотонно возрастающую кривую, расположенную вдоль оси абсцисс (рис. 4.5).

Известны различные методы вычисления квадратного корня, основанные на многочленных и рациональных приближениях, разложениях в биномиальный ряд и т. п. [45, 48, 70]. Чаще всего для вычислений используется итерационная формула Герона (частный случай формулы Ньютона):

,+ ,=0,5(у,+х/у,). (4-9)

где / = 0,1, yo~\f х - начальное приближение, значение которого выбирается по условиям несложности вычисления (константа или линейная функция) и макси-

мальной близости к искомому значению корня, что позволяет уменьшить число итераций. Обычно это приближение выбирается на основе эмпирической формулы, зависящей от диапазона изменения аргумента. Так, например, при 0,5<х<1 наилучшим приближением считается уо 0,5903x4-0,4173 [48]. В простейшем случае в качестве значения уо можно использовать непосредственно значение X, т. е. уо = х. Итерационный процесс вычисления корня заканчивается, когда значения двух соседних приближений yi и совпадают с требуемой точностью. Пусть, например, необходимо вычислить с четырьмя значащими цифрами = д/28,34 я:; 5,324. Примем уо = Ь. Тогда у1 = 0,5(5 + 28,34/5) 5,33, у2 = 0,5(5,33 -f

-Ь 28,34/5,33) « 5,324, уз = 0,5(5,324 + 28,34/5,324)« « 5,324. Так как t/2 » t/з, то процесс закончен. Сходимость итерационного процесса хорошая, и в каждом шаге число верных цифр примерно удваивается.

Рассмотренный метод реализован в программе вычисления квадратного корня ККОР:

1980 00В8 12С0 1000 19Е0

1980 AF

1981 F5

1982 Е5

1983 С5

1984 11D519 1987 СПБВОО 198А 1111219

ORG 1980Н ПМЗ SET 0В8Н ДДПЗЗ SET 12С0Н СЯПЗЗ SET 1000Н СРПЗЗ SET 19Е0Н

ККОР:

гПОДПРОГРАММА ВЫЧИСЛЕНИЯ КВАДРАТНОГО КОРНЯ У=Х»»(1/2). гВХОДНЫЕ ПАРАМЕТРЫ!(H-L)-АДРЕС АРГУМЕНТА ХгПРЕЯСТАВЛЕН-гНОГО В ФОРМЕ ТРЕХВАЙТНОГО ДВОИЧНОГО В ПРЯМОМ КОДЕ ЧИСЛА гс ПЛАВАЮЩЕЙ ЗАПЯТОЙ,(BfС)-МАСКА ТОЧНОСТИ,ОПРЕДЕЛЯЮЩАЯ гТОЧНОСТЬ ВЫЧИСЛЕНИЯ ФУНКЦИИ у (СОДЕРЖИТ НУЛИ в МЛАДШИХ гНЕЗНАЧАШИХ И ЕДИНИЦЫ В СТАРШИХ ЗНАЧАЩИХ разрядах).РЕ-гЗУЛЬТАТ ФОРМИРУЕТСЯ в ОБЛАСТИ ПАМЯТИ -БУФЕР-.выходные {ПАРАМЕТРЫ:(А)-КОЛИЧЕСТВО ВЫПОЛНЕННЫХ ИТЕРАЦИИ В ПРОЦЕС-гСЕ ВЫЧИСЛЕНИЯ УгСУ=1-ПРИЗНАК ПЕРЕПОЛНЕНИЯ ИЛИ АНТИПЕРЕ-гПОЛНЕНйЯ ПОРЯДКА РЕЗУЛЬТАТА.ИСПОЛЬЗУЮТСЯ ВСЕ РЕГИСТРЫг гСОХРАНЯЮТСЯ (HfD,(ВгС).глубина СТЕКА-Х.ИСПОЛЬЗУЮТСЯ г ПОДПРОГРАММЫ:«ПМЗ» f «ДДПЗЗ» f »К0МЗ» f•ЯЯФ17»,«ПМАг», г»СЯПЗЗ»,»0БМЗ«,»ЯМАН2»,»ПМАН2»г«НМАН2»,«Я0ПЯ«,*Д0ПН». :ОЦЕНКА:ЯЛИНА-Вг байт (+424 БАЙТ ПОДПРОГРАМН),ВРЕМЯ-НЕ гБОЛЕЕ (219+6350»К> тактов,ГДЕ К-КОЛИЧЕСТВО ИТЕРАЦИЙ.

г»»»»»»*»*»*»»»»»»»»»»*»»»»»»»»»»**»»»»»»»»»»*»»»»«»«»««

XRA PUSH PUSH PUSH

гПЕРЕНЕЩЕНИЕ АРГУНЕНТА LXI Г,БУФД CALL ПНЗ LXI Р,БУФЕР

г(А)-СЧЕТЧИК ИТЕРАЧИЙ=0 гСОХРАНЕНИЕ СЧЕТЧИКА гСОХРАНЕНИЕ АДРЕСА X гСОХРАНЕНИЕ НАСКИ X В "БУФЕР" И "БУФЯ"

гПЕРЕНЕЩЕНИЕ В "БУФЯ*

198D СПВЗОО

1990 ЕВ

1991 35

1992 01D519

1995 cncoia

1998 IIACD19

199В 11D819 199Е CDEeOO 19А1 ЕВ

19А2 CDOOlO 19А5 DACD19 19А8 60 19А9 69 19АА 35

19АВ ЕВ 19АС 01 19AD 21D219 19В0 CIIE019 19ВЗ САСЕ19

1986 ЕВ

1987 11D219 19ВА СПВВОО

CALL ПМЗ ;ПЕРЕМЕЩЕНИЕ В "БУФЕР"

$ВЫЧИСЛЕНИЕ НАЧАЛЬНОГО ПРИБЛИЖЕНИЯ У(0)=Х/2 В "БУФЕР" XCHG S(H.L)-АДРЕС "ВУФЕР"

tCR Н ;УНЕНЫ11ЕНИЕ П0РЯДКА:Х/2

;ДЕЛЕНИЕ АРГУМЕНТА X НА ТЕКУЩЕЕ ПРИБЛИЖЕНИЕ !Х/У(1)

ЧИКЛ: LXI В.БУФД

CALL ДДПЗЗ jЧАСТНОЕ В "БУФД" JC ЛЕР1 $ЕСЛИ ОШИБКА ПОРЯДКА

;ПЕРЕМЕЩЕНИЕ ТЕКУЧЕГО ПРИБЛИЖЕНИЯ ДЛЯ СЛОЖЕНИЯ Б "БУФ" LXI BfEy*

CALL ПМЗ гПЕРЕМЕШЕНИЕ ИЗ "БУФЕР" В "БУФ" XCHG 5(H.L)-АДРЕС "БУФ"

гВЫЧИСЛЕНИЕ ПРИБЛИЖЕНИЯ:У(1+1)=0.5»(У(1)+Х/У(1)>

CALL СДПЗЗ

JC ПЕР1

на» НгВ

HOW L.C

DCR Н ;СРАВНЕНИЕ ТЕКУЩЕГО ПРИБЛИЖЕНИЯ У(1) ХСНВ

POP В

LXI Н.БУФЕР

CALL СРПЗЗ

JZ ПЕР2

гУ(1+1) В "БУФД" ;ЕСЛИ ОШИБКА ПОРЯДКА

;(H.L)-АДРЕС "БУФД" $ДЕДЕНИЕ YlI*l)/2

С ОЧЕРЕДНЫМ ;(D.E)-АДРЕС "БУФД" гВОССТАНОВЛЕНИЕ МАСКИ

гВНЧИСЛЕНИЕ ПРИЗНАКОВ CY.Z

гЕСЛИ у(1+1)=у(1)

гПЕРЕМЕЩЕНИЕ ПРИБЛИЖЕНИЯ У(1+1) НА МЕСТО У«1) XCHG s(H.L)-AHPEC У(1+1)

LXI D.БУФЕР CALL ПМЗ гПЕРЕМЕЩЕНЙЕ АРГУМЕНТА XCHG

X В "БУФН" г(В.Е)-АДРЕС "БУФД"

Эта программа носит исследовательский характер, поскольку, во-первых, область значений аргумента неограниченна и в качестве начального приближения выбрано