ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ ................................................ 3
Глава 1. МЕТОДЫ ВЫЧИСЛЕНИЯ ЭЛЕМЕНТАРНЫХ ФУНКЦИЙ.......... 6
1.1.	Обзор методов........................ . .	—
1.2.	Основы метода «цифра за цифрой»............... 8
1.3.	Анализ сходимости вычислительных алгоритмов .	12
1.4.	Рекуррентные соотношения метода «цифра за цифрой»	.............................18
1.5.	Применение метода «цифра за цифрой* для преобразования систем счисления 7........................31
Глава 2. АНАЛИЗ ПОГРЕШНОСТЕЙ ВЫЧИСЛЕНИЯ ЭЛЕМЕНТАРНЫХ ФУНКЦИЙ;. . 3^
2.1.	Вводные замечания .	............'.	—
2.2.	Погрешности выполнения операции «поворот» 36
'	2.3 Погрешности выполнения операции «вектор» .	42
2.4.	Анализ погрешностей способа Меджита ....	51
2.5.	Погрешности вычисления элементарных функций с помощью полиномиальной аппроксимации ...	58
Глава 3. ВОПРОСЫ СТРУКТУРНОЙ РЕАЛИЗАЦИИ ВЫЧИСЛИТЕЛЬНЫХ АЛГО-
РИТМОВ . . . :	.........	... 67
3.1. Реализация метода «цифра за цифрой*............—
3.2. Реализация метода полиномиальной аппроксимации 76
Глава 4. НЕКОТОРЫЕ ВОРЬОСЫ ПРОЕКТИРОВАНИЯ ЦВМ С АППАРАТУРНОЙ РЕАЛИЗАЦИЕЙ	ЭЛЕМЕНТАРНЫХ	ФУНКЦИЙ .......... 82
4.1.	Выбор основных параметров......................—
4.2. Области применения аппаратурной реализации элементарных	функций..........................87
УКАЗАТЕЛЬ ЛИТЕРАТУРЫ ................................... 92
Рекомендовано к изданию Редакционно-издательским советом Ленинградского ордена Ленина электротехнического института имени В. И. Ульянова (Ленина)
УДК 681.3.001:518.5
Байков В. Д., Смолов В. Б. Аппаратурная реализация элементарных функций в ЦВМ. Л., Изд-во Ленингр. ун-,та, 1975, 96 с.	'	’ - .-ssmi
*
Рассматривается один из вопросов, относящихся к проблеме оптимизации соотношения программных и аппаратурных средств системы математического обеспечения ЦВМ,— анализ методов вычисления элементарных функций, ориентированных на аппаратурную реализацию. Основное внимание уделено методу «цифра за цифрой» и методу аппроксимации элементарных функций полиномами наилучцтего приближения. Исследуются все виды погрешностей вычислительных алгоритмов. Намечается подход к выбору параметров ЦВМ с аппаратурной реализацией элементарных функций.
Книга рассчитана на специалистов по математическому обеспечению и структурному проектированию ЦВМ, ЭКВМ, прикладной математике и автоматизированны!,! системам управления.
Ил.— 35, табл.— 8, библиогр.— 81 назв.
Байков Владимир Дмитриевич.
Смолов Владимир Борисович
Аппаратурная реализация элементарных функций в ЦВМ
Редактор Л. К. Бетехтина Техн, редактор А.-В. Борщева Корректоры С- К. Школьникова, Э. А. Горелик
М-31664. Сдано в набор 10/1 1975 г. Подписано к печати 12/VI 1975 г.
Формат бумаги 60X90’1в. Бумага типографская № 3.
Печ. л. 6. Уч.-изд. л. 5,71. Бум. л. 3. Тираж 10 000 экз. Заказ 124. Цена 57 коп.
Издательство ЛГУ нм. А. А. Жданова 199164. Ленинград, Университетская наб., 7/9.
Сортавальская книжная типография Управления по делам издательств, полиграфии и книжной торговли Совета Министров Карельской АССР
Сортавала, Карельская, 42.
30502—088
Б 076(02)—75 149—75
(С) Издательство Ленинградского университета, 1975
ВВЕДЕНИЕ
Постоянно растущая сложность задач, решаемых цифровыми вычислительными машинами, повышение требований к точности, времени и достоверности результатов решения, простоте программирования и удобству обслуживания, а также часто накладываемые ограничения на габаритные размеры, вес и стоимость вычислительных машин тесным образом связаны с проблемой повышения эффективности работы современных ЦВМ.
Достижение максимальной эффективности, по словам академика В. М. Глушкова [12], в значительной степени определяется оптимальным соотношением программных и аппаратурных средств системы математического обеспечения (МО).
 Непрерывное совершенствование технологии производства электронных схем привело, в последнее время к резкой диспропорции между стоимостью программных (software) и аппаратурных (hardware) средств системы МО. Если стоимость электронных компонентов постоянно уменьшаемся, то затраты на программную часть неуклонно возрастают. Аппаратурная реа лизация средств МО по сравнению с программной имеет также ряд преимуществ в части быстродействия, надежности и простоты программирования [12, 39].
Процесс переложения части функций МО с программных средств на аппаратурные начался еще при производстве машин первого поколения. Например, операция «деление», выполнявшаяся в ранних образцах ЦВМ по специальным подпрограммам, по мере совершенствования технологии стала выполняться аппаратурно.
Однако в вычислительных машинах первых двух поколений основные функции МО возлагались на программные средства. В настоящее время в некоторых работах [25, 39] высказывается мнение, что к 1978 г. произойдет замена большей части программных 'средств системы МО аппаратурными средствами.
По мнению ряда авторов [18, 47, 60], при существующей технологической базе на аппаратурные средства могут быть возложены следующие функцйи: вычисление элементарных функций, двоично-десятичные и десятично-двоичные преобразо
вания, преобразования координат, операции просмотра таблиц, операции масштабирования и др.
Однако аппаратурную реализацию нельзя понимать как простое механическое перенесение функций МО с программных средств на аппаратурные. Специфика аппаратурной реализации заставляет использовать иные критерии при выборе вычислительных алгоритмов по сравнению с программной реализацией.
В первую очередь необходимо отметить тот факт, что если программная реализация связывается с выполнением программы (либо подпрограммы) и состоит в выполнении отдельных команд, то аппаратурная реализация подразумевает выполнение микропрограммы и состоит из микрокоманд (микроприказов). В связи с этим существенно отличается число обращений к оперативному запоминающему устройству (ОЗУ).
При программной реализации для выполнения одной арифметической операции необходимо произвести несколько обращений к ОЗУ (выборка команды, выборка операндов, запись результата). Поскольку вычисление, например, одной элемен тарной функции требует нескольких десятков арифметических операций, то соответственно в десятки раз увеличится и число обращений к ОЗУ, ц это в конечном счете определяет время вычислений.
Число обращений к ОЗУ при аппаратурной реализации любой элементарной функции не превосходит количества обращений, требуемого для выполнения одной арифметической операции.
Для программной реализации все арифметические действия: сложение, вычитание, умножение, деление и сдвиг— являются командами, и выполнение их связано с неоднократным обращением к ОЗУ.
При аппаратурной реализации сложение, вычитание и сдвиг — это микрооперации, а умножение и деление — команды (микропрограммы), и, следовательно, время их реализации существенно отличается.
При программной реализации в 'большинстве универсальных ЦВМ все константы (коэффициенты), необходимые для проведения вычислений, хранятся в ОЗУ При аппаратурной реализации константы записываются в одностороннее постоянное запоминающее устройство (ПЗУ), обладающее существенно большим быстродействием, чем ОЗУ.
Все вышесказанное определяет специфику требований к вычислительным алгоритмам, ориентированным на аппаратурную реализацию. Алгоритмы должны анализироваться по составу операций, числу промежуточных результатов — связности алгоритмов и тоебуемому числу констант, определяющему объем ПЗУ.
Кроме того, общими вопросами анализа численных методов
независимо от способа реализации являются анализ сходимости, анализ то гности, оценка времени реализации, определение требуемых аппаратурных затрат.
В настоящее время методы вычисления элементарных функций в основном рассматриваются применительно к программной реализации. В то же время аспектам аппаратурной реализации уделяется недостаточно внимания.
В данной работе последовательно рассматриваются вопросы теории и аппаратурной реализации алгоритмов вычисления элементарных функций, использующих полиномиальную аппроксимацию, й алгоритмов, основанных на разновидности итерационного метода «цифра за цифрой», имеющего большие возможности при создании современных мини ЦВМ, ЭКВМ,. вычислительно-управляющих и информационно-вычислительных комплексов.
ГЛАВА 1
МЕТОДЫ ВЫЧИСЛЕНИЯ ЭЛЕМЕНТАРНЫХ ФУНКЦИЙ
1.1.	ОБЗОР МЕТОДОВ
Проблема оптимизации соотношения программных и аппаратурных средств системы МО включает в себя комплекс различных вопросов. В данной работе рассматривается один из частных вопросов, относящихся к этой проблеме,— анализ методов вычисления элементарных функций при их аппаратурной реализации.
В последнее время этому вопросу уделяется значительное внимание как в теоретических исследованиях, так и в отношении технической реализации [8, 10, 11, 15, 17, 21, 23, 24, 26, 27, 28, 29, 38, 40, 44, 45, 49, 52, 58, 63, 65, 70, 71, 80].
Существует большое количество разнообразных методов вычисления элементарных функций Из них в цифровой вычислительной технике нашли применение:
1)	разложение в ряд Тейлора;
2)	аппроксимация с помощью различного вида полиномов наилучшего приближения;
3)	цепные дроби;
4)	рациональные приближения;
5)	табличные методы;
6)	итерационные методы.
Охарактеризуем кратко каждый из этих методов. Степенные полиномы (отрезок ряда Тейлора, полином Чебышева и т. д.) вычисляются в ЦВМ чаще всего по схеме Горнера. Время, необходимое для вычисления полинома при разложении функции произвольного вида, приблизительно равно 4гол = «(£умн-Нсл), где т — степень полинома; /уМн— время выполнения команды умножения; tcn — время выполнения команды сложения.
Преимуществом разложения в ряд Тейлора является возможность вычисления коэффициентов членов ряда непосредственно в процессе работы. В связи с этим отсутствует необходимость запоминания их в памяти машины, как это требуется при полиномиальной аппроксимации по Чебышеву. Однако такой способ определения коэффициентов требует значительного времени вычисления. Недостатком использования ряда Тейлора является также его медленная сходимость при вычислении функций Inx, arctgx, arcsinx, что приводит к большому времени вычисления и накоплению значительной инструментальной погрешности. Кроме того, при этом способе методическая погрешность монотонно возрастает с увеличением аргумента. Для
уменьшения влияния этого вида погрешности аргумент предварительно сводят в более узкую область с помощью соответствующих преобразований.
Методическая погрешность полиномиальной аппроксимации знакодеременна и равномерно распределена по промежутку изменения аргумента. К недостаткам этого метода следует отнести большую загрузку ПЗУ, в которое должны быть записаны коэффициенты всех аппроксимирующих полиномов.
Преимуществом цепных дробей является малый требуемый объем ПЗУ, принципиально более широкая область сходимости, чем для ряда Тейлора, и универсальность применения программы (микропрограммы) вычисления цепной дроби для различных функций [15]. Однако практически получается, что при увеличении аргумента функции резко возрастает необходимое число звеньев дроби, что заставляет приводить аргументы к интервалу, не более широкому, чем при разложении в ряд Тейлора. Недостатком метода является, во-первых, необходимость наличия в системе команд машины операции деления, во-вторых, большое время вычисления, которое даже для самого быстрого способа составляет [15]	,
Д. др ==: ^(^умн "4~ ^дел ^сл)>
где v — число звеньев дроби, зависящее от вида функции и требуемой точности; ta. дР~ время реализации цепных дробей.
При использовании рациональных приближений элементарные функции представляются в виде отношения двух полиномов с числом членов в каждом намного меньшим, чем для соответствующих разложений в ряд Тейлора. Однако при данном методе все коэффициенты полиномов должны быть предварительно занесены в память. Время вычисления элементарной функции при использовании рациональных приближений состоит из суммарного времени вычисления двух полиномов и выполнения операции деления.
Различные табличные методы основаны большей частью на методах криволинейной или кусочно-линейной аппроксимации [26, 28, 44]. Достоинством их является малое требуемое число арифметических операций, необходимое для вычисления функции. Однако практическое их использование ограничивается требованием большого объема запоминающего устройства. При табличном методе для вычисления только одной функции требуется в среднем 2п/2—2п значений, что составляет для ЦВМ с 24-разрядной сеткой, не менее 4096 ячеек памяти. Этот фактор ограничивает практическое применение рассматриваемого метода вычислительными машинами с длиной слова, не превышающей 12—15 двоичных разрядов.
Развитием табличных методов являются таблично-алгоритмические методы [29, 38, 45, 65], позволяющие значительно сократить объем таблиц за счет некоторого увеличения времени
вычислений при использовании интерполяции разлучных порядков. Однако эти способы еще недостаточно исследованы.
Сущность итерационных методов состоит в построении последовательности yi+i — сходящейся к функции у(х). Эффективность применения данных методов зависит, во-первых, от скорости сходимости (необходимого числа итерации, удовлетворяющего заданной точности), и во-вторых, от набора операций, выполняющихся в каждом шаге. Необходимость в ряде случаев выполнения операций деления и умножения в процессе выполнения итераций [24] существенно увеличивает время вычисления. Кроме того, итерационные уравнения до настоящего времени были известны лишь для некоторых элементарных функций [24].	.
Из всех рассмотренных выше методов при реализации на ЦВМ наиболее* часто используется метод полиномиальной аппроксимации.
Однако в последнее время внимание разработчиков вычислительных машин стал привлекать один итерационный метод [10, 21, 27, 32, 40, 50, 53, 67, 78], который может быть отнесен к методам «цифра за цифрой». Надо отметить, что вообще к методам «цифра з а цифрой» относят любой процесс вычислений, в результате выполнения которого на каждом циклически повторяющемся шаге последовательно получают одну надежную цифру результата, независимо от того, какие операции при этом совершаются. С этой точки зрения алгоритмы вычисления элементарных функций, рассматриваемые в данной раооте, можно отнести лишь к группе методов «цифра за цифрой». Однако поскольку в зарубежной литературе в настоящее время этот термин (digit by digit) наиболее часто применяется именно по отношению к указанным алгоритмам [52, 65, 69, 81], а в отечественных публикациях соответствующий термин пока еще не установился, будем использовать в дальнейшем для данного метода непосредственный перевод английского названия.
В следующих разделах рассматриваются теоретические вопросы метода «цифра за цифрой».	!
1.2.	ОСНОВЫ МЕТОДА „ЦИФРА ЗА ЦИФРОЙ1'
Вычисление любой элементарной функции по методу «цифра за цифрой» сводится к выполнению двух этапов.
На первом этапе аргументы элементарных функций, заданные «-разрядными кодами в позиционной системе счисления: с основанием а я являющиеся правильными дробями, т. е. числами	представляются либо сходящимся произве-
дением, содержащим в общем случае п комплексных членов вида (1—/^a-i), либо суммой п слагаемых одного из следующих видов: In^l-p^a-’), £»arctga-i, ^Arth-’.
Искомым на данном этапе является набор операторов для которых могут быть выбраны два рода значений: 0 и 1 или — 1 и 4-1. В первом случае говорят об итерационном процессе со знакопостоянными шагами, во втором — со знакопеременными шагами
На втором этапе на основании найденною в предыдущем этапе набора значений операторов определяется величина вычисляемой элементарной функции. Это выполняется либо путем суммирования слагаемых одного’' йз видов: giarctga-i, gjArtha-’, причем i-e слагаемое соответствует i-му члену произведения первого этапа, либо с помощью вычисления произведения действительных (1—gid-i) или комплексных (1—чисел, в котором 1-й’член произведения соответствует i-му слагаемому, используемому на первом этапе.
Каждый этап вычисления выполняется за п шагов и представляет собой итерационный процесс, состоящий в построении, последовательности: Ui—f(Ui-i). Обозначив  разность между двумя соседними членами последовательности 6i = «i — «z-i, назовем данную величину шагом итерации. Каждая итерация первого этапа состоит в определении значения оператора на основании знака бг. На каждой итерации второго этапа определяется очередной член последовательности сходящейся к вычисляемой элементарной функции.
Для проведения двух указанных этапов необходимо выполнение только двух типов операций — алгебраического сложения и сдвига.
Перейдем к подробному рассмотрению каждого из этапов вычисления типовых элементарных функций по методу «цифра за цифрой».
Этап [
Логарифмическая и экспоненциальная функции. Пусть аргументы функций In я и ехря заданы n-разрядными числами в позиционной системе счисления с основанием а. Тогда выполнение этапа I состоит в представлении аргумента функции 1пя в виде 1
Х ~ п" л -k Е
а функции ехря
* =	.	(1.2)
«
В случае итераций со знакопеременными шагами знак опера-топа gj при вычислении функции In я выбирается по условию
sign =— sign [а: 1Ц—\ (1 НИ’* — 1],	(1.3)
а для Функции exp х знак оператора определяется по соотношению
sign = sign [х — Я ft In (1 + а-*)].
Для итераций со знакопостоянными шагами значение оператора для будет:
для функции 1пх	,
Bz=—-sign [%П'->0(1+^а^)М1 +^-1],	(1-4)
для функции ехрх
Ez = sign[x — J^^SfelnU +a-fc) — ?Jn(l +Л-г)1. (1-5) причем знаку «минус» соответствует значение £г = 0.
В дальнейшем, если это особо не оговаривается, речь будет идти об итерациях со знакопеременными шагами.
Для десятичных и двоичных логарифмов и для вычисления значения показательной функции проводятся аналогичные преобразования с заменой натуральных логарифмов в соответствующих выражениях на десятичные или двоичные.
Операция деления и функция Ух. При выполнении первого этапа делитель в выражении z=yfx должен быть представлен как -
Знак оператора определяется по соотношению (1.3).
Для вычисления функции Ух запишем тождество [49]:
Ух = х/Ух . Представим подкоренное выражение так:
1
Знак оператора определяется по соотношению
sign £z =— sign [xllj-^l + a~kyk _ 1 ].
Прямые и обратные тригонометрические и гиперболические функции. Для функций arctg.(y/X), arcctg(F/X) и ]/(Х2-|-У2) на первом этапе аргумент представляется в виде произведения комплексных чисел. Для функции arctg(V/X)
x+iY-
(1-7)
где R — произвольное действительное Число.
Для функции arcctg(K/X)
Г+УХ- .-)»•
(1-8)
Для функции ]/ (Х2+ У2) подходит любое из этих преобразований.	»
Отметим, что величина jR на данном этапе не играет роли, поскольку знак оператора & (i^O) в; выражении (1.7) определяется по соотношению
sign Ег= sign { 1т[Н+/Г)П«(1 -/Ъ<х-*)ЧЬ U-9)
Для функции arcctg(y/X) знак оператора g, (i^O) определяется аналогично с заменой в выражении (1.9) ЛД-/У на У+jX. Аргументы могут изменяться в пределах У<0, Х>0. Аргумент функций sin ф и cos ф представляется так:
УФ = 2/=о^1п(1+^/а“/>	<1Л°)
Знак оператора £,• (t^O) определяется по соотношению
sign = sign — arctga-ft], (1.11)
Аргумент может изменяться в пределах —л/2<ф<п/2,
Выражения для преобразования аргументов гиперболических функций аналогичны co-t ответствую щим выражениям для аргументов тригонометрических функций с заменой констант arctg <x-i на константы Arth а'1. Это соответствие легко может быть проиллюстрировано графиком гиперболических функций (рис. 1).
После определения значений всех операторов |г- необходимо перейти к выполнению этапа II. Заметим, что если
Рис. 1
считать набор операторов g, цифрами результата, то этап I фактически представляет собой операцию по преобразованию систем счисления: из исходной с основанием а в промежуточную систему, где вес i-ro разряда определяется одним из возможных способов: In (l±a-i), arctg a-i, Arth a-4.
На этапе II производится вычисление элементарной функции и одновременно выполняется преобразование из промежуточной системы в а-ичную систему счисления, в которой представляется значение функции.
Во всех приведенных выше выражениях, полученных для произвольной системы счисления с основанием а, фигурировав
ла величина qi, которая может принимать значения 9^11,2, ... , а—1).
Для наиболее часто применяемой в ЦВМ двоичной системы счисления величина qi принимает лишь одно возможное значение: <7<=1. Это значительно упрощает все приведенные выражения и, кроме того, облегчает вычисления по ним. Использование двоичной системы счисления в итерационных процессах со знакопеременными шагами имеет простую геометрическую интерпретацию. Умножению на комплексное число вида (1±/2~‘) соответствует вра-
Рис. 2
щение единичного вектора (поворот координат) по часовой или против часовой стрелки на угол, тангенс которого равен 2~1 (рис. 2). Причем, независимо от направления поворота, модуль вектора увеличивается на каждом шаге в +2~2i) раз. Поскольку общее число таких поворотов (шагов) фиксировано, то фиксирована и величина К— ПД& j/(l + 2-2’), называемая коэффициентом деформации вектора.
1.3.	АНАЛИЗ СХОДИМОСТИ ВЫЧИСЛИТЕЛЬНЫХ АЛГОРИТМОВ
Рассмотрим условия сходимости алгоритмов вычисления элементарных функций по методу «цифра за цифрой» для двоичной системы счисления.
Для сходимости алгоритмов достаточно, чтобы выполнялись следующие условия:
1)
2)	11m 8г = 0;
3)
Последнее есть условие исправляемое™ итераций, где — величина i-ro шага итерации, |х|тах — максимальная абсолютная величина аргумента функции, п— число итераций.
Из трех приведенных условий наиболее сложным является анализ выполнения условия исправляемости итерационного процесса при знакопеременных шагах. Проанализируем выполнение этого условия при вычислении функций sin х и cos х.
В соответствии с выражениями (1.10) и (1.11) данное условие будет
arctg 2~zarctg2-ft.	(1-12)
Взяв, первые 'члены разложения в ряд функции arctg х для х=2~г и преобразуя (1.12), получим, что указанное неравенство выполняется при любых i.
Дтя функции arctg х условие исправляемое™ итераций в соответствии с (1.7) запишется в виде системы неравенств:
Im[(l 4-у2-9П«=г+1(1 - /2-*)1 <0, К
Im[(l -72-')П«=4+1(1 +у2-*)] > 0. j 1	'
Преобразуя систему неравенств (1.13), получим агс!ё2-г —arctg2 ^<0, 1 — arctg2~z -f- 2*Lz+1 arctg 2 k > 0. j
Полученная система неравенств сводится к доказанному выше неравенству (1.12) и, следовательно, также удовлетворяется при любых I.
Рассмотрим выполнение условия исправляемости итераций при вычислении функций arcsin х и arccos х. Указанное условие выполняется в случае справедливости системы неравенств:
Im[(l +у2-ЭП«=/+1(1 -у2-*)] - xKt < 0, )	.
Im [(1 -,2-011^(1 +у2-*)]-х^> 0, |	>
где Kz=VTTUo(l+2-2ft).
Вычисление величины Кг на каждом шаге и-умножение х на Кг вызывают существенное удлинение вычислительного процесса.-. Поэтому для упрощения вычислений вместо Ki иногда берут постоянную величину К [9, 40, 71].
Однако при использовании этого способа в случае попадания текущего значения Уг (ординаты вращаемого вектора) в зону хКг<Уг<хК вектор вместо «правильного» поворота сделает «неправильный» поворот в противоположную сторону (рис. 3). В связи с этим при любом i возможно появление «неправильною» итерационного шага (только одного, если х<т]/2/2) и, следовательно, должно выполняться условие
arctg2~z + arctg 2-(‘+й	arctg 2~ft.	(1-16)
Анализ выражения (1.16) показывает, что данное условие в указанном виде не выполняется. Цля его выполнения необходимо использовать «двойные» итерационные шаги. «Двойными» для двоичной системы счисления назовем такие итерационные шаги, при которых общее число итераций увеличивается вдвое, а величины шагов изменяются только для .четных номе
ров итераций. В случае использования «двойных» шагов рассматриваемое неравенство (1.16) заменится неравенством
2arctg2-z <. 2 V" .+1arctg2~ft.
Данное неравенство приводится к неравенству (1.12), справедливость которого была доказана выше.
Проанализируем условие исправляемости итераций для функции ехр х. Поскольку функция ехр х не обладает свойствами четности и нечетности, то в соответствии с выражением (1.2) данное условие будет
1п(1+2-) + 2^+11п(1-2^)<0,| ln(l-2-z) + ^=z+1ln(l+2^)>0. J	>
Анализ показывает, что из системы неравенств (1.17) второе неравенство не выполняется.
При использовании «двойных» итерационных шагов условие исправляемости итераций запишется так:
In (1 - 2~z) + 2 ^=/+I In (1 + 2-^) > 0..	(1.18)
Езяв пепвые члены разложения функции In х в ряд при зна-
чении х— 1—2~г и преобразуя (1.18), получим, что данное неравенство справедливо.
При анализе условия сходимости алгоритма вычисления функции In х видим, что если взять логарифм от левой и правой частей (1.1), то придется анализировать неравенств г (1-17), соответствующие функции ехр х. Слёдователь-
'	но, для сходимости алгоритма
• Рис. з вычисления функции In х также необходимо использовать «двойные» шаги.
Предлагаемые в работе [70] способы вычисления функций In х и ехр х с помощью предварительного анализа интервала, в который попадает значение аргумента, и использование «однократных» итерационных шагов ведут к усложнению вычислительных алгоритмов, а главное, к значительным погрешностям, которые .могут возникать на последующих итерациях.
Все сказанное выше относится только к знакопеременным шагам. При использовании знакопостоянных шагов происходит «восстановление» аргумента при выполнении «неправильного» шага, и итерационный процесс продолжается со следующегс шага с новым значением индекса i.
Для прямых и обратных гиперболических функций неравенство
Arth2-z<V" . Arth2~ft
не удовлетворяется. В случае «двойных» итерационных шагов приходим к анализу неравенства
Arth2; < 2 2fe=i+iArth2 ’*•
Используя разложение в ряд функции Arth х и преобразуя данное неравенство, видим, что оно удовлетворяется.
Таким образом, для вычисления функций sh х, ch х, Arth х необходимо использовать «двойные» итерационные шаги.
Остановимся на вычислении функций arcsin(F/R) и arccos(A’//?). Для сходимости итерационного процесса во всем диапазоне изменения аргументов применяются «двойные» шаги. При этом аргументы функции arcsin(F/R) и arccos(X/R) представляются в виде мнимой и действительной частей произведения:
arcsin (K/R): YjR = Im[(1/№)П«=0(1 -уЧг2^)], arccos(X/R): X/R = Re [(1/№)П«=0(1 ~ А2 Н
'где i=0,0,1,1, ... , л, л; №=nLo(l + 2“2i).
Поскольку при «двойных» шагах сумма углов поворота вектора увеличивается в два раза по сравнению с обычными итерациями, то в течение итерационного цикла вектор может перейти из первого квадранта во второй или четвертый. В связи с этим знаковые соотношения должны учитывать номер квадранта с помощью знака соответствующей составляющей:
sign Sz = sign { 1т[/?П'~> (1 — jЧЛ2-»)]— YK2\ X
X sign {Re HU (I-Л* 2 *)]},	(1.19)
signEz — sign (Re [/? П'-* (1 - j 2T*)] - XK2\ X
X sign {1т[/?П‘-> (1 —у ^.2-*)]}.	(1.20)
Аргументы могут изменяться в пределах Ос {|	2/2.
Перейдем 'к рассмотрению второго этапа вычисления элементарных функций
Этап II
Задачей этапа II явйяется определение величины вычисляемой элементарной функции по найденным на этапе I значениям операторов gt-.
Для пол\чения значения функции In х прологарифмируем ©ыражение (1.1)
1пх=-2?=11п(1-Нг2-9- 
Поскольку логарифмы (натуральные, двоичные или десятичные) констант вида (l+gi2-i) вычислены и записаны в память машины, то для реализации функций In х, lg2 х, logic х выполнение этапа II сводится к суммированию констант.
Для вычисления экспоненциальной функции потенцируем равенство (1.2)
ехрх = И«=1(14-^2-‘).	(1.21)
В случае, если в выражении (1.2) были взяты двоичные или .десятичные логарифмы, получим соответственно 2х или 10х. Область допустимых изменений аргумента для функций In х и ехр х составит не менее (0,251,5). Используя известное тождество xy=exp(t/ In х), с помощью функций ехр х и In х можно вычислять показательную функцию при произвольном основании.	,
Этап IIх выполнение операции деления состоит в подстанов-же значения х из (1.6) в выражение z=y/x, тогда
2 = УП«=1(1 +512-').
Для функции
]/х = хПГ=1(1+^2-г).	(1-22)
Рассмотрим этап II вычисления прямых и обратных тригонометрических функций. Прологарифмируем выражение (1.7) и, взяв главное значение логарифма, приравняем мнимые части:
arctg(r/X) = - 2L0 Ezarctg2~z.	(1.23)
Аналогично можно получить выражение для функции arcctg(F/X).
Из выражения (1.7) следует, что величина R есть результат произведения:
/?=(^ + УТ)П«=0(1^УД,2-г	(1.24)
Подставив в выражение (1.7) значение R, приравняем действительные части:
. —------- Re {(X + j Y) П"( 1 — Дг 2~f)}
У^Г2+У2) = - ” >	г-°\	---41.	(1.25)
Гп<1о(1+2-29	’
Аналогичные преобразования можно провести с выражением (1.8). Легко заметить, что при значении Х=1 вычисляются функции вида arctg Y, arcctg Y, У (1-}-У2)
Потенцируем выражение (1.10) и приравняем мнимые части, учитывая коэффициент деформации А=УП^ (1+2~2’):
sinT = 1тЦ1//Ш0(1 + Л5 ')]•	(1-26)
Приравняв действительные части, получим
cos ? - Re [(1/A ) nto(l +J ^2-91	(1-27)
Из выражений (1.19), (1.20), (1.26), и (1.27) следует, что sin <р= Y/R и costj)=X/R. Поскольку из 'выражения (1.11) вытекает, что	arctg 2~г, то
<р =arcsin (Y/R) = L arctg'24
или ср =arccos (%//?) = ^arctg2-z, I — 0, 0, 1, 1, ... , n, n.
При Y=x—2~a, R=x~Y2~a, где a — произвольное Целое положительное число, получим
ср = arcsin [(х — 2~а)/(х -ф- 2_“)1-	(1 -28)
При этом проекция вектора на ось абсцисс равна
V [(х + 2~а)2—(х — 2 й)21 = ]Yx- 2-“/2+1.	(1.29)
Если положить а = 2, то ^х-2-а12+1=}!х. Выражение (1.29) при а=2 приведено в работе [9]. Допустимые пределы изменения аргумента функции фх
0<х<|/Й-ф-2~°.	(1.30)
Для гиперболических функций
Arth (Y/X) =- -XLi егАг№2-г, sh т = Im [(1//Q IIU(1 +/^2-)Ь ch =.Re [(1//Q П?=1(1 +/Л2-%
i = 1, 1, 2, 2, ... , тг, п, ^А=/П?=1(1 -2-2‘).
Область допустимых изменений аргументов для • функции Arth(K/A) — (| YjX\ <1), для функций sh <р и chф—(0<ф<Д,08), для функции Arc.th(X/y) — (| X/Y | > 1).
Величина Rh называется коэффициентом деформации гиперболического вектора.
Обратные гиперболические функции Arsh(F/7?) и Arch(A/R) вычисляются как и обратные тригонометрические функции с той лишь разницей, что вместо констант arctg 2-' используются коистанты Arth 2-i.
Таким образом, эды рассмотрели основные теоретические предпосылки вычисления элементарных математических функций по единообразной схеме применительно к двоичной системе счисления.
На основании вышеизложенного можно указать основные отличия метода «цифра за цифрой» от классических итерационных процедур. Метод «цифра за цифрой» характеризуется следующими особенностями:
величины шагов итерации задаются заранее, зависят только от номера итерации (i) и не зависят от степени приближения к требуемому результату;
используются косвенные методы (проверки на сходимость^ т. е. на каждой итерации определяется не величина разности (ui — Ui-j), а только ее знак;
число итераций непосредственно зависит от числа разрядов в представлении аргументов элементарных функций.
1.4, РЕКУРРЕНТНЫЕ СООТНОШЕНИЯ МЕТОДА „ЦИФРА ЗА ЦИФРОЙ"
Алгоритмы вычисления элементарных функций по методу «цифра за цифрой» могут быть представлены в виде рекуррентных соотношений, содержащих только операции сдвига и алгебраического сложения. Такая форма записи имеет значительные преимущества при машинной реализации. Не вдаваясь пока в подробности структурной организации машины, отметим только, что при этом для проведения вычислений необходимо иметь 3—4 ячейки оперативной памяти (или 3—4 ^реги-стра), устройства анализа и присвоения знака и устройства сдвига на переменное число разрядов.
Рассмотрим рекуррентные соотношения, получаемые из соответствующих выражений, приведенных выше, при записи алгоритмов вычисления элементарных функций по способам Волдера [78, 79] и Меджита [68], названным так по имени авторов, впервые описавших данные алгоритмы.
Спосоо Волдера
Отметим вначале, что умножение на действительное число типа (1±2-<) требует одного ' сдвига вправо на i разрядов и одного алгебраического сложения. Умножёнию на комплексное число типа (1±/2~*) другого комплексного числа соответствует выполнение двух алгебраических сложений и двух сдвигов на i разрядов.
Рассмотрим вычисление прямых и обратных тригонометрических функций.
Функции sin ф, cos ф. Обозначим
е/ = <Р - Sfci arctg2-fc,
+уЧ*2~й)],
xt = Re [х0 П^(1 +/ 2-*)].
Тогда в соответствии с выражениями (1.11), (1.26) и (1.27): этап I e«-ei-^retg2-‘, f	sign = sign 0Z,
T yz+i = yz —Ez2-Zxz, этап II xz+i = xi + 5i2-,yz,
где t = 0, 1, 2.n—1.
Начальные условия: 0o=<p, Уо=О, x0—l/R.
Результаты: t/n=sinq>, xn = cosq).	
Функции arctg (Y/X), arcctg (Y/X), ]/(X2+ Y2). Обозначим yt = Im{(X + JY) n«J0(l - j 2-% x/ = Re{(X + /T)n'-J0(l -ДА2-% е* = 2л=(А arctg 2-ft.
В соответствии с выражениями (1-9), (1.23), (1.24) и (1.25): У/+1 = Уг-^2-(Х> этап I xZ4_i = 2-fyz, sign = sign yz, этап II Gz+j = 6Z -p 5zarctg2~‘.
Начальные условия: Уо—Y, x0—X, 6o=0.
Результаты: xn = /С]/ (X2+ У2), 0n =—arctg(F/X), Qn+n/2— = arcctg (У/Х).
Функции arcsin (Y/R), arccos {X/R). Для этих двух функций используемые обозначения и рекуррентные соотношения те же самые, что и для функции arctg(T/X). Из выражений (1.19) и (1.20) соответственно:
a) sign Ez = sign (yz — Г№) sign xh 6) sign £z =— sign (%z — XK2) sign yz,
где i = 0, 0, 1, 1, ..., n—1, n—1.
Начальные условия: x0—R, yo=0, 0o = O.
Результаты: a) 0n= arcsin (Y/R), 6) 0n = arccos(X/R).
При задании других начальных условий Xo—R/K2, уо = О, 0о=О результат операции не изменится, а рекуррентные соотношения для определения знака будут: sign|,=sign(t/i—У)Х Xsignx;, sign &=—sign (х{—Х) sign yt.
Функция J/х. Рекуррентные соотношения записываются аналогично соотношениям для вычисления функции arcsin (Y/R). В соответствии с выражениями (1.19) и (1.28)
signEz = sign [yz— (х—2~а)К2]signxz. ’
Начальные условия: Xo=x4-2~°, #о=О, 0о=О.
Результат: хп = № рЛх-2~а/2+1.
Можно использовать и другое соотношение
sign Ег = sign [у, — (х — 2-°)] sign xt.
Начальные условия: Хо= (х4-2-о)/К2, Уо=О, 0о=О-
Результат: хп= У^х-2~а12+1.
Перейдем к рассмотрению вопросов получения рекуррентных соотношений для функций In х и ехр х.
Обозначим
' У/ = У1П'-11(1 - ^2-^).
Для функции ехрх в соответствии с выражениями (1.3) и (1.21)
этап I ®ж = »г-Щ(1+Е12-‘). sign ==• sign 6г,
этап II Xi+i — хг 4- £г 2%,
где i=l, 1, 2, 2.п—1, п—1.
Начальные условия- 0t=x, #1—0, Xi = l.
Результат: хп=ехрх.
Вычисление функции 1пх путем непосредственного использования выражения (1.3) приводит к необходимости вычисления на каждом шаге разности (х,—1) и последующего восстановления величины Xi с помощью прибавления единицы. Можно упростить этот алгоритм и сделать его однотипным с остальными алгоритмами, если при вычислении функции In X использовать тождество
1п[1 4-ГМГ]=—1пХ при У=1 — X.
В этом случае рекуррентные соотношения для функции 1пх:
У i+i = УI —
этап I Х/+, ~ Xl + 2~lxt,	(1-31)
sign 5; = sign yit
этап II 0l+1 = 6z4-ln(14-^2-‘),	(1.32)
где i=l, 1, 2, 2, ..., п—1, п—1
Начальные условия: х^=х, У\ = \—х, 01 = 0;
Результат: 0П=—1пх.
Для прямых и обратных гиперболических функций все обозначения 0f, Xi аналогичны соответствующим обозначениям для тригонометрических функций.
Функции ship, ch ф. Рекуррентные соотношения представляются в следующем виде:
Л+1 = ег — SjArth 2~‘, , этап I	1
sign ?z = sign 6Z, этап II ?'+! = ?<+ лг+1 = хг+Вг2-‘у,,
где i=l, 1, 2, 2,	п—1, п—1.
Начальные условия: 01 = ф, Xi= 1, */i=0.
Результаты: уп — Kh-shtp, xn—Kh- ch ф.______
Функции Arth {Y/X), Arcth (X/Y), V(X2 — У2). Рекуррентные соотношения:
V/+i = yi-^2-% этап I Xi+t = Xi — £z2~zyz, sign fz = sign yz, этап II 6,+1 = 6, + EtArth2-i,
где i=l, 1, 2, 2,	n—1, n—1.
Начальные условия: xx=X, y\ = Y, 0i = O.	_______
Результаты: 0n=Arth(K/X),0n=Arcth(X/У),хп = ХпУ(X2~Y2). Все рассмотренные выше рекуррентные соотношения могут быть использованы для знакопеременных шагов итераций. В случае применения способа знакопостоянных шагов при вычислении функций In х, ехрх, Ух начальные условия для пер--вых двух функций не изменятся, а рекуррентные соотношения примут следующий вид.
Для функции 1пх в соответствии с (1.4) и (1.31):
У/+1 = Уг-^2-%, этап I Xz+1 = xz + ^z2-%, = sign(yz — 2~%), этап II 0z+i = 0Z +£zln(l 4-2~‘), где i=0, 1, 2, ..., п—1.
Для Функции ехрх в соответствии с выражениями (1.5) и (1.21):
этап I
ez+i = 6z-vn (1 + 2-9, ^=sign[ez-in(i + 2-')],
этап II Xz+i = xt + £z 2&cz,
где i=0, 1, 2, ..., п—1.
Для Функции ]fx в соответствии с выражениями (1.22) и (1.31):
У1+1 = У1 —	%,
этап I Хг+1 = xz-Hz2-%
В/= sign (yz — 2-%),
где t= 1, 1, 2, 2, ..., п—1, п—1,
этап II 6z+i = 6Z-|- Bz2-Z 6Z,
где i=l, 2, ..., и—1.
Начальные условия: xz=x, yz = l—х, 0z=x.
Результат: Qn=V^x.
Для операции деления рекуррентные соотношения; запишутся аналогично с.той лишь разницей, что величина 1=1, 2, 3, ..., п—1 для обоих этапов.
Начальные условия: xz=x, z/z = l—х, Qi=y.
Результат: f)n=z=-y/x.
Перейдем к рассмотрению способа Меджита.
Способ Меджита
При реализации метода «цифра за цифрой» по способу Вол-дера оба этапа вычисления элементарных функций выполняются одновременно и составляют единый процесс. Основным отличием способа Меджита является последовательный характер выполнения этапов. Э^о позволяет представить этапы в виде алгоритмов, сходных с алгоритмами обычного деления без восстановления остатка и умножения с младших разрядов множителя. С этой точки зрения способ Волдера аналогичен одновре менному выполнению деления без восстановления остатка со сдвигом делителя вправо и умножению со старших разрядов множителя.
Формально переход от записи рекуррентных соотношений по Волдеру к записи по Меджиту-осугцествляется с помощью подстановки:
zz = 2'yz.	(1.33)
Кроме того, рекуррентные соотношения этапа II при реализации по способу Меджита записываются с убывающим ичдек-сом. Для функций sirup, costp, arctg (Y/X), arcctg(Y/X), |^(№+У2) значения индекса i на этапе I: t’=0,1, 2, ..., n—l,a на этапе II: i=n, n—1, n—2, ..., 2, 1.
При вычислении функций Inx, expx, shtp, chtp, Arth(K/X), Arcth(F/X), K(2C2- Г2) индекс i на этапе I принимает значения: i=l, 1, ..., n—1, n—1, а на этапе II: i=n, n, n—1, n—1, .... 2, 2.
При записи рекуррентных соотношений будем использовать те же самые обозначения, что и для-способа Волдера.
Функции sin <р, cos ф. В соответствии с выражениями (1 11) <1.26), (1.27) и (1.33):
т 6z+i = 2(6z — BZ2Z arctg2~z), этап I
sign = sign 0Z,
.	=	— Ez_j xt),
этап II
Начальные условия: 6о=ф, zn=0, Xn=^/K.
Результаты: г0=sin ф, х0=cos ф.	_____
Функции arctg(K/X), arcctg(y/Ar),| (A'2 | y2). В соответствии «выражениями (1.9), (1.23), (1.24), (1.25), (1.33):
zz+i = 2(zz —Bzxz), этап I Xz+1 = xz + Bz2-2z2z, sign ti = signzZ) этап II 6z-i = 2“1(6Z4-Bz^i2/~1 arctg2-(z-1>). Начальные условия: г0= Y, x0=X, 0n = O.
Результаты: xn = K.'\^(X2 -j- Y2), 0O=—arctg(y/X), 0о+л/2 = = arcctg(F/X).
Функция Inx. В соответствии с выражениями (1.31), (1.32) и (1.33):
zi+1 = 2(zz — kt Xi),
этап I Xz+1 = xz4-Ez2-zxz, sign it = signzz, этап II ez_1 = 2-I[0z + 2z~4n(l+EZ_12-<Z-»)].
Начальные условия: Zi=l—x, xj=x, 0n = O.
Результат: 0Z=—Inx.
Функция expx. В соответствии с выражениями (1.4), (1.21) и (1.33):
этап! 0Z+* =	2Чп(1 +£/2-9],
sign Bz = sign 6Z,
этап II хг-_1 = 2_,(Л:«+	2“(z~*>xz).
Начальные условия: 01=х, хг = 1.
Результат: %i = expx.
Функции sh ф, ch ф. Аналогично полученным выше рекуррентным соотношениям для тригонометрических функций:
. ez+1 = 2(0z - BZ2Z Arth 2-z), этап ilv г 1
*sign£z = sign6z,
этап II
X^^Xi + ^-^Zi.
Начальные условия: 6i = <p,zn — 0, хп—1.
Результаты: Zj=Xhsh <р, Xi = /(hch <р.
Функции Arth (YIX), Arcth (Х/У), V(X3 — У2). Рекуррентные соотношения:
zz+i = 2(z/— i.tXi), этап I Xz+1 = xz-^2-2%, sign — sign zt,
этап II 6/_1 = 2-40i + ^-i2i-,Arth2-<i-i)).
Начальные условия: Xi=X, Z\ — Y, 6n = 0.
Результаты: O^ArthCK/X), 6i = Arcth (Х/У), х„ = Лл]<СХ3-Г2).
С помощью метода «цифра за цифрой» путем задания соответствующих начальных условий можно выполнять операции преобразования координат.
1)	поворот осей координат;
2)	преобразование из прямоугольной системы координат в полярную;
3)	преобразование из полярной системы координат в прямоугольную.
Данные преобразования
могут выполняться кап: с тригонометрическими, так и с гиперболическими векторами.
Введем в рассмотрение параметр С, принимающий два возможных значения С£{+ 1, —1}. Запишем с учетом этого параметра выражения для преобразования координат [80]:
1)	Хп = Xc[Xcos (т С’/2) + KC^sin (<р С1/2)],
уп = Хс [ Feos (<? С1'2) - X С1'2 sin (<р С1'2)];
2)	х„ = ХсГ(Х2 + ^2),
e„ = C-V2arctg(U'2r/X);
3)	хя = X;XcCos(o^2),
уп = К^~^ sin (<? О/2).
Здесь С= + 1 для тригонометрических функций, С =—1 для гиперболических функций, Кч —коэффициент деформации тригонометрического (С = + 1) или гиперболического (С =—1) вектора, —тригонометрический или гиперболический радиус.
При использовании управляющего соотношения signg,= = sign0, и начальных условиях хнач=Х, ую.ч=¥, 0нач=<р вы
полняется операция 1). Для тригонометрических функций она имеет вид (рис. 4):
хп ±= ЛГ(Хсо8 <р+ Ksirnp),
' y,t —	Y cos ®— Xsin<p).
Для гиперболических функций эта операция имеет вид хп = Kh{X ch © — У sh ср), y« = ^A(^ch?-Xsh-d).
При начальных условиях Унач—X, Увач—Y, бнач—0 и использовании управляющего соотношения sign|i=signz/j (для способа Волдера) wiHsigngi = = sign Zi (для способа Мед-жита) выполняется операция 2), представленная для тригонометрических функций на рис. 5:
Рис. 5
х„ = /а/(х2+Р),
е„= arctg (Y/X).
Для гиперболических функций эта операция будет хя = лгЛГ(^2-г2),
S6„ = Arth(K/X).
При начальных условиях Хнач=Дс, Увач=0, 0Нач=Ф и использовании управляющего соотношения sign &= sign 0г- выполняется операция 3), которая для тригонометрических функций имеет вид
хп = A7?cos<p, уп = A7?sin ©,
а для гиперболических функций
*я = /<лЯлсЬф, yn==^Ash<p.
Принципиально все рассмотренные преобразования координат могут быть выполнены не только на плоскости, но и в пространстве, но для этого необходимо трижды повторить выполнение соответствующей операции. -
Во всех предыдущих рекуррентных соотношениях для вычисления прямых и обратных тригонометрических и гигерболи-ческих функций предполагалось, что вращаются -оси координат, а соответствующие векторы остаются неподвижными. Можно
цечать и наоборот —вращать непосредственно сами векторы, оставляя неподвижными оси координат. Для сохранения общепринятых знаков отсчета углов («плюс»—против часовой стрелки, «минус»— по часовой стрелке) необходимо переписать рекуррентные соотношения в следующем виде:
способ Волдера
У/+1 = У/ + ^2-%, xz+i = xz —
sign gi = sign 0j для 1) и 3) операций, или signgz = —signy» для 2) операции;
способ Меджита
Zi_1=2-1(zi4-Ei_Ixi),
*	л:/-! ==	—2-2U-n^.,
sign gi = sign для 1) и 3) операций, или	zi+1 = 2(zz + £z xz),
xz+1==xz-+z2-2+z, signgi=—sigrzs для 2) операции.
При этом остальные соотношения и начальные условия не меняются.
Рекуррентные соотношения для вычисления по способу Меджита функций in х, exp х, Ух со знакопостоянными шагами итераций записываются аналогично соответствующим соотношениям для способа Волдера с заменой ln(l—j—2—<) на 2i-1X Xln (1+2 Н'-П) и подстановкой zi = 2iyi.
Анализируя рекуррентные соотношения для вычисления элементарных функций, представленные в соответствии с двумя способами их реализации, можно прийти к выводу, что в обоих способах этап I аналогичен операции деления, а этап II — операции умножения. Отличие состоит в том, что при выполнении этих вычислений на каждом шаге соответственно делитель и множимое модифицируются В связи с этим как сами операции, так и их результаты получили названия с приставкой «псевдо»—псевдоумножение, псевдочастное и т. д.
Обобщая рекуррентные соотношения, построим графическую схему вычислений. Для наглядности представим на этих же рисунках графические схемы выполнения операций деления без восстановления остатка и умножения соответственно со старших (рис. 6) и с младших (рис. 7) разрядов множителя. Нетрудно заметить, что операции деления и- умножения представляют собой частный случай операций псевдоделения и псевдоумножения. Поскольку при реализации метода «цифра за цифрой» по способу Волдера. оба этапа вычисления выполняются совместно, то при этом может быть реализована составная операция •—«умножение — деление».
Установка 3„0" х у,i
Множимо -* X Множитель* L
ьц.,-Уь'2'1Х1 “ Д' i
i:~ i+1
Li'2
Рис. 6
Допустим, что необходимо определ _ть результат операции U = (A/B)C} где OsCC<l, |/?| — |А| > 0. Частное от деления A/В может быть представлено в виде суммы [7]:
где £/£{—1, +1}.
Данное выражение можно переписать:
Д-Д2^1^2-8==0^	(1-34)
Результат Z-го шага вычислений обозначим
Из выражения (1.34) при правильно организованной операции деления следует, что limxj_|_i=0. Отсюда видно, что зна-i-мг
ки операторов & должны удовлетворять соотношению signgi = = signxj. Одновременно с получением х t+i вычисляется величина
M+i = C2Ui^2--\
Обозначим B—yi, C=Zi. С учетом этого запишем
-XZ+-! = xt — 2-гуг, у/+1 = yt,
Ut f-i = Ui 4- 2 zi+i = zt.
Начальные условия: Xi=A—В, yi = B, Zi = C, t/j = O.
Результаты: xn = 0, yn = B, zn = C, Un=(A/B) C.
В табл. 1 сведены рекуррентные соотношения вычисления рйда элементарных функций по способам Волдера и Меджита. Как следует из этой таблицы, формальные отличия способов Волдера и Меджита состоят во временной последовательности выполнения этапов, использовании подстановки г^=24у,, в характере изменения зависимости величины итерационных шагов от номера итерации и в форме задания табличных констант. Эти отличия существенным образом влияют на ряд технических характеристик реализации двух указанных способов: точность, быстродействие, структуру операционного устройства, блок микропрограммного управления, объем ПЗУ констант.
Все эти отличия подробно проанализированы в следующих главах.
Сопоставляя между собой, способы знакопостоянных и знакопеременных шагов итераций, можно отметить, что первый способ с точки зрения быстродействия более выгоден при вычислении функций 1пх, ехрх.ф х. Второй способ из-за постоянства коэффициента К? эффективнее при вычислении прямых и обратных тригонометрических и гиперболических функций.
Алгоритмы итерационного процесса со' знакопеременными шагами использованы-впервые в работе Волдера [78], что по-
Таблица I		
Функции	Рекуррентные соотношения	
	способ Волдера	способ Меджита
exp х	I 6/+1 fiz-ln (1+^2-') sign $z=sign fiz II xl+i=Xi+ii 2~‘xt	I 0z+i=2[Bz--2zIn (l+ez2~‘)] sign ez=sign ez II ^-1=2-’ (xz+ez_j 2 -(i~l)Xi)
sin x cos X	I ez+i=ez—£z arctg 2“' sign sz=sign 6Z II У/+1=УгЛ 2_/ Xi xl+l=Xi+^2~l yz	1 ez+i=2 (Bz—£z 2Z arctg 2~l )' sign Ez=sign Bz II zz_]=2	(z'z %i—ixi} Xi_l=xi+^l_l 2 “2 (Z-I) Zi
arctg (y/x)	I У/-|-1=У' & 2 ‘ xl х1+1=х^1 2Г1 yt sign 5Z—sign yz II 6Z+1=6/+Sz arctg 2~l	I s'z+i^2 (-^z—?z^z) Xi+I=Xi+it 2~21 Zi sign Bz=sign zi II 6^=2-’ (Bz -j- ?z_j 2 '-’arctg г-!'-1’)
arcsin у	I	yz+r -У1—Ъ 2~‘ Xi xi+l=Xi+^t 2~‘ yz sign Bz=sign (yz—y№) sign xi 11 ez-H=et+5j arctg 2~z	
зволило вычислять функции sirup, costp, arcsin(E//?), агссо8(Х//?)„ ]/\Х2+У2) по методу «цифра за цифрой».. В появившихся примерно в то же самое время • статьях И. Я. Акушского и Д. И. Юдицкого [1], а также Е. Д. Лапыгина [19, 20] используется способ 'знакопостоянных шагов, что явилось причиной отсутствия в этих работах простых алгоритмов вычисления вышеназванных функций.
Основную трудность при использовании способа знакопостоянных шагов итераций и недвоичных-систем счисления представляет вычисление коэффициента К, определяемого, например, для тригонометрических функций как
К= у2 П?=1(1 + %	'	(1 -35)
Это приводит к снижению быстродействия, так как кроме непосредственного вычисления фунций необходимо еще определять величину К- При использовании способа знакопостоянных шагов итераций в ЦВМ, работающих в двоичной системе счисления, время (вычисления функций увеличивается при этом в два раза [40].
При использовании недвоичных систем счисления вместо непосредственного вычисления коэффициента К можно зафиксировать величину qi для всех i от 1 до пи взять ее равной либо (а—1) — для прямых тригонометрических функций и функции arctg(F/X), либо равной а — для прямых гиперболических функций, In х и ехр х, и, наконец, равной 2(а—1) — для функций, arcsin х и arccos х. В этом случае коэффициент К есть постоянная величина.
Если учесть, что при значении i^>n/2 выполняется условие a~2i<a~n, то, следовательно, все члены произведения (1.35) с номером, большим п/2, не увеличивают значения К в пределах n-разрядной точности. Поэтому величину qi можно фиксировать только для значений i=l—«/2, а для больших значений i брать величину qi в соответствии со знаковыми соотношениями.
Второй способ состоит в исключении коэффициента К делением:/С sin ф/ (К. cos ф). Найденная при этом функция tgф используется для последующего определения функций sin ф и cos ф по известным тригонометрическим тождествам.
1.5. ПРИМЕНЕНИЕ МЕТОДА „ЦИФРА ЗА ЦИФРОЙ" ДЛЯ ПРЕОБРАЗОВАНИЯ СИСТЕМ СЧИСЛЕНИЯ
Основная идея метода «цифра за цифрой»— использование заранее заданных приращений аргумента — может применяться не только при вычислении элементарных функций, но и в более широких областях: нахождении корней полиномов [69], двоично-десятичных и десятично-двоичных преобразованиях [51].
Использование метода «цифра за цифрой» для преобразований систем счисления базируется па тех же принципах, что и вычисление элементарных функций. Выше указывалось, что первый этап вычисления элементарных функций может быть интерпретирован как операция по преобразованию систем счисления— из двоичной в систему с весами: ln(l±2-'), arctg2~' и т. Д.
Преобразования из двоично-десятичной системы счисления в двоичную и из двоичной в двоично-десятичную осуществляются аналогично вычислению элементарных функций — в два этапа. На первом этапе исходная информация преобразуется в промежуточную систему счисления. Результат первого этапа— набор операторов £{—1,4-1 } , соответствующих заранее вычисленным константам преобразования. На втором этапе от промежуточной системы счисления переходят к представлению результата в заданной системе счисления.
Для представления цифр одной десятичной тетрады, работающей в коде 8- -4—2:—1, используется набор нечетных чисел: -—9, —7, —5, ... , —1, +1, ... ,+7, -|-9. Правило соответствия:
T = Q/2 + 9/2,	(1.36)
где Т — величина, обозначаемая цифрами 0, 1, ... , 9; Q —ве-.-личина, обозначаемая цифрами—9, —7.......-|-1, -|-9. '
Пусть t-я десятичная тетрада какого-либо числа имеет вид
 Тс 10' = dt&-10' + d/34-10'+ dl22-10' + da-10',
где da £{0,1}.
Используя (1.36), перепишем данное равенство:
7> 10' = £44-10' + ^2-10' + £21  10' + £41/2)  10' + (9/2) • 10', где £•;£{—1, +1}.
В общем виде переход от набора, состоящего из п-}-1 числа: (7=0,1, ... , и), к набору, состоящему из чисел: W=—w, —ay-J-2, ... , —1, 4~U	> w—2, w осуществляется по
правилу V=W/2-\-v/2.
Таким образом, на первом этапе осуществляется преобразование
[?|дв. дес -> £11	^13 ^14 ^21 ^22 •••	••• ^4-
После .того как получены операторы g,, для всех тетрад, двоичное число находится суммированием констант с учетом знака
[?]дв = (1/2)	10-1-(Р+1)1 _|_ уч=1 .10-['-(Р+1)1 £4=1 £У2-О-3),
где t — общее число тетрад, 6, — число различных цифр в i-й тетраде, р — минимальное число, при котором выполняется условие [ф] дес<Д-1(Х
При решении широкого круга задач часть переменных представляется в виде углов. Рассмотрим в связи с этим особен-
ности кодирования отдельных десятичных тетрад при изображении углов, выраженных в градусах.
При кодировании цифр тетрады, соответствующей сотням градусов, надо учитывать, что максимальная величина их может быть равна трём (в случае, если рассматриваются углы от О до 360°) или единице (если рассматриваются углы от 0 до 180°),. Следовательно, в любом случае для ее кодирования используется неизбыточный код, а константа b равна соответственно трем или единице. Для кодирования’ цифр десятичной тетрады, изображающей десятки минут, константа Ь=5, используемый код имеет избыточность, равную пяти. Аналогичную избыточность имеет код для тетрады, соответствующей десяткам секунд.
Первоначально преобразуемый угол записывается в регистр у. В регистр х записывается единица, с помощью которой в дальнейшем образуется дополнительный код содержимого регистра у. В регистр угла в начале операции засылается константа
g = (l/2)
В конце итерационного процесса в этом регистре образуется двоичный код угла. Управление осуществляется знаком' регистра у.
При преобразовании угла из двоичного кода в двоично-десятичный используются те же самые константы и схемы управления. Преобразуемый код засылается первоначально в регистр угла. Затем из него начинают последовательно вычитаться константы, с учетом управляющего знака, начиная с константы g. Код 8- 4—2—1 формируется в у-регистре (ячейке). Управление осуществляется по знаку углового регистра.
ГЛАВА 2
АНАЛИЗ ПОГРЕШНОСТЕЙ ВЫЧИСЛЕНИЯ ЭЛЕМЕНТАРНЫХ ФУНКЦИЙ
2.1.	ВВОДНЫЕ ЗАМЕЧАНИЯ,
Любой алгоритм, реализуемый на вычислительной машине, может быть охарактеризован тремя параметрами: точностью реализации, временем реализации, требуемым количеством оборудования.
Анализ погрешностей алгоритмов вычисления элементарных функций как по методу «цифра за цифрой», так и с помощью других методов недостаточно исследован в литературе. В' связи с этим вопросы анализа точностных характеристик исследуемых методов объединены в отдельную главу и предшествуют рассмотрению вопросов, связанных с оценкой двух других параметров.
Погрешности результата решения любой вычислительной задачи можно разделить на две категории: погрешности алгоритмизации и погрешности реализации.
Причина первой категории погрешностей — это несовершенство, приближенность математической модели, на базе которой строится алгоритм, описывающий исследуемый предмет, явление, процесс. Погрешности этой группы изучаются специальными дисциплинами, к которым относятся решаемые задачи. Например, многие навигационные задачи решаются с помощью методов сферической и сфероидической геодезии [32/ 37, 64], при этом погрешность алгоритмизации представляет собой погрешность представления формы Земли сферой, эллипсоидом или геоидом.
Погрешности, относящиеся ко второй категории, возникают на этапе реализации алгоритма решения поставленной задачи. В зависимости от объекта и метода реализации они могут иметь различную величину и физическую природу. Однако во всех случаях погрешности можно отнести к одной из трех групп:
1)	методические (остаточные, аналитические, принципиальные) ;
2)	инструментальные (возникающие, арифметические, зарождающиеся) ;
3)	трансформированные (неустранимые, наследственные, распространяющиеся).
С точки зрения анализа погрешностей вычислений на ЦВМ существенную специфику представляют собой инструменталы
ные погрешности. По сравнению с соответствующей группой погрешностей аналоговых вычислительных устройств инструментальные погрешности цифровых вычислителей обусловлены тремя особенностями: дискретной формой представления информации; сведением всех вычислений к последовательности арифметических и логических операций; наличием операции округления. Различные способы выполнения арифметических операций и влияние их на погрешности вычислений будут рассмотрены ниже.
Пусть.	pi 2~‘; pz£{0,l}. Тогда основные способы
округления следующие:
1)	отбрасывание всех разрядов, следующих за п-м;
2)	добавление «1» к рп, если p«+i = l;
3)	установка рп = 1 во всех случаях;
4)	добавление «1» к pw, если рп = 1;
5)	добавление «1» к рп случайным образом;
6)	добавление «1» к р™, если pn+i A(₽n+2V ₽«+з\/.;-- V Pn+fe) — 1 •
В ряде работ [31, 37, 61] указывается, что наиболее достоверными оценками погрешностей вычислений на ЦВМ служат их статистические характеристики. Объясняется это многими факторами, основными из которых являются два обстоятельства: во-первых, сам статистический характер возникновения погрешностей [13, 4.1, 61, 77] и, во-вторых, наличие большого числа независимых компонент, составляющих результирующую погрешность вычислений. Например, суммарные погрешности вычисления элементарных функций — это композиция методических, инструментальных и трансформированных составляющих. В свою очередь, на каждую из составляющих влияет несколько факгоров. Например, инструментальная погрешность обусловлена ошибками представления операндов, наличием округлений, погрешностью выполнения самих операций.
В силу этого можно считать, что функция распределения результирующей погрешности будет иметь вид, близкий к нормальному. Для нормального закона распределения имеет место известное соотношение между максимальной (Д) и среднеквадратической (<т) оценками погрешностей, выполняющееся с вероятностью, равной 0,9973 [41]: Д^Зо.
В связи с этим можно считать, что две статистические оценки — математическое ожидание и среднеквадратическое отклонение— довольно полно и достаточно объективно характеризуют погрешности вычисления элементарных функций.
Следует отметить, что при вычислениях на ЦВМ статистический анализ погрел Гйостей рассматривается по отношению к случайным значениям аргументов, так как при повторных вычислениях с одними и теми же исходными данными на исправно работающей машине результат не меняется.
В начале данной главы анализируются среднеквадратические погрешности элементарных функций, вычисляемых по методу «цифра за цифрой» при использовании знакопеременных приращений па ЦВМ. с фиксированной 'запятой.
В силу отличия двух способов реализации метода «цифра за цифрой»— по Волдеру и по Меджиту — погрешности каждого из них должны быть рассмотрены отдельно. В то же время, как показывает анализ рекуррентных соотношений, для вычисления различных элементарных функций по обоим способам, приведенный в гл. 1, они могут быть разбиты на две группы: выполняемые по типам операций «поворот» и «вектор». К первой группе относятся функции sin ф, cos ф, ехр х, ко второй группе следует отнести функции arctg (F/X), arcsin(F/.R), arccos(X//?), 1пх. Вначале будут рассмотрены погрешности элементарных функций, вычисляемых по способу Волдера по типам операций «поворот» и «вектор». Анализ погрешностей вычисления элементарных функций по способу Меджита, частично основанный на полученных результатах, проводили совместно для двух типов операций.
Затем будут проанализированы вычислительные погрешности метода полиномиальной аппроксимации, нашедшего наибольшее распространение при реализации элементарных функций на цифровых машинах.
2.2.	ПОГРЕШНОСТИ ВЫПОЛНЕНИЯ ОПЕРАЦИИ „ПОВОРОТ1*
Независимо от вида операций, выполняемой по методу «цифра за цифрой», погрешности вычислений каждой из них могут быть разбиты на три группы:
методические погрешности усечения итерационного процесса;
инструментальные погрешности, обусловленные потерей точности при сложении, округлении и сдвиге;
трансформированные погрешности как исходных данных, так и промежуточных вычислений.
Несмотря на то, что оба этапа вычисления элементарных функций при реализации по способу Волдера производятся одновременно, анализ их погрешностей может быть проведен применительно к каждому из этапов. Проанализируем с этой точки зрения погрешности операции «поворот». Будем считать, что погрешности исходных данных (аргументов функций) — отсутствуют. Назовем в этом случае- общую погрешность вычисления элементарной функции приборной погрешностью.
Рекуррентные соотношения выполнения операции «поворот»:
этап! «w-e.-E.arctgZ-',
sign = sign 6г,
этап II
У/+1 = Уг—-^2-%, х/4-1 = хг + Ег 2“‘у,.
(2.2}
Погрешности этапа I (буква В в верхнем индексе здесь и далее означает: по Волдеру):
методическая погрешность конечного числа итераций — оБ ;
п. м’
инструментальная погрешность алгебраического суммирования округленных констант— б®кон. '*
Погрешности этапа II:
погрешность, трансформированная из этапа I,—оБ т;
инструментальная погрешность вследствие сдвигов на I разрядов вправо—• бп. и.
Рассмотрим погрешности этапа I. Дисперсия методической погрешности, в предположении равной вероятности появления положительных и отрицательных членов, равна
D* м = 2 2^„+1(arctg2-(‘ -D)2.1/2,	(2.3)
где п — число шагов итераций.
Возьмём первый член разложения функции arctgx в ряд Тейлора, получим с точностью до 2-10_4 % единиц младшего разряда
arctg 2^6-1) = 2“<г-1),	4	(2.4)
где j'min Л-|-1.
Подставив (2.4) в (2.3) и выполнив соответствующие преоб-, разевания, получим
^.м = (1/3)2-2(-п.
Среднеквадратическая погрешность определится:
4м=(2//3)*2-«.	(2.5)
Дисперсия погрешности, обусловленной алгебраическим суммированием л округленных констант, записанных в памяти, в предположении равной вероятности появления положительных и отрицательных членов, равна
4BKoH = 22LiioH-l/2,	(2.6)
где п — число констант; Окон — погрешность округления констант; */г— вероятность появления положительного или отрицательного члена.
Определим величину среднеквадратической погрешности ОКругЛеНИЯ КОНСТаНТ — Икон-
Ошибки округления асимптотически являются независимыми равномерно распределенными величинами [61, 77]. В зави
симости от принятого способа округления среднеквадратические погрешности составят:
для округления усечением стр. 35, способ 1):
Okoh = (1V3)-2~«,
для округления симметричного (стр. 35, способ 2): s
4h = (V(2}/3))-2-«.	' (2.7).
При округлении по первому способу, кроме случайной составляющей погрешности, возникает еще систематическая составляющая, равная приблизительно половине единицы младшего разряда.
В ЦВМ константы округляются чаще по второму способу. Подставив выражение (2.7) в (2.6), получим
кон= [2£«=1(1/(2уз))2 1/2]2-2".	(2.8)
Преобразуя (2.8), получим выражение среднеквадратической погрешности
4. кон = (1^/(21/'3))2-«.	(2.9)
Общая погрешность первого этапа составит
4/=m. J2+(°пв кон)2 = (кя^б/(2Гз)). 2-«.
Определим погрешности этапа II. Погрешность, трансформированная из этапа I, с учетом того, что величина угла поворота единичного вектора может принимать значения в промежутке 0—90° с равной вероятностью, определится:
ов	Цп+16 2_„
н.т	2	21'3
Более сложным является анализ инструментальной погрешности вследствие сдвигов на каждом шаге. Рассмотрим подробно этот вопрос.
В соответствии с выражением (2.2) на (г-)-1)-м шаге за пределы разрядной сетки при сдвиге выходят I разрядов, образующих остаток. Поскольку появление положительных и отрицательных остатков равновероятно, считаем, что математическое ожидание погрешности равно нулю. Предположив равновероятность появления единиц и нулей в разрядах остатка, запишем выражение дисперсии погрешности вычислений за счет сдвига на (i’+1)-m шаге;
где k — возможная величина остатка; l/(2i+1—1)—вероятность появления любой комбинации единиц и нулей в разрядах
остатка; 2~2i— квадрат масштабного коэффициента приведения погрешности к единице младшего разряда; (2г—1) — максимальная величина остатка (в- единицах младшего разряда),
Преобразуя (2.10) и используя формулу суммы квадратов натуральных ч'исел, получим
(9г+1 1_ 9 1_3	1	\
------S—1 •	’2“	<2Л1>
Воспользуемся разложением (2i+1—I)-1 по биному Ньютона:
i)-i = 2-('+i)	2-2<;+О + 2-3('+D + ...	(2.12)
Взяв первые два члена разложения (2.12), перепишем (2.11):
nR 1  9-^  О”2^ + ')  I- 9—(3;+2)
D? , = 1 z	z_______L_f_______ . 9-2n
,+1 3 •
С погрешностью, не превышающей 0,5%, можно записать, что • 4-н = К(1 - 2-г)?3 • 2-«.	(2.13)
Общая дисперсия погрешности за п шагов в предположении независимости погрешности каждого шага составит
D*.
Подставив в эту формулу значение Df+l из (2.13) и преобразуя её, получим величину среднеквадратической погрешности
' 4. и = К(й-2)/3-2-«.	(2.14)
Может оказаться, что величина и превысит допустимую величину среднеквадратической погрешности вычислений. В этом случае необходимо увеличить длину разрядной сетки операционного устройства, оставив все остальные параметры (число шагов, разрядность констант и др.) без изменения. Допустим, что к регистрам добавлено г дополнительных разрядов. В этом случае выражение (2.10) перепишется:
(П-21	2______1 £29—2п
Di+i, г =	2/-г44 -1	Г "
Для дисперсии погрешности за п шагов получим
£)в	__1 Пв	2 2г(» —г —2) g_2n
п. иг .2<»=г+Г«+1. г''"'	3 z
Среднеквадратическая “погрешность определится как
.	(2.15)
Общая приборная погрешность операции «поворот» составит
°пв - v w жя н г)2 = V т+и Нг-^2г • 2-п.
На рис 8 графически изображена зависимость погрешности вычислений о® от числа разрядов исходных чисел п при различном числе дополнительных разрядов г. Для большей наглядности по оси ординат отложена относительная среднеквад-
ратическая погрешность — ,а^ -2п.
Рассмотрим трансформированную погрешность исходных данных. Считая погрешности входных величин и погрешности округлений чисел независимыми, запишем выражение погрешности исходных данных при операции «поворот»
°ис = VW+Ж)
При повороте координат
Рис. 8 или вектора на угол ф величины трансформированных погрешностей новых координат (х и у) связаны с величинами погрешностей исходных данных следующими зависимостями:
°хт = К(°исЛ- COS <р)2 + (оису- sin <р)? + (/? O„c<psina>)3, °ут = V(°ИСЛ- sin <р)3 4- (oHCycos ср)3 + (R Оис <р COS ср)2. Предположив наиболее вероятным углом поворота 45°, при R =1,0 получим
Ът = «ут = (Г2/2)	+
При условии (Тис <р = (Тисх = '(Тис у ПОЛуЧИМ <Тхт = <Тз/т= <3ИСК(3/2).
Погрешности вычисления функции ехр х во многом аналогичны соответствующим погрешностям операции «поворот». Основное отличие состоит в использовании способа «двойных» шагов.
Рекуррентные соотношения для вычисления функции ехрх: . ez+1 = et- in (1 + ^2-9, этап I
sign It = sign 6г,
этап II xi+i =	E/2-%.	(2.16)
Погрешности этапа I: инструментальная погрешность суммирования 2п округленных констант— о® кон;
методическая погрешность усечения итерационного Процесса— аем-
Погрешности этапа II:
погрешность,-трансформированная из этапа I, — авт;
инструментальная погрешность из-за сдвигов на i разрядов вправо — с’е и-
Погрешность а® кон определяется аналогично формуле (2.9):
ов _ l'2” о-" екон 2]/3"
Дисперсия методической погрешности в предположений равной вероятности появления положительных и отрицательных членов в отброшенной части ряда
Певм=(1/2)^1[Ш(1 +2 9]2+ [1п(1^-2-‘-)]2. (2.17)
Преобразуя (2.17), получим выражение среднеквадратической погрешности
^м=(1//3)2-«.	(2.18)
Общая погрешность этапа I определяется как
ав = |/’(ов )2 I /ов)Т= >/2я _4 2-«. е/ ' ' екон' I \ ем' 21/1Г
Погрешности этапа II:
погрешность, трансформированная из этапа I, равна
ов ==;К2п + 4 ет 2]/3
Дисперсия инструментальной погрешности из-за сдвигов; вправо на (i-1-1) -м шаге определится как
Поскольку Xi=4 (см. 1.4), то из выражения (2.16) следует,. что выход за разрядную сетку вправо части разрядов начинается только с (п/2+1)-го шага. Следовательно, на п-м шаге суммарная дисперсия составит
пв _ у»-1 пв ____________ 2 %г‘2(п!‘2 г — 2) (у 9п
ей ^»=и/2+1+г 1+1, г	з
Среднеквадратическая“йогрешность определится как
ав = 2~г / ей
2-«.
Общая приборная погрешность вычисления функции ехр х составит
=m)2+w = V 2(w/2-y---2)- 2	+2-^ 2-.
Обозначив, как и ранее, погрешности исходных данных <тпс, возьмем первые члены разложения в ряд Тейлора функции ехр х при х=сгис:
ехр(апс)= 1 +оиС + ~^-+... -	(2.19)
Поскольку членами, следующими за вторым, ввиду их малости можно пренебречь, то считаем, что трансформированная погрешность исходных данных составляет сгис (поскольку при <Тпс=0 выраженйе (2.19) равно единице), т. е. коэффициент трансформации погрешности равен единице. Погрешность авт определялась аналогичным образом.
Оценки погрешностей вычисления функции определяются по тем же формулам, что и для операции «поворот». Исключение составляет только инструментальная погрешность суммирования констант, так как при операции ]/X управление осуществляется по знаку разности yi — (х—2~а) и, следовательно, погрешность а® кон отсутствует. Кроме того, при этой «операции используются «двойные» шаги.
Используя выражения (2'5) и (2.15), получим
«£»- +
2.3.	ПОГРЕШНОСТИ ВЫПОЛНЕНИЯ ОПЕРАЦИИ „ВЕКТОР11
Рекуррентные соотношения операции «вектор»:
Ун-i ~Vt~ Ъ2~1Х1,
этап I x/+i = xz + ^2-%	(2-20)
sign = sign уг,'
этап II 0z+i = 0г-|~£г arctg 2~1.
Погрешности этапа I:
инструментальная погрешность из-за сдвигов вправо на i разрядов —а®к и;
методическая погрешность усечения итерационного процесса — ав век. м
Погрешности этапа II:
трансформированная погрешность из этапа I — авек т ;
инструментальная погрешность суммирования п округленных констант —ав	.
Отметим, что поскольку результатом операции «вектор» являются две различные величины: arctg(K/X) и рЛ(№ + У2), то анализ их погрешностей неодинаков. Инструментальная погрешность этапа I вычисления функции arctg(K/X) определяется погрешностью вычисления ординаты уп по формуле (2.15):
Свек. иУ = ]/(« —2-г)/3 • 2-<^>.	(2.21)
.Методическая погрешность для обеих величин — arctg(T/X) и V(X2 4~ Y2) определяется по формуле (2.5)
= (2/|/3)2--	(2,22)
Инструментальная погрешность этапа I вычисления величины модуля вектора + У2) имеет две особенности. Во-первых, поскольку знак оператора в выражении (2.20) определяется по правилу sign = sign z/i, то это выражение можно переписать в виде:
= — ^2-%,
•*,+1 = */ + 2-'Ш
Отсюда следует, что погрешность вычисления абсциссы (модуля вектора) имеет и случайную и систематическую составляющие. Вторая особенность состоит в том, что вычисление модуля вектора заканчивается па итерационном шаге с номером, намного меньшим, чем п. Это объясняется тем, что произведение 2-г |у,| уменьшается при возрастании величины i по двум причинам. Во-первых, из-за увеличения отрицательного показателя степени, и во-вторых, из-за уменьшения величины |уJ. На некотором шаге с номером «+1 величина 2-’ |у,| выйдет за пределы разрядной сетки. Следствием этого будут два обстоятельства: на этом шаге закончится увеличение модуля вектора, определение погрешности вычислений до и после этого шага осуществляется по различным формулам. Определим величину s. Нй i-м шаге итерационного процесса можно считать, что угол между осью абсцисс и вектором, по крайней мере не больше, чем arctg2-</-1). В этом случае можно записать Уг^ЯгХ Xsin (arctg 2_(Z-1)),
где = llLiK(l
.или, переходя к строгому неравенству, yj</?maxsin(arctg2"=<z-1)), где
= |,W(1 + 2-2O-1))1/X2+ У2.
Для ЦВМ с представлением чисел с фиксированной запятой величины X и Y выбираются таким образом, чтобы выполнялось условие Л’тах^Н- Тогда
уг < sin(arctg2M'-O).	•	(2.23)
Запишем первые члены разложения в ряд функций arctg ц и sin th
arctg т] = т] — т]3/3 -|- t)5/5 —...,	(2.24)
sin i) = -8 — »3/3! 4- 85/5! — ... .	(2.25}
Второй член разложения (2.24) больше суммы остальных младших'.членов, а при = величиной самого второго члена также можно пренебречь, так как, например, если п=30, то уже при i=l l получим
7]з/3 = (1/3)2-3<г-1)<2-31.
В этом случае можно записать, что с точностью до единицы младшего разряда
«	arctg т) —7).	(2 26)
Для ряда (2.25) при г= 11
83/3! = (1/31)2-30-0 < 2-32.
Следовательно, аналогично запишем
sin8 = 8.	(2.27)
Из (2.26) и (2.27) следует, что
-sinS =т3 = 2-</-1>	t (2.28)
Подставий (2.28) в (2.23), получим, что уже при i^nl2 выпол няется условие t/i<2~<z-1). При i=n/2-}-l получим yn/2+i<2 ~"/2.' На следующем (п/2-]-2)-м шаге образуется величина 2' W2+2>X Хул/2+i, которая выйдет за пределы разрядной сетки. Таким образом, величина s-|-1 = п/2-|-2 и, следовательно, s=n/2-|-l-
Определим погрешность вычисления величины xs за первые (n/2+l) шагов. Считая равновероятными появления единиц, и нулей в разрядах остатка, сдвинутых за разрядную сетку, запишем выражения для математического ожидания и дисперсии погрешности на (t-f-l)-M шаге
Л4в+1= [(21-1 —
~ W - (2^‘ - 2-1))2] 2~2"’	(2.29}
где 2-’— коэффициент приведения погрешности к единицемладшего разряда; 1/2® — вероятность появления любой комбинации единиц и нулей в разрядах остатка.
Дисперсия погрешности за s шагов определится как
ЯвВек. ИД = sa( W)(2-2 - 2-2(‘+»)2-2«;
Среднеквадратическая погрешность с точностью не менее 2°/о равна
Овек.иД = К(1/6)(35 — 4)2-«.
(2.30)
В случае, если величина а®ек и R превосходит допустимую погрешность, то длину разрядной сетки увеличивают на г разрядов. В этом случае выражение (2.29) будет
- С2'^' -2-9)2]2-2«, где (г’-*"-1—2_>) 2~‘— математическое ожидание погрешности (в единицах n-го разряда); 1/2‘“г —вероятность появления единиц и нулей в разрядах остатка. -• .»
После преобразований получим
£>в г = (1 /3)(2-2<’-+1) — 2-2(/+1>)2-2л.
Дисперсия ошибки за s шагов составит
£)В	= yv-1 £)В
век. иг Xj(=r+1 Ж. г* •
Среднеквадратическая погрешность
авек. иг = (l/6)(2-^3(s-r)- 4)"2-«.	(2.31)
Определим инструментальную погрешность вычислений величины модуля вектора, начиная с (п/2-|-2)-го шага, т. е. с (s+1) до n-го шага. Дисперсия погрешности на (i-|-l)-M шаге	'
2
Дв л п _	(Л - (2^-1-2~>))22-2«,
где	—2—I)2—‘ — математическое ожидание погрешности
(в единицах n-го разряда);	(2n-i-1—1)—максимальная вели-
чина остатка (в единицах n-го разряда), 1/2и~‘— вероятность появления любой комбинации единиц и нулей в разрядах остатка.
Для приближенных расчетов примем.
£>в „^(l/3)(22(«-2Z-1>)2-2“.
Среднеквадратическая погрешность за п шагов определится
= ^2ид+Лв+1.» = (2-’/Г 3)2-".
Таким образом, погрешность вычисления величины Модуля вектора начиная с (s-M)-ro шага составит менее С,075 единицы младшего разряда и, следовательно, ею можно пренебречь.
Кроме инструментальной погрешности величина модуля вектора имеет еще методическую погрешность, обусловленную усеченней итерационного процесса. Эта погрешность на этапе II определяет конечный угол между осью абсцисс и вектором на последнем шаге итерации и, таким образом, трансформируется в погрешность величийы ]/ (А"2 + У2). Величина трансформированной погрешности
Овек.тЯ =	К2(1—COS (авек. м • Д)-
Разложим функцию cos(a^K м-л) в ряд Тейлора и возьмем первые два члена разложения:
*	( в I2
(°век. м • -) = 1 -	(2.32)
Анализ выражения (2.32) с учетом того, что Двек. м — (2/]/3) 2-л (формула (2.15)) показывает, что максимальное отличие величины cos(<j^eK м-тг)от единицы составляет не более 0,2% единицы младшего разряда, и поэтому величиной а®ек ,г/? можно пренебречь.
Следовательно, общая приборная погрешность величины модуля вектора определяется по формуле (2.31) прщ s = n/2+L Соответствующие графические зависимости представлены на рис. 9. Общая погрешность вычисления модуля вектора при г=0 определяется выражением (2.30).
Поскольку величина погрешности вычисления модуля вектора знакопостоянна, то для компенсации систематической составляющей можно прибавить к вычисленному значению xs математическое ожидание погрешности, которое составит
г = 2&1+1(2-<г+1)-2-0+1))2-2".
После преобразований получим
(S — 2 — Г)2-«.
Для больших п при г=0 запишем
А4вк^(/г/4)2-«.
Выясним, возникает ли погрешность вследствие того, что коэффициент деформации модуля вектора вычисляется по формуле

(2.33)
тогда как выше было показано, что число итерационных шагов, на котором прекращается возрастание величины К2), составляет s = n/2+1.
Возведем в квадрат обе части выражения (2.33):
№ = U"=1(l 4-2-2^1)).
На t-м шаге вычислений можно записать
ЛГ2 = nz-i (1 _|_ 2-2U-П)(1	2-20-D),
Перепишем это как /C2=(2-|-pz-i)+(2+p/-i) 2~2(‘~1\ где pz-i— дробная часть квадрата коэффициента деформации на (i—1)-м шаге, (2+pz-i) 2~2<i-1)-—увеличение дробной части квадрата коэффициента на t-м шаге.
Рис. 10
Обозначим (2-j-р/1)2“2(/“1)= Д£. Вычислим величину Л; при i=п1%-|-2:
Ли/2+2 = (2 + р„/2+1)2-2<«/2+2-1).
Поскольку рл/24-2< 1, то Дп/2-|-2<^0,75-2“л. Следовательно, уже на (п/2ф-2)-м шаге приращение величины меньше единицы младшего разряда. Расчеты показывают, что приращение коэффициента Кп/ги составляет менее 0,3 единицы младшего разряда. Отсюда следует, что коэффициент деформации вектора может быть рассчитан по формуле (2.33) при кт&х=п либо при ктах=.п/2+1. Получающаяся при этом разность выходит за пределы разрядной сетки. Например, при и=24 получены следующие числа: К1з = 1,64676023; Л24== 1,64676025. Ошибка не превышает половины единицы младшего разряда (2-24= = 0,596-10-7)
Рассмотрим погрешности вычисления функции arctg( Y/X). В предположении независимости инструментальной (2.21) и методической (2.22) погрешностей этапа I получим
°век I = ^еК.и02 + (0век.м)2 = У' 2~2Г + 4г
(2.34)
. Определим трансформированную погрешность этапа II. Возможны девять вариантов .сочетания величин погрешностей авек. I и авек.и/?’ из которых варианты с^ек , = 0 не дают трансформированной погрешности; Остальные шесть вариантов показаны на рис. 10. Поскольку каждый из вариантов равновероятен (Р=1/9), тс математическое ожйдание noiрешности равно нулю. Из треугольников (рис. 10) определим дисперсию трансформированной погрешности
Г/	св \2 /	ов \2
^ек. , - (2/9) arctg"- + arctg -	---- +
У	К Л /	\	+ век. и Д )
При значении /?^0,5 (что достигается либо масштабированием, либо нормализацией) величина а®ек R пренебрежимо мала. Взяв первый член разложения в ряд функции arctg х и преобразуя (2.35), запишем с точностью не менее 1%:
св
Пвек.т=(2/3)-^.	(2.36)
Подставив в (2.36) выражение для авек 1 из (2.34) и преобразуя, получим
, = ЯГI I" 2	  2-.
Средгеквадратическая погрешность суммирования п округленных констант определится по формуле (2:9)
ав =1^=2-«
век. кон
Считая погрешности этапа II вычисления функции arctg (У/Х) независимыми, получим
„в Al f 8 (» —2-г)2~21 -4 п- 2_п
°век? arctg J/ 9	№	• 12
На оис. 11 графически представлена зависимость погрешности вычисления функции arctg (У/Х) от разрядности представления чисел п и от числа дополнительных разрядов г. Из графиков следует, что введение более двух-трех дополнительных разрядов в регистры — нецелесообразно.
Рис. 12
При операции «вектор» трансформированная погрешность исходных данных для функции arctg (У/Х) опоеделяется аналогично рассмотренной выше трансформированной погрешности этапа II. Разница состоит в том, что первоначальный угол берется равным 45°. Возможные варианты сочетания значений погрешностей стИсх и (Тису показаны на рис. 12. Дисперсия погрешности
о,.= (2/9)[( arctg^S^-) + (aretg-^-)S+
+1 arctg
+ о2
I X г ИС у
KR
Преобразуя данное выражение, запишем величину среднеквадратической погрешности при 7? = 0,5
<з с == ——— 1/а2	4- а2
Т. ИС	Г ИС X 1 ИС у
Для величины модуля вектора трансформированная погрешность равна
ат ис 7?	—I—' о4
I. иг д у ИС X I ИС у
Погрешности вычисления функций arcsin( У//?) и arccos(X//?) определяются аналогично соответствующим погрешностям вычисления функции arctg (У/Х) -с учетом «двойных» итерационных шагов:
_	1 Л 8 2(« -2 — г)2-2г + 4 , п 2_п
oarcsln —’ Oarccos	I/ 9 '	№	' 6 ' '
Рекуррентные соотношения вычисления функции In Х‘.
yz+I = yz— ^2-%,
этап I хг+^^ + ^2-%, sign = sign yh этап II 0j+i — 6Z + In(l -f- £г2_/)-Погрешности этапа I: методическая погрешность усечения итерационного процесса определяется по формуле (2.18)
4 м = (1/ГЗ)2-«;
инструментальная погрешность из-за сдвигов вправо на i разрядов определяется по формуле (2.21)
в - 2-п/2 <и-2~г)2-»
°1П И . ”	I/	J
Общая погрешность этапа I составит
4 / = V2{п- 2-г>> 2-^ + 4-2-".
го	о
Погрешности этапа II. Поскольку целью этапа I является сведение аргумента функции 1пх к единице, то. трансформированная погрешность определяется из-соотношения
4т = Ш (1 + 4 /) ~ lnd) = а,в , _ (1/2)(ов /)2 + ... .
Ввиду малости величины а^п/ всеми членами разложения в ряд функции 1п(1+а® 7), кроме первого, можно пренебречь. Следовательно, 4т^4г Инструментальная погрешность суммирования 2п округленных констант определяется по формуле (2.9)
ов _____ У^п п—п
ш кон 2/3
Общая приборная погрешность вычисления функции 1пх равна
ав =1/(ав УЧ-(ав У = 1/2(” /I—2~2г4- 4- + 4-2~п’
In * V In Т' \ Jn КОН/ У 3	*	3 ~ 6
Трансформированная погрешность исходных данных определяется аналогично погрешности сфп т
°Б 1 == о, ИС 111	’
2.4.	АНАЛИЗ ПОГРЕШНОСТЕЙ СПОСОБА МЕДЖИТА
Существенной особенностью способа Меджита, позволившей повысить точность вычисления элементарных функций по методу «цифра за цифрой», является разбиение итерационного процесса на два последовательно выполняемых этапа. Это дает возможность при проведении этапа II начинать вычислительную процедуру с младших разрядов операндов, что значительно повышает точность результатов. Кроме этого, при выполнении I или II этапов по способу Меджита используются нормализованные константы, имеющие по сравнению с ненормализованными существенно меньшие относительные погрешности. '
Рассмотрим погрешности способа Меджита при выполнении операции «поворот». Рекуррентные соотношения для проведения вычислений:
e/+1 = 2(ez-^‘arctg2~9, sign Ег = sign ez,
ZZ_1 = 2-1(zi — Zi-iXt),
этап II	v ‘
x^i = xt + ki-i2-2^-^Zi.
этап
(2.37)
(2.38)
I
Погрешности этапа I (буква M в верхнем индексе здесь и далее означает: по Меджиту):
методическая погрешность усечения итерационного процесса—
инструментальная погрешность алгебраического суммирования констант— °”кон-
Погрешности этапа II:
трансформированная погрешность этапа I — о” т;
инструментальная погрешность вследствие сдвигов вправо на 2i разрядов — а^;
трансформированная погрешность— °^тг;
инструментальная погрешность из-за сдвигов на один разряд вправо — а” и.
Выражение методической погрешности о”м совпадает с соответствующей формулой, полученной в разделе 2.2 для способа Волдера (2.5):
-	= (2/|ЛЗ)2-«.
Оценим инструментальную погрешность алгебраического суммирования п округленных .констант. Поскольку погрешность
округления константы составляет l/(°}/3)-2“" и после каждого цикла результат сдвигается влево на один разряд (2.37), то, предположив независимость погрешностей на каждом шаге, можно записать
ом в 2-Л-1/ (/7 ’ . 2у+	2Y+ ... + f ’ у.
(2.39)
Преобразуя выражение (2.39), получим °”он = (1/6)2«+1-2-«.
Так как на каждом шаге вычислений величина 6, сдвигалась на один разряд влево, то,' следовательно, получившийся результат в 2” раз больше истинного остатка и соответственно погрешность также в 2П раз больше погрешности о^кон-Учитывая это, получим
^koH = (V3)-2-«.	(2.40)
Общая погрешность первого этапа составит
=l/w«)2 + (^«j2 = (VTW-“-
Погрешности этапа II. Погрешность, трансформированная из этапа I, может быть рассчитана в предположении, что величина радиуса вектора равна единице, а аргумент функции составляет 45°. В этом случае
т = (®2)	= flS26/6)2-".
Оценим инструментальную погрешность из-за сдвигов вправо на 2i разрядов. Математическое ожидание погрешности равно нулю, что следует из рассмотрения выражений (2.37) и (2.38). Дисперсия погрешности на (i+l)-M шаге
. Г1М — I 9—4/	2 V 22г-1 А2 |9-2л____ 1 —2 2/ 9—2/1
(2.41)
где 1/(22<+1—1)—вероятность появления любой комбинации единиц и нулей в разрядах остатка; (22i—1) — максимальная величина остатка в единицах младшего разряда; 2-4i — квадрат масштабного коэффициента.	/
Суммарная дисперсия за п/2 шагов (поскольку при i>n/2 все число 2~2iZt выйдет за пределы разрядной сетки вправо) составит
ЛМ ______ 5CW/2 1	2	о—2п  	8 9—2/1
и /	3	—	18 z •
Поскольку величина х0 представляет собой косинус заданного аргумента, то
ом = ^3w~~ 8 о—
'	cos 3 V2
Рассмотрим, как трансформируется погрешность в погрешность °”TZ. После каждого цикла алгебраического сложения происходит сдвиг вправо на одгщ разряд. Запишем выражение погрешности °^тг в предположении независимости погрешностей учитывая, что i принимает значения от п/2 до нуля:
°” т г = V '.4Г(«л/2-2-Т+1^-2)2+ ... + 4'	(2.42)
Из выражения (2.41) следует, что
Оп Ж = 1/2-	(2.43)
"	О
Подставив (2.43) в (2.42), получим
= (1/6)2-
Дисперсия инструментальной погрешности из-за сдвигов вправо на один разряд составит
; = 2~2Z(l/2) SLo^2"2” = С2-2‘-’)2-2".
Суммарная дисперсия за п шагов составит
Dn. И = (Zto2-2'-1)2"2" = (2/3)2-2п.
Средпсквадратическая погрешность
о”и = ]<273 2-	(2.44)
Общая погрешность вычисления функции sin <р составит
°" = ^(°”т)2 + КМтг)2 + (%Ми)2= 0/ЭД2-
Представим рекуррентные соотношения для вычисления функции ехр хг -
этап I еЖ = 2[ег-2Чп (1 + ^27')], sign — sign 6г,
этап II Xi-i = 2~1(xi-[-ti-i2-<l-1>xi).
Погрешности этапа I:
методическая погрешность усечения итерационного процесса определяется по формуле (2.18):
о”м = (1/1/3)2-«,
инструментальная погрешность суммирования констант определяется по формуле (2.40) с учетом «двойных» шагов:
 о”кон = (/2/3)2-«.
Общая погрешность этапа I равна
°* = /Кмм)2 + (°емкон)2= (/5/3)2-".
Погрешности этапа II:
трансформированная погрешность из этапа I
оемт=(/5/3)2-«;
инструментальная погрешность вследствие сдвигов на i разрядов вправо определяется по формуле (2.13)
’’ семи г = /(2/3)(1-2-92-;
трансформированная погрешность а^тг определяется по формуле (2.42) с помощью подстановки величины а^и .
оемтг = (2/2/3)2-«;
инструментальная погрешность за счет сдвигов на один разряд вправо определяется по формуле (2.44)
с” = У2ГЗ -2-".
Общая приборная погрешность вычисления функции ехр л: составит
°” = /(°”)2 + (°еМтг)2 + Ю2 = (/19/3)2-".
Рассмотрим погрешности выполнения операции «вектор». Соответствующие рекуррентные соотношения.
zi+i = 2(^ — ^xt),
этап I xi+i =хг4-2-2/|г£|, sign = sign zb
этап II 6z_i	arctgг-^-1*).
Погрешности этапа I:
методическая погрешность усечения итерационного процесса
__см •
век. м’
 инструментальная погрешность из-за сдвигов на 2 г разрядов вправо—о«киг;
трансформированная погрешность— a^KTZ.
Погрешности этапа II:
трансформированная погрешность этапа I— о^к т;
инструментальная погрешность суммирования констант — — ам .
век. кон’
инструментальная погрешность вследствие сдвигов на один разряд вправо — а^ек и.
Методическая погрешность определяется но формуле (2.5): овМек.м = (2/КЗ)2-\
Инструментальная погрешность из-за сдвигов вправо на 21 разрядов имеет систематическую и случайную составляющие. Математическое ожидание погрешности вна (i-|-l)-M шаге определяется как
= (2й-1—2-»)2-2/2-л.
Поскольку на каждом шаге величина Z{ сдвигается вправо на 21 разрядов, то, следовательно, суммарное математическое ожидание погрешности за s — n/2-\-l шагов будет
= ((3«-8)/12)2-«.
Запишем выражение дисперсии инструментальной погрешности на (i-|-l)-M шаге
£>иМ;+1 = [2-^2-2^Хо“- (22/_1 ~	(2.45)
Преобразуя (2.45), получим
£)М.+1 — (1 /3)(2-2 - 2-2(2z+D)2-2«.
Отсюда
0«ж = у (1/3)(2-2 —2-2(и+й)2-п.
Погрешность вычисления модуля вектора составит
ам п — 1/Х* 7)М	— П ~6 2~п
Овек. к — V 2л=оии г-н — 2 Уб 
При этом, как и ранее в (2.32), трансформацией методической погрешности в погрешность вычисления модуля вектора можно пренебречь.
Рассмотрим трансформацию погрешности °”/+1 в погрешность оМк т z при алгебраическом сложении и сдвиге на один разряд влево на первых ‘s шагах. Считая независимыми погрешности каждого шага, запишем
°” п/2 =	2)2 + (о«2Р  2)2 + ... + (оМ„,2)2: (2.46)
Преобразуя (2.46), получим
ctmz„/2=[.2«/2-/(2/3)]2~«.
При i>n/2 величина 'о^1 = const, поэтому аналогично (2.46) получим, что погрешность за вторые п/2 шагов составит
«тМгп/2= [(1/3)2"] 2-«.
Однако поскольку величина представляет собой псевдо-ост атои. сдвинутый влево на п разрядов, то погрешность истинного псевдоостатка определится:
ОвМек. тг = (1/3)2-".
Общая погрешность этапа I равна
	»"«' =	+	= (И3/3)2-.
Погрешности этапа II:
трансформированная погрешность этапа I, определяемая по формуле (2.36):
и
погрешность суммирования констант, определяемая по формуле (2.42) с помощью подстановки сГкон=[1/(2	3)]2~п:
дм = 11/3)2“"; , погрешность от сдвигов на один разряд вправо, определяе-мая по формуле (2.44):
®век. и = Г~2/3 • 2~"
Общая приборная погрешность вычисления функции arctg(y/Aj равна
arete —	)2 (оМ )2 + (аМ Г«4,50- 2~".
век. arcig у \ век т/ | \ век< кон' I V век. и' ’
Рассмотрим погрешности вычисления функции In х, рекуррентные соотношения которой
zf+i = 2(zz-^xz), этап I х/+1 = лг4-^2-%, sign = sign zh .
этап п ez_i = г-’^+г'-1 in (i + ^г-^-1»)].
Погрешности этапа I:
методическая погрешность, определяемая по формуле (2.18):
°ым = (1/ГЗ)2-";
инструментальная погрешность, за счет сдвигов на i разрядов вправо, определяемая по формуле (2.13): ..
«Ы и/ = У (2/3) (1-2-9 -2-";
трансформированная погрешность °^тг, определяемая с помощью подстановки величины о” й . в формулу (2.39):
м
,	|птг~з^7 •
'Общая погрешность этапа I составит
о™ / = К(оГ )2+(аГ' )2=-^2-л.
,П 1 г \ 1ПМ ! 1 х In Т Z' 3 V 7
Погрешности этапа II:
трансформированная погрешность этапа I
°1п т — г~ 4	'
о у /
инструментальная погрешность суммирования констант,, определяемая по формуле (2.40):
оы кои = (К2/3)2-«;
инструментальная погрешность за счет сдвигов на один разряд вправо, определяемая по формуле (2.44):
^„ = /2/3-2-".
В предположении независимости всех составляющих общая погрешность вычисления функции In х составит
°ы = /(оГ1 )2+(о.м )2+(б,м )2	1,16 • 2~«.
Выражения для погрешностей трансформации исходных данных для всех элементарных функций, вычисляемых по способу Меджита, аналогичны соответствующим выражениям, приведенным в двух предыдущих параграфах при анализе точности способа Волдера.
В табл. 2 представлены приборные погрешности элементарных функций, вычисляемых по способам Волдера и Меджита.
Сопоставление по точности двух способов реализации метода «цифра за цифрой»— по Волдеру и Меджиту — позволяет отметить следующее:
величины погрешностей способа Меджита меньше .соответствующих погрешностей способа Волдера;
относительные погрешности (выраженные в единицах младшего разряда) способа Меджита для большинства элементарных функций не зависят от разрядности представления чисел;
относительные погрешности способа Волдера возрастают с увеличением разрядности;
при реализации способа Меджита наибольший удельный вес имеют методические цргрешности усечения итерационного процесса;
при реализации способа Волдера превалируют инструментальные погрешности за счет сдвигов вправо.
. Таблица 2		
	Формула вычисления	
Функция	г^О	г=0
	Погрешности способа Волдера	
Sin ср COS <Р		/3" 9-л 2/2
ехр х	|/2W27~2) 2~*+^-4 2-	V 6«~4 9-п 2/Т	•
УХ2+У2	(1/6)У 3(и/2+1—г)—4-2 “("+г)	У 1,5л— 1 9-л 6
arctg (У/Х)	|/	2~2г+4 п V 9	Д'И	+12	/5п+8 2/"Г
arcsin (У/7?) .arccos (XIR)	т/8_ 2 (n-2-r) 2~2Ч4 п ’ 9	/<а	+ 6 2	Т7 10и 9-л 2/“Г
In X	У	2-442-	/ 10»—12 21ГЗ"
V X	1/2 2(^2) 2_г, 2_, г о	о	
	Погрешности способа Меджита	
.sin ср	1,19-2“”	
COS ср	3/2 8 о— п 3 /"2	
ехр х	1,45-2“”	
/х2+ У2 \	Уп~е г-п 2/6	
arctg (У/Х)	1,50-2“”	
In X	1,16-2“”	
2.5. ПОГРЕШНОСТИ ВЫЧИСЛЕНИЯ ЭЛЕМЕНТАРНЫХ ФУНКЦИЙ С ПОМОЩЬЮ ПОЛИНОМИАЛЬНОЙ АППРОКСИМАЦИИ
Рассмотрим погрешности вычисления элементарных функций с помощью степенных полиномов. Основными источниками погрешностей являются: методическая погрешность полиномиальной аппроксимации [24], инструментальные и трансформированные погрешности, обусловленные потерей точности при сложении, умножении и округлении.
инструментальные погрешности, возникающие непосредственно в процессе самих вычислений, зависят от способа выполнения .арифметических операций и правила округления результатов операций. При вычислении элементарных функций указанные погрешности/а также погрешности аргумента функции и коэффициентов полинома, обусловленные конечной разрядностью машины, трансформируются в погрешность результата. Поэтому анализ этих погрешностей (названных вычислительной погрешностью) целесообразно проводить’ совместно.
Вычисление степенных полиномов обычно осуществляется по •схеме Горнера:
f(x) = atxl = (...(amx ф~ ат^)х ф- ... ф- а^х ф- а0. (2.47) Обозначим адлф-а/-1 =<рк(х). Как было установлено выше, .в процессе вычислений участвуют три источника погрешностей. В предположении их независимости запишем выражение для полной среднек1вадратической погрешности функции f(x) [66]:
ч Г 2 . Vm (V-}2 2 1 V” ( df У 2 °/=|/ v*/ -°*+2^=0^;
(2.48)
где Qx— погрешность аргумента функции; cOr—погрешность R-ro коэффициента полинома; о Vr—погрешность вычисления выражения <pR(x).
Из выражения (2.47) следует, что = xR, = xR. По-oaR	°}R
грешность Сад=са = 0,29 • 2-п, так как это обычная погрешность округления константы [13].
Погрешность о Vr обусловлена инструментальной погрешностью операции умножения и постоянна для любого 7?, т. е.
•О <р —'Оумн-
к
Учитывая это, подставим . соответствующие выражения в (2.48). После преобразований получим (первый тип функций)	_____________________________
. f	2 . 1—Х2т+2 . 2.2,	,о ЛСЛ
°/1 = У	°* ф--+ Оумн).	(2.49)
Для четных функций tz;=O при /=2#ф-1 (7? = 0, 1, 2,	, т/2)
(второй тип функций)
(тУ °- +	(°- + °у™)-	(2-5°)
Для нечетных функция щ=0 при /=2/? (третий тип функций)
_	1	2 I X2 —Х2га+4 2 |	2 ~	/О ЧП
°/3 — У [fa) х + 1-х^—(2-51)
Проанализируем формулы (2.49), (2 50), (2.51). Из выражений, находящихся под корнем, наибольший интерес представляет дробь, стоящая перед суммой (°а + °уМН)- Величина этой дроби, а следовательно и погрешность результата, зависят от значения аргумента функции.
Для первого и третьего типов исследуемых элементарных функций выполняется условие =С2,. для второго типа функций выполняется условие ^1.
При стремлении	величины х к нулю выражения (2.49),
(2.5Q) и (2 51) с учетом этого запишутся соответственно: '
=	°умиГ4х2-Н1+°>у,	(2.52)
а/2 =	Оуми К-'-2 + (1 + °«/оуЫИ).	(2.53)
°/з==2<зЛ.,	(2.54)
ГДе" Я — (Тх/Сумн-
Анализ этих выражений при стремлении величины х к единице приводит к необходимости раскрытия неопределенности вида 0/0. После преобразований получим
<71 = °уми К4 + (тп + 1)(1 + о|/ар,	(2.55)
«/2 - оумя Кх2 + (/п/2+1)(1+о^мн),	(2.56)
<7з = оумн V 4х2 -«-((/и - 1)/2 + 1)(1 + °>2.ми).	(2.57)
Сопоставление выражений (2.52), (2.53), (2.54), (2.55), (2.56) и (2.57) показывает, что значение погрешности существенно зависит от величины аргумента функции. Поскольку предельные значения аргумента («0» или «1») маловероятны, то более достоверными являются интегральные оценки, усреднен-, ные по промежутку изменения’аргумента.
Запишем интегралы от выражений, стоящих перед суммами в (2-49), (2.50), (2.51). После преобразований fl 1 _ *.2m+2
Л в	dx ~ (1/2)[0,577 4- In (тп + 1) + 2 In 2],
Pl i 2т| 4
4 = Jo i-x* dxf^8'+ (1/2)[(1/2)(0,577 + In (т + 1)+2In 2)], 4== J0£-i=^F_6/x’te(1/2)l(1/2)(°,577 + ln И + n 4-2 In 2)]-ic/8.
На рис. 13 графически представлены все три зависимости. Так как практически всегда выполняется условие т<20, то усред-получаем
ленные оценки среднеквадратических погрешностей могут быть записаны следующим образом:
f	°умн
°/2 °умн
К4^ + 2Л1+°2Лмн)> 1/*2+1>5(1+сХмн)’ jA4z2 + (1+..02^2MJ,
(2.58)
(2.59)
(2.60)
отметить, что
(2.58), (2.59) и
Надо формулы (2.60) справедливы для оценок погрешностей вычисления по схеме Горнера любого степенного полинома — полинома Чебышева, отрезка ряда Тейлора и т. д.
При выборе конкретных способов умножения величина погрешности Нунн является определенным числом.. Проанализируем погрешности выполнения различных способов операции умножения.
Применяемые в настоящее время способы выполнения операции умножения с точки зрения анализа погрешностей можно
разбить на две группы: класси-
ческие методы, при которых все промежуточные действия проводятся с 2н-разрядными операндами, а округление произво-
дится в конце операции умножения; итерационные методы, при
которых разрядность операнда изменяется в процессе выполнения от 1 до п разрядов.
Инструментальная погрешность первой группы способов равна 0,29-2-п, поскольку это обычная погрешность округления
Более слож'ной является оценка погрешностей второй группы способов выполнения умножения. В то же время эти способы из-за большего быстродействия и меньших аппаратуцных затрат в ряде случаев .являются предпочтительными [30].
Округление при выполнении умножения по этим способам может осуществляться одним из трех методов: отбрасыванием младших разрядов; округлением после получения "окончатель
ного результата; округлением на каждом шаге образования частичного произведения. Округление при двух последних методах осуществляется путем добавления единицы в n-й разряд, если разрядная цифра («+1)-го разряда равна единице (симметричное округление).
Рассмотрим сначала погрешность при первом и втором методах округления. Математическое ожидание погрешности на i-м шаге при первом методе округления составит
Ма = (2-' • Л. 4- У 2*4 2-" = (2~2 - 2 -<г+2>) • 2-", \	2‘	2	л=1 J
(2.61)
где 2-i — коэффициент приведения погрешности к единице младшего разряда; 1/2®— вероятность появления любой комбинации единиц и нулей остатка; 1/2 — вероятность появления единицы в i-м разряде множителя; (2®—1) —максимальная величина погрешности.
Дисперсия погрешности на i-м шаге определится как
Da = 2-2г • 4- • - 4 У 2‘-1 {k — 2-2 4 2-(Н 2) )3 • 2“2п.	(2.62)
Дисперсия погрешности результата с точностью не менее 1,5% равна
n„i = SLina^(«/6)-2-2«.
Среднеквадратическая погрешность составит
°уМН1~К^7б-2-'!.	(2.63)
Определим математическое ожидание погрешности на последнем (n-м) шаге
Мл = SLj/Иц = ((« - 1 )/4) • 2~*.	(2.64)
При округлении по первому методу погрешность1 состоит из двух компонент: систематической, определяемой выражением (2.64); случайной, определяемой выражением (2.63). При использовании второго метода к окончательному результату прибавляется величина Мп1, компенсирующая систематическую составляющую погрешности.
Определим погрешность при умножении с округлением на каждом шаге. Математическое ожидание погрешности равно нулю. Дисперсия погрешности на i-м шаге
I 9	1 "VI i'-1-!	\	2-24-2-<z+2)
D = 2-2z-4-4-7j	Л2)-2-2п = —--4-------2-2«.
12	\ 2Z 2	. 6
Дисперсия погрешности результата с точностью не менее 1,5%
Dn2 =	= (1 /24) (п - 1) • 2~2«.
Среднеквадратическая погрешность определится: ' °УМн2 = 1<(«-1)/24-2-«.
Суммарная погрешность операции умножения составит cVMH с = |/а2	-I- а2 , 	(2.65)
умн. С Г умн. Т 1 умн. И»	Х  >
где сгумн-и — инструментальная погрешность операции умноже-ния; Оумн. т — трансформированная погрешность [13, 37].
Рис. 14
В случае если вычисленная величина погрешности (2.65) превышает заданную, необходимо увеличить число разрядов регистров. Допустим, что к регистрам добавлено г дополнительных разрядов. В этом случае выражения для математического ожидания и дисперсии погрешности операции умножения на i-м шаге запишутся аналогично формулам (2.61) и (2.62):
Dilr = 2~2'	2‘~г~г (k — 2~(г+2) + 2-<z+2>)22-2n.
На последнем шаге операции получим
<1, = 2?=г+1УИ/1г^(1/4)(«-г-1)2-(п+б	(2.66)
Dnlr = 2Ь+1Ог1г^(1/6)(/г - г)2-2("+п.
Среднеквадратическая погрешность °yMHlr^K(«-r)/6-2-<«+n	.	(2.67)
Для варианта выполнения умножения с округлением на каждом щаге дисперсия и среднеквадратическое значение погрешности запишутся соответственно:
Dn а г ъ (1/24) {ti - г — 1) 2~2(«+И,
Оумнаг^К (« —г - 1)/24-2-(«+г).	(2.68)
Здесь, как и в предыдущих случаях, замена в выражениях (2.66), (2.67), (2.68) точного равенства приближенным дает максимальную относительную погрешность, не превышающую 1,5%. Полученные зависимости графически представлены на рис. 14.
Используем полученные выражения для оценок погрешностей операции умножения в формулах погрешностей вычисления степенных полиномов. При умножении младшими разрядами вперед (классические методы) <Тумн=<то=0,29-2~п. Примем, что о,:с=|+,т- е. к=1. Тогда выражения (2.58), (2.59) и (2.60) перепишутся:
ад <6,29УТ+5 • 2~" = 0,87• 2~я,	(2.69)
о/2 < 0,29 ]Л 1 4-ЗД • 2-« = 0,61 -2-«,	(2.70)
а)з<0,29|/4 + 2 -2-» = 0,71-2-”.	-	(2 71)
В случае умножения со старших разрядов множителя (итерационные методы) в соответствии с формулой (2.63) получим ^д <	‘ |/2,5 + 3,25/п • 2-«,	(2.72)
0/2 <	 V 1,75+ 1,37/п • 2-«,	(2.73)
0/з<Г+6-]/ 1 +2,5/«  2-«.	(2.74)
Остановимся на соотношении методических и инструментальных погрешностей полиномиальной аппроксимации. Степень аппроксимирующего полинома целесообразно выбирать по условию выполнения неравенства
°м < °д/3,	(2.75)
где ом — методическая погрешность конечного числа членов полинома; Ом=Ам/]/' 3 [13].
В табл. 3 в соответствии с* [24] приведены методические погрешности ряда элементарных функций для различного числа членов аппроксимирующих полиномов. Табл. 4 построена в соответствии с формулами (2.69) — (2.74) для различных разрядностей п. В ней представлены вычислительные погрешности полиномов (ст/г/3) при двух способах выполнения операции
Таблица 3
Функция	Число членов полинома								
	3	4	5	6	7	8	9	10	11
sin (-/2) х	6,35-10“®	6,35-10“7	3,18- 10 я	4,75-10-12					
arctg х	4,05-10“4	4,6-10“5	6,9-10-6	1,04-10~6	1,44-10“7	2,3-10“8	5,1-10“9	9,1 -1О"10	2,2-10“10
in X	3,15-10“4	4,35 -10“5	5,8-10“6	8,7-10~7	1,27-10“7	1,85-10-8	4,8-10“9	5,6-10“10	1,4-Ю“10
ехр х	5,2-10“3	5,2-10“4	4,3 -10“®	3,1 -IO'6	1,94-Ю-7	1,08-10“8	5,35-КГ10	2,45-10~п	1,02-10“12
Таблица 4
Функция		Разрядность (и)								
		16	15	' 20	25	30	35'	40	45	50
sin ,(л/2) х,	Мл.	2,3-10“4	7,1-10“6	2,24-10“7	6,85-10“9	2,18-10“10	6,85-10“12	2,12-10“13	6,6-10“16	2,08-10“16
arctg х	Ст.	4,65-10“4	1,7-10“®	6,1-10“7	2,02-10“8	8,05-10“10	2,35-10“п	7,9-10“13	2,64-10' 14	8,65-10“16
In X,	Мл.	2,82-10“4	8,6-10“6	2,76-10“7	8,4-10“9	2,7 10“10	8,4-10“12	2,62-10“13	8,1-10“14	2,56-10“16
ехр х	Ст.	7,0-10“4	7,з-1о ;5	9,4-10“7	3,16-10“8	1,12-10“9	3,6-10“п	1,25-10“12	4,1-10“14	1,35-10“15
умножения. Используя указанные таблицы, а также условие (2.75), можно построить графики, на которых изображаются зависимости mmm=f(«) для функций sin(n/2)x, arctgx, 1пх, ехрх, где ттт — минимально необходимое число членов полинома (рис. 15, 16. 17, 18), здесь мл.— умножение с младших разрядов множителя, ст.— умножение со старших разрядов множителя.
Число иленой полинома	членов полином
Графики зависимости минимально необходимого числа членов полинома от разрядности представления чисел в ЦВМ для ряда элементарных функций дают возможность оптимизировать соотношение двух основных характеристик качества вычислений: точности и быстродействия. Полученные результаты могут быть использованы не только при аппаратурной реализации, но и при вычисление элементарных функций программным способом.
ГЛАВА 3
ВОПРОСЫ СТРУКТУРНОЙ РЕАЛИЗАЦИИ ВЫЧИСЛИТЕЛЬНЫХ АЛГОРИТМОВ
3.1. РЕАЛИЗАЦИЯ МЕТОДА „ЦИФРА ЗА ЦИФРОЙ1*
Рассмотрение рекуррентных соотношений двух этапов вычисления элементарных функций по методу «цифра за цифрой» приводит к выводу о трех возможных, с точки зрения последовательности решения, способах их аппаратурной реализации. Рекуррентные соотношения представляют собой систему трех уравнений, из которых два уравнения одного этапа взаимосвязаны (т. е. в каждом из них на всех шагах используется результат другого), а третье уравнение связано с двумя первыми только односторонне (т. е. в нем в течение всего итерационного процесса используется результат первых двух уравнений этапа I, либо в противоположном случае два уравнения этапа II используют результат этапа I на протяжении всей вычислительной процедуры). Графически это представлено на рис. 19.
Возможны пять вариантов временных последовательностей реализации итерационных уравнений, которые на рис. 20 обозначены буквами а, б, в, г, д. Римские цифры соответствуют номерам этапов, арабские —номерам уравнений.
Реализацию двух этапов вычисления можно осуществить одним из трех способов: последовательной реализацией этапов с 'последовательным решением уравнений внутри этапа (рис. 20, а, г) ; последовательной реализацией этапов с параллельным решением уравнений внутри этапа (рис. 20, б, д); параллельной реализацией этапов—I и II (одновременным решением всех трех уравнений (рис. 20, в)).
Из рис. 20 следует, что последовательное выполнение двух этапов может осуществляться на двух различных уровнях: на уровне итерационных шагов (рис. 20, а, б); на уровне этапов (рис. 20, г, д). Первые три временные диаграммы соответствуют способу Волдера, последние две — способу Меджита.
С точки зрения обработки разрядов чисел в ЦВМ могут быть рассмотрены два метода: последовательная и параллельная обработка.
Таким образом, должны быть проанализированы десять вариантов реализации метода «цифра за цифрой». Каждый вариант различается Структурой операционного устройства, структурой блока микропрограммного управления, быстродействием и количеством оборудования.
В то же время общее требуемое число констант и погреш-
Но Бор констант
Аргумент функции
„ Прямые "функции
I этап
Ч этап
•I/ этап
Рис. 19
ности вычислении не зависят от варианта временной диаграммы работы, а являются функцией числа итерационных шагов. Поскольку итерационный процесс вычисления элементарной функции состоит из п шагов, и каждому шагу соответствует определенна# константа, то для каждой функции требуется п
III	I II П	II
111	1	Г~3
t 1, I	... , 1 I	1	|	_ ... t	_________ I I
и	2п	Зп t
I	II	II	II
I	I	I	2	2	2
,	111	13	3	3
' -	, I-1-1 -	„..	1 I I--	—, .ч	।_____________________к
п	2п	t
Рис. 20
констант. Для логарифмической и экспоненциальной функций требуется 2п констант. Общее число констант равно:
для прямых и обратных тригонометрических функций п констант arctg 2-i;
для прямых и обратных гиперболических функций п констант Arth 2-i;
для логарифмической и экспоненциальной функций п констант 1п(1-]-2~г) и п констант 1п(1—2-i)-
Для сокращения числа констант можно использовать тот факт, что вблизи нуля или единицы многие элементарные функции с большой точностью апдооксимируютс я линейной функцией.
Используем формулы разложения в ряд функций arctg х, Arthx, 1п(1±х).	•
Для функции arctg х при х=2_£, t^n/З получим
arctg 2_/ = 2~г	•	(3.1)
с погрешностью, не превышающей 2~п/3, т. е */» единицы ^младшего разряда представления чисел. Для функции Arthx при х=2_\ i^n/З получим
Arth 2-z = 2-1	(3.2)
с погрешностью, не большей 0,5 -2~п.
Для функции In(lzzx) при x=2-i, iZ^n/2 получим
1п(1 + 2-‘)=± 2-г	(3.3)
с погрешностью, не большей 0,6 -2~п.
При реализации по способу Волдера константы arctg 2~\ Arth-2-i и In(l±2-i) используются и записываются в ПЗУ машины непосредственно. При реализации по способу Меджита эти константы используются в нормализованном виде, т. е. 2iarctg2“\ 2zArtti2~z и 241п (1 ±2-*) •
Для оценки общего числа констант, требуемого для реализации по способу Меджита, умножим правые и левые части выражений (3.1), (3.2) и (3.3) на 2’. Анализ полученных выражений показывает, что в этом случае
2‘ arctg 2~‘ = 1
при t^n/2 с погрешностью, не превышающей 2-п/3;
2‘Arth 2~z = 1
при i^n/2 с погрешностью, не превышающей 2~п/2;
2l In (1 ± 2-') = ± 1
при
Таким образом, при реализации метода «цифра за цифрой» в памяти машины должны быть записаны не все требуемые константы, а только старшие, соответствующие небольшой величине индекса i. Младшие константы при переходе на новый шаг итерации могут быть образованы путем сдвига единицы на один разряд вправо.
Общее число констант для способов Волдера и Меджита представлено в табл. 5.
Таблица 5
Функции	Аппроксимация	Число констант:		
		без аппроксимации	с использованием аппроксимации	
			по способу Волдера	по способу Меджита
arctg 2-t	2~l	п	и/3	я/2
Arth 2“1	2~l	п	и/3	и/2
In (1 ±2“0	±2“z	2п	п	2п
При использовании знакопостоянных шагов итераций количество логарифмических констант сокращается вдвое.
Следует подчеркнуть, что использование линейной аппроксимации в данном случае не влечет за собой увеличения погрешности вычислений, поскольку образующаяся, методическая погрешность выходит за пределы разрядной сетки.
Пяти вариантам временных диаграмм реализации метода «цифра за цифрой» (см. рис. 20), как указывалось выше, соот-
Рис. 21
ветствуют десять разновидностей структур операционного устройства (ОУ) ЦВМ. Рекуррентные соотношения, полученные в гл. 1 для вычисления различных элементарных функций по Способам Волдера и Меджига, а также временные диаграммы работы служат основой для построения различных вариантов структур ОУ (рис. 21, 22). На рисунках следующие обозначения: Рг X, Рг У, Рг ПЗУ, Рга — соответственно регистры абсциссы, ординаты, ПЗУ и угла; БСД — блок сдвига кодов; X— су м м атор -в ычитател ь.
lib
56
Рис. 22

Отметим, что реализация «двойных» итерационных шагов в структурах ОУ, использующих способ Меджита, требует наличия либо двух регистров для запоминания операторов либо одного регистра удвоенной разрядности.
Определим быстродействие различных вариантов структур. Оценим вначале в общем виде время выполнения отдельных элементарных операций.
Время сдвига на один разряд равно /Сд=рТз, где т3 — время задержки на элемент.
Время последовательного суммирования составит тогда ^пос. с =ярТз, где п — разрядность ОУ.
Время параллельного суммирования равно г1 пар. с = ет3.
Рассмотрим быстродействие структур Волдера. Поскольку общее чис'ло итераций равно п, а константы сдвига изменяются от 2-1 до 2_("-i), то среднее время сдвига, приходящееся на одну итерацию, будет
Чд. ср = ((П~2п + 1)П Р тз = (»/2) р V
Обозначив буквенными индексами «а» и «б» соответственно последовательную и параллельную структуры ОУ, получим следующие значения времени выполнения (структуры la, 2a, 3a,. рис. 21):
la L Tla = nx3(np -L- np-\- (/z/2) p —np) = 3,5n2pi:3,	(3.4}
2a T3a — n x3(n p (»/2) p + n p) = 2,5 n? p %,	(3.5)
3a T3a — n x3(n p -f- (ft/2) p) = 1,5 ft2 p t3.	(3.6)
В случае последовательной арифметики с помощью соответствующих логических схем вместо пространственного сдвига может быть использован временной сдвиг, выполняемый одновременно с операцией алгебраического сложения. При этом в выражениях (3.4), (3.5) и (3.6) исключаются слагаемые (н/2)рт3 и они принимают следующий вид:
ЛО = 3п2РТз. Т'2а = 2П2рХ3, ТЗа = п2?Хз-
При использовании параллельного операционного устройства (см. рис. 21, структуры 16, 26, 36) время алгебраического сложения существенно сокращается, а время сдвига остается прежним, кроме того, может быть использован только пространственный сдвиг.
Значения времени выполнения составят соответственно:
16 T16=nt3(e4-e-|-(n/2)p + e) = Зп е х3 -ф (ft2/2) р т3,
26 7'2б:=»'гз(е+(«/2)р + е) = 2» е т3(п2/2) р т3,
36 Т36 == П т3(е (ft/2) р) = п е х3 -|~ (ft2/2) р т3.
Временные оценки реализации рекуррентных соотношений способа Меджита выводятся аналогично соответствующим оценкам для способа Волдера. Разница заключается в следующем. Во-первых, в рекуррентных соотношениях способа Меджита имеется сдвиг на один разряд (вправо или влево); во-вторых, при 1>п/2 величина Zj2~2i выходит за разрядную сетку, и сдвиги на 21 разрядов вправо (а следовательно, и суммирование Xi±2~2iZi) не производятся.  Среднее время сдвигов на 2i разрядов, приходящееся на п/2 шагов итераций, рацио
_(2(» —1)/2+2)(»/2)	_	'
Гад- ср —•	2и/2	Р ~3'—"' ' °
Время выполнения для различных вариантов последовательной структуры (рис. 22):
4а Т\а = «т3[(пр4-р)+(1/2)[(«р-|-р)4-(пр + р-]-пр+(п/2)р)]],
5а Лв=»'1з[(»р + р)+(1/2)[(пр + р)+(пр + р + (n/2)p)]J.
Для параллельной структуры время выполнения для вариантов 46 и 56:
46 Л б = п т3[(е + р)+(1/2) [(е + р)+(е + в + р +(п/2) р)]],
56 Т56 = пт3[(е + р)+(1/2)[(е + р)+(е + р + (п/2) р)]].
Для последовательных структур при использовании временного сдвига получим соответственно:
„ T'ia = 2>5ft2 р тз> Т'о = 2,0-«2рт3.
Сокращение времени при этом происходит за счет того, что составляющие 0,25п2рт3 (время сдвига на 21 разрядов) и 2 гфт3 (время сдвига на один разряд) исключаются.
Рассмотрим в качестве примера два варианта структурной схемы ОУ, получившие достаточно широкое распространение на практике: схему с одноразрядным комбинационным сумматором и схему с параллельным сумматором со сквозным переносом. В этом случае численные выражения коэффициентов будут: р = 3, Е = П.
Подставив эти величины в соответствующие выражения, получим
Т1а= 10,5п2 г3,	7\ а - (8,25а2 4- 5п) г3,
Ла = 7,5п2т3,	7'&а = (6,75п2 + 6п)т3,
^з« = 4,5п2т3,
7;а = 9пЧ, Г;с = 7,5п2т3)
Л б = w г3, Ti б = (3,25п2 + 6п) т3, Т2б = 3,5/гЧ, . Т56 = (2,75п24-6п)?3. 7’зб = 2,5я2т3,
На рис. 23 и 24 указанные зависимости представлены графически.
Анализ полученных в общем виде зависимостей времени реализации рекуррентных соотношений позволяет сделать выводы о том, что наибольший удельный вес занимает время выполнения сдвигов на переменное число разрядов, поэтому уменьшение этого времени либо путем сдвигов сразу на 2i разрядов,
либо путем применения временного сдвига позволяет значительно повысить быстродействие. В связи с этим можно сделать следующие выводы:
параллельная структура при реализации способа Волдера невыгодна, тдк как она дает лишь незначительное увеличение быстродействия по сравнению с последовательной структурой;
Рис. 24
параллельная структура при реализации способа Меджита дает значительное увеличение быстродействия;
реализация временного сдвига с помощью логических схем при способе Волдера выгоднее, чем при способе Меджита, так как дает более ощутимое увеличение быстродействия;
соответствующие структуры, использующие способ Меджита,. обладают большим быстродействием, чем структуры, работающие по способу Волдера;
наибольшим быстродействием обладают структуры, реализующие способ Волдера с параллельным решением всех трех рекуррентных соотношений.
Все приведенные выше формулы для оценки быстродействия предполагали синхронный способ организации итерационного вычислительного процесса. При этом каждая функция вычисляется' за п итерационных шагов независимо от величины аргумента. В работе [49] предлагается асинхронный принцип вычисления при реализации функций 1пх, ехрх и ]Лх.
Суть его состоит в том, что номер начального шага выбирается в зависимости от величины разности (1—х). Чем меньше эта разность (больше нулей в старших разрядах разности), тем с большего номера начинается итерационный процесс. Кроме того, вычисления заканчиваются на (тг/2)-й итерации, а затем производится коррекция получившегося результата за счет линейной аппроксимации. В среднем метод дает выигрыш nt> быстродействию, но при этом несколько усложняются соответствующие' микропрограммы.
3.2. РЕАЛИЗАЦИЯ МЕТОДА БИНОМИАЛЬНОЙ АППРОКСИМАЦИИ
Полное время вычисления элементарной функции по методу полиномиальной аппроксимации делится на время непосредственного вычисления полинома и время, необходимое для сведения аргумента в более узкую область с целью ускорения сходимости полинома. При фиксированном’ значении аргумента функции и определенным образом заданных машинных параметрах должен существовать минимум общего времени вычисления элементарной функции, определяемый оптимальным сочетанием времени преобразования аргумента и времени вычисления полинома. Однако эта задача трудноразрешима, так как аргументы функций (меняются в широких пределах, и, кроме того, в задачу входит большое число неизвестных, определяемых параметрами машины.
При вычислении степенных полиномов переход от программной к аппаратурной реализации позволяет сократить только дополнительное время, т. е. сумму времени, требующегося для. приращения адреса команды, извлечения команд из памяти, декодирования кода операции, выработки адресов операндов, и выборки операндов из памяти. Время же, отводимое на не
посредственное вычисление полинома, практически остается неизменным.
Рассмотрим оценки быстродействия некоторых вариантов структур, реализующих элементарные функции с помощью метода полиномиальной аппроксимации. Поскольку анализ всего «спектра» разнообразных вариантов структур с учетом использования различных алгоритмов выполнения операции умножения, способов округления, а также схемной реализации цепей
а
 Рис. 25
сдвига и переноса представляется слишком громоздким, то в качестве иллюстрации остановимся только на одном варианте последовательной структуры и одном варианте параллельной структуры (рис. 25). Кроме того, при оценке времени реализации будей исходить из требования минимальных аппаратурных затрат.
В этом случае время выполнения операции умножения для двух рассматриваемых вариантов — а и б запишется соответственно
^уми. а == А? Р 'C3j	^умн. б == ^(р Н~ е)тз,
где смысл обозначений р и е такой же, как и в разделе 3.1.
Рис. 26	Рис. 27
Для принятых величин коэффициентов р и е (р = 3, е=п) запишем
^умн. а — Зм? Т3, ^умн- б — i-fl" “Ь Зл) Т3.
С помощью графиков минимально необходимого числа членов полинома (рис. 15, 16, 17, 18) определим зависимость времени. вычисления элементарных функций (7ЭЛ.ф) sin(jt/2)x, arctg х, 1пх, ехрх от разрядности представления чисел.
В общем виде эта зависимость при вычислении по схеме Горнера может быть записана как 7ЭЛ.ф = т(п) (^умн+^сл), где т(п)—минимально необходимое число членов полинома, ^уми, ten — время выполнения операций умножения и сложения..
Соответствующие графики для параллельного варианта выполнения вычислительного блока, иллюстрирующие рассматриваемые примеры, представлены на рис. 26, 27. Для последовательного варианта кривые только переместятся вверх, не меняя своего наклона, на величину [(logp) -10] сантиметров.
В табл. 6 на основании графиков (рис. 15, 16, 17, 18) представлено количество констант, требуемых для реализации элементарных функций с помощью метода полиномиальной аппроксимации для различной разрядности чисрл. В этой же таблице
Таблица 6
Функция
sin (л/2)х............
arctg х ..............
In х .............
ехр х.................
Всего.................
Общее количество констант
для метода ./„цифра за цифрой” . . .*.........
Разрядность						
10 1	15	20	25	30	35	40
3	4	4	5	6	7	8
3	5	7	9	11	13	15
3	5	6	8	 10	13	16
4	6	7	8	9	10	11
13 '	20	24	30	36	43	50
13	20	27	32	40	44	53
указано общее количество констант, требуемое при реализации метода «цифра за цифрой» для соответствующих функций. Можно убедиться в том, что требуемые затраты ПЗУ для двух рассматриваемых методов приблизительно одинаковы.
Рассмотрим сравнительные оценки указанных методов по двум другим параметрам: точности и быстродействию.
Анализируя формулы оценки погрешностей, представленные в табл. 2 и 4, можно прийти к выводу о том, что при фиксированной разрядности представления чисел среднеквадратические погрешности вычисления элементарных функций для способа Волдера и для полиномиальной аппроксимации при умножении со старших разрядов множителя, для способа Меджита и для полиномиальной аппроксимации при умножении с младших разрядов множителя приблизительно одинаковы.
Время вычисления элементарных функций при различных
численных методах существенно зависит от структуры операционного устройства. В разделе 3.1 были получены приближен-
ные аналитические зависимости времени вычисления для метода «цифра за цифрой», а в начале данного раздела — оценки времени реализации метода полиномиальной аппроксимации для двух вариантов структуры ОУ — последовательной и параллельной.
Анализ соответствующих формул и графиков для рассматриваемых примеров (см. рис. 23, 24 и рис. 26, 27) показывает принципиальное отличие зависимости времени реализации двух сравниваемых методов:
при методе «цифра за цифрой» крутизна кривых времени реализации при увеличении разрядности уменьшается (в полулогарифмическом масштабе);
при методе полиномиальной аппроксимации крутизна соответствующих кривых остается приблизительно постоянной :и большей, чем при методе «цифра за цифрой».
Таблица 7
Метод полиномиальной аппроксимации	Метод „цифра за цифрой*4:	
	способ Волдера	способ Меджита
тэл. ф=тп* Т3 *	Т'1а	тз Г2« =6«2 ^з 7зй — 3«г т3	ел- -	' Й Й 11	1! О	сл a w w
Объясняется это тем, что при использовании метода полиномиальной аппроксимации с увеличением разрядности ЦВМ. возрастает требуемое число членов полинома (т. е. требуемое число умножений и сложений) и увеличивается время выполнения (число циклов) операции умножения.
При использовании, метода «цифра за цифрой» с увеличением разрядности возрастает только число шагов итераций, т. е. число сложений и сдвигов, и,- следовательно, время реализации возрастает «линейно».
Значит, чем больше разрядность представления чисел, тем большим относительным быстродействием обладает итерационный метод «цифра за цифрой» по сравнению с методом полиномиальной аппроксимации.
Вопросы сравнительного анализа указанных методов с точки зрения аппаратурных затрат на реализацию ОУ, БМПУ будут подробно рассмотрены применительно к конкретной системе элементов в гл. 4. Здесь заметим только, что основной особенностью реализации метода «цифра за цифрой» является усложнение структуры ОУ по сравнению со структурой, реализующей метод полиномиальной аппроксимации. Сопоставляя между собой соответствующие варианты структур (см. рис. 21, 22 и рис. 25) можно заметить, что в выбранных примерах по числу сумматоров и регистров структуры, реализующие метод полиномиальной аппроксимации, более экономичны.
В связи с этим представляет интерес .сопоставление по бы-стродействию параллельной структуры рассматриваемого типа (см. рис. 25) и последовательных структур, реализующих метод «цифра за цифрой» для принятых вариантов схем сумматоров, регистров, цепей переноса и сдвига. В табл. 7 представлены выражения оценок времени реализации для различных структур.
Из табл. 7 видно, что при числе членов полинома т^.3 быстродействие метода полиномиальной» аппроксимации при приблизительно равных затратах оборудования не меньше быстродействия метода «цифра за цифрой». При числе членов полинома от трех до девяти все большее количество вариантов последовательных структур Волдера и Меджита превосходят по быстродействию традиционную структуру. Когда число членов полинома превышает девять, все варианты структур метода «цифра за цифрой» превосходят по быстродействию структуры, использующие метод полиномиальной аппроксимации.
ГЛАВА 4
НЕКОТОРЫЕ ЕСПЕССЫ EFGEKjИРСЕАЕИЯ ЦВМ С АППАРАТУРНОЙ РЕАЛИЗАЦИЕЙ ЭЛЕМЕНТАРНЫХ ФУНКЦИЙ
4.1. ВЫБОР ОСНОВНЫХ ПАРАМЕТРОВ
В предыдущих главах исследовался широкий круг вопросов,, связанных с теорией аппаратурной реализации вычисления элементарных функций по методу «цифра за цифрой» и по методу полиномиально’?! аппроксимации. Однако при определении конкретных параметров вычислительной машины с аппаратурной реализацией элементарных функций требуется рассмотрение дополнительного ряда вопросов. В частности, для специализированных ЦВМ необходимо наметить подход к.определению длины разрядной сетки машины в зависимости от заданной точности решения поставленных задач.
Для специализированных ЦВМ круг решаемых задач заранее ограничен. Это позволяет свести задачу анализа погрешностей к определению наименьшей возможной разрядности, обеспечивающей получение решения с приемлемой точностью. При этом основная проблема состоит в получении оценок погрешностей сложных формульных выражений с приемлемыми затратами времени. Для решения данной задачи можно использовать два подхода — аналитический и машинный.
Сущность первого подхода состоит в получении формул для оценки погрешностей операций, функций и вычислении общего выражения погрешности реализации всей формулы с учетом трансформации погрешностей. Преимуществом такого’ подхода является наглядность влияния каждой из составляющих погрешности на результирующую погрешность. К недостаткам его относятся приближенность результатов и большой объем ручных вычислений, что может быть сокращено при использовании графиков, таблиц, номограмм и т. п.
Второй подход заключается в статистическом моделировании алгоритма решения задачи на универсальной ЦВМ при выбранных формате данных, численном методе, способе выполнения арифметических операций и способе округления. При этом анализ погрешностей производится так же, как и при вычислении элементарных функций: сравнением с эталоном и последующей обработкой и оценкой достоверности результатов моделирования.
-Основной проблемой статистического моделирования сложных формульных выражений является сокращение времени
и требуемый объемов памяти при допустимых величинах доверительных интервалов для анализируемых параметров.' Необходимость анализа погрешностей реализации алгоритмов заставляет программно интерпретировать арифметические операции для различной длины разрядной сетки. Кроме того, в моделирующей программе необходимо иметь набор стандартных программ вычисления элементарных функций с методической погрешностью., оптимально соответствующей каждому фиксированному значению длины разрядной сеУки.
Значительное число переменных (4—6 и более) в алгоритмах решения задач заставляет анализировать большие массивы выходных результатов.
Несмотря на некоторую универсальность программы моделирования, каждый раз необходимо выполнять непосредственное программирование самого вычислительного алгоритма, проводить трансляцию, отладку и т. д., что требует дополнительного времени.
Сокращение времени и требуемых объемов памяти может быть осуществлено, во-первых, предварительным ориентировочным выбором разрядности с помощью аналитического подхода, во-вторых, за счет особых приемов моделирования.
Основным недостатком машинного подхода к оценке погрешностей с точки зрения анализа численных методов является прагматичность результатов, т. е. для фиксированного набора входных параметров оценки хотя и получаются достоверными, однако ни сравнительного влияния каждого из параметров, ни наглядности результатов непосредственно получить при этом не удается.
Рассмотрим содержание аналитического подхода к выбору длины разрядной сетки специализированной ЦВМ (СЦВМ), использующей способ Волдера, считая заданными алгоритмы решения и допустимую величину погрешности.
Вычисление в СЦВМ, использующей метод «цифра за цифрой», сложной тригонометрической формулы сводится к выполнению в определенной последовательности арифметических операций и операций «поворот» и «вектор». В литературе [64, 78] описана удобная форма представления вычислительного процесса при использовании метода «цифра за цифрой». Возьмем, к примеру, решение задачи определения дальности 5Сф и пеленга П на объект при известных географических координатах своего места (фс, А'с) и места объекта (фо, Ло) [4]. Для небольших расстояний задача решается по формулам
П = arctg
(Лс — Хо)  cos ((ус + <р0)/2) ?о —?с
\ф = К(?0 — Фс)2 + (Хс — Ч2 COS2((<pc + <f>0)/2).
Схема вычислительного процесса представлена на рис. 28. На этой схеме буквами X, Y, ср обозначены соответственно регистры абсциссы, ординаты и угла, а «Умн», «П», «Век» — сокращенные обозначения операций умножения, «поворота» и «вектора».
4>c+q>0 Me 7/К 2
Рис. 28
Рис 29
Как показывают результаты построения схем вычислительного процесса для большого числа навигационных задач [32, 54, 64, 78] количество ступеней вычислений не превышает 5—7. На рис. 28, например, изображены 4 ступени. Это в значительной мере определяется тем, что при методе «цифра за цифрой» за одну ступень вычислений могут быть выполнены такие сложные операции, как преобразование координат. При использовании традиционных методов поворот осей декартовых координат, например, требует 11 ступеней вычислений. Малое число ступеней вычислений при использовании метода «цифра за цифрой» значительно упрощает анализ погрешностей сложных формул.
При рассмотрении большого числа формул решения различных навигационных задач можно заметить, что в подавляющем большинстве случаев заключительной ступенью является операция «вектор». Как следует из графиков рис. 9, 11, при операции «вектор» наибольшую погрешность имеет функция arctg (У/Х) [6]. Следовательно, при анализе погрешностей с целью выбора длины разрядной сетки необходимо учитывать именно эту функцию.
Непосредственный анализ погрешностей вычисления формул можно разбить на два этапа — грубый и точный.
При грубом анализе, исходя из допустимой погрешности с помощью графиков и приближенных формул, оценивают разрядность проектируемой СЦВМ. При точном анализе, на основании найденной разрядности и известных методик [35], вы  числяют погрешность результата при различном числе основных и дополнительных разрядЬв.
Рассмотрим этап I анализа погрешностей вычисления сложных формул по способу Волдера. С этой целью необходимо последовательно выполнить ряд вычислений:
1) по допустимой среднеквадратической погрешности результата Одон и максимальной величине выходной переменной определяют нижнюю границу длины разрядной сетки:
= ] logs (^тах/адоп)тах[ К	1
 2) по графику (см. рис. 11) определяют соответствующую этой разрядности погрешность (ц при г=0;
3)	по графикам (см. рис. 8, 14) определяют погрешности операций «поворот» и умножения при n=tii и г—0—От и <тумнь
4)	вычисляют погрешность результата по формуле
°рез 1 —
1 f д2_1__ 4(°п1^ + °умн1М)
V	з№л1
(4.1)
где h — число операций «поворот»; М — число умножений; Кт — коэффициент деформации вектора при п-ги;
5)	’ вычисляют требуемое число дополнительных разрядов: Г1 = ]log2 (орез! 2" 1/2)[-|— 1.
Если окажется, что г^З, то берут новую величину п: «2 = «1+1 и повторяют вычисления по формуле (4.1). При этом число дополнительных разрядов определяют из выражения «2=] log2(epe322«2/4)[+.l.
При точном анализе погрешностей вычисления формул в качестве исходной разрядности берут величину /г, полученную па этапе I, а число дополнительных разрядов г полагают равным нулю. Используя методику постепенной трансформации погрешностей [35], вычисляют 0ni и <Tsi при заданных величинах п и г. Логическая схема дальнейших вычислений представлена на рис. 29."
Вычисления осуществляются по следующим формулам:
Г(dZx \2 о I / dZi \2 2	„
°z 1 = |/ ( д Л ) °*-!- \д(К2)) ' 1<2 °умн >
_ -1 /~(V о2	/^2 V 02 I а2
0X2—1/ (aZ! J °Х1ТДй? J <Р^ п,
Г[dZj \2 9 . (dZ3 \2 р . 9
0x3= |/	+ °к + °уми ’
1/"(^Уох2 + (^Тохз + °2 t
Оп = |/ \az2 / Z2~	/ Z3 ~ arcts ’
Г [ dS \2 9	। I dS \2 9	.	9
°S |/ /dZ^J °X2“1 (/zr) ахз + °век. иЯ,
где Zb Z2, Z3 — промежуточные результаты вычислений (рис. 28).
.	На рис. 30 представлены за-
висимости погрешностей вычислении пеленга П от числа дополнительных разрядов при длине разрядной сетки п = 30, 31, 32.
Остановимся на выборе структуры СЦВМ по заданному быстродействию, взяв в качестве исходных данных выбранную разрядность и блок-схему алгоритма" решения задачи (см. рис. 28).
Зная число ступеней вычислений Мст и допустимое
время вычислений /доп, определяют время реализации одной ступени, равное = t ДОп/ЛгСт. Затем определяют допустимое относительное время вычислений, равное ?от=^1/тз-По найденной разрядности с помощью графика зависимости быстродействия (см. рис. 23) проводят перпендикулярно к оси абсцисс прямую до пересечения ее с горизонталью, проведенной из точки на оси ординат, соответствующей числу /от.
Все кривые, проходящие ниже точки пересечения, удовлетворяют заданным требованиям по точности и быстродействию.
4.2. ОБЛАСТИ ПРИМЕНЕНИЯ АППАРАТУРНОЙ РЕАЛИЗАЦИИ ЭЛЕМЕНТАРНЫХ ФУНКЦИЙ
Следует подчеркнуть, что в настоящей работе подробно исследован только «нижний» уровень реализации метода «цифра за цифрой», т. е. рассматривается лишь та часть ЦВМ, которая непосредственно относится к вычислению элементарных функций: операционное устройство (ОУ), блок микропрограммного управления (БМПУ), постоянное запоминающее устройство (ПЗУ). Что касается оценок «верхнего» уровня, т. е. устройства центрального управления, ОЗУ, ДЗУ и т. д., то вопросы, связанные с этим, только ставятся и намечаются возможные пути их решения.
Как было указано выше, ввиду отсутствия разработанной методики оценки затрат оборудования на этапе структурного проектирования и единой типовой системы логических элементов (ТСЛЭ), оценки по аппаратурным затратам производятся для .наиболее распространенной типовой системы транзисторно-транзисторных логических элементов «Логика-2» путем доведения различных вариантов структур до принципиальных схем. Данная задача облегчается тем, что имеются рекомендованные схемы типовых узлов: сумматора, регистра, счетчика и т. д., выполненные на используемой системе элементов. Ниже показано количество элементов различных типовых функциональ-
ных узлов: Последовательный сумматор.........................12
Статический регистр .................. 2п
Сдвигающий регистр...................  4п
Сдвигающий регистр со сдвигом вправо и влево..............................  5п
Параллельный сумматор..................8п
Параллельный сумматор со	сдвигом .... 13,5м
Для всех вариантов структур, реализующих метод «цифра за цифрой», были разработаны функциональные схемы.
Кроме регистров* и сумматоров в состав операционного устройства входят вентили связи, схемы преобразования кодов, триггеры управления и т. д.	.
Рекуррентные соотношения для вычисления элементарных функций, временные диаграммы работы и структуры ОУ служат основой для построения микропрограмм. В состав БМПУ кроме микропрограммного автомата входят два счетчика (счетчик тактов и счетчик циклов) и регистр адреса ПЗУ. Суммарные затраты оборудования на реализацию БМПУ представлены на рис. 31.
Рис. 31
Постоянное .запоминающее устройство также реализуется на типовой системе логических элементов. Затраты оборудования ПЗУ в количестве элементов для различных разрядностей представлены в табл. 8.
Таблица 8
Константа	Разрядность:							
	7	способ Волдера			способ Меджита			
		14	28	42 .	7	14	28	42
arctg 2	3	11	44	98	5	17	66	147
Arth 2—/	3	11	44	98	5	17	66	147
ln(l±2~z)	9	33	132	294	18	66	264	588
Каждый из вариантов структурной схемы вычислительного блока характеризуется определенными затратами оборудования. Зависимости затрат оборудования по отдельным блокам — ОУ, БМПУ и общие аппаратурные затраты, выраженные в числе модулей, представлены на рис. 31, 32, 33 и 34.
Сопоставляя зависимости требуемых затрат оборудования для двух способов реализации метода «цифра за цифрой», можно отметить следующее:
последовательные варианты структур, реализующие способ Меджита (см. рис. 22, 4а, 5а), более экономичны,' чем соответствующие структуры, реализующие способ Волдера (см. рис. 21* 1а, 2а), но эти преимущества «компенсируются» большими затратами БМПУ и ПЗУ; соответствующие параллельные варианты структур экономичнее при использовании способа Волдера;
Затрата оборувования
Рис. 33
Рис. 34
наименьших аппаратурных затрат требуют структуры, реализующие способ Волдера с одним, двумя и тремя последовательными сумматорами, и структуры, использующие способ Меджита с двумя последовательными сумматорами.
О 10	20 J0 40	50 п
Рис. 35
Аналогичному анализу подвергалась структура вычислительного блока параллельного типа для реализации элементарных функций с помощью метода полиномиальной аппроксимации (см... рис. 25). Учитывались все затраты оборудования на реализацию типовых схем регистров, сумматора, счетчика, схем связи и т. д. Результаты анализа представлены на рис. 35.
Анализируя графики общих затрат оборудования на реализацию метода полиномиальной аппроксимации, можно заметить, что наиболее близки к ним структуры 16 и 46 на рис. 21 (структуры с одним параллельным сумматором), реализующие метод «цифра за цифрой».
Сопоставив соответствующие зависимости для оценки времени реализации (см. рис. 23, 24 и рис. 26, 27) можно отметить, что для данной системы элементов и рассматриваемых структур при равных затратах оборудования, начиная с разрядности • п«15, с точки зрения быстродействия выгоднее применять метод «цифра за цифрой».
В итоге можно сказать, что, вероятно, не существует мето- ' дОв вычисления на ЦВМ элементарных функций, «оптимальных» в абсолютном смысле слова. Существуют лишь «оптимальные области» применения каждого метода. Одним из определяющих факторов применения того или иного метода является соответствующая ему точность вычисления элементарных функций.
Точность, с одной стороны, это необходимая оценка качества вычислений, а с другой — она связывает численный метод и разрядность ЦВМ. Разрядность же машины во многом определяет и быстродействие и требуемые аппаратурные затраты.
Данная работа является одной из первых попыток детального рассмотрения вопросов, связанных с аппаратурной реализацией элементарных функций. Основные трудности, с которыми встретились авторы, состоят в том, что практика проектирования ЦВМ создала широкий «спектр» как структурных, так и схемных решений, характеристики которых в настоящее время почти не поддаются аналитическому описанию.
В связи с этим в данной работе исследования реализации численных методов проводились для гипотетических моделей, и полученные оценки справедливы только в среднем.
Вопросы, связанные с аппаратурной реализацией элементарных функций, естественно, не исчерпываются содержанием этой книги. Поскольку данные вопросы находятся на стыке вычислительной математики и цифровой вычислительной техники, то можно надеяться, чтд усилия специалистов двух указанных направлений дадут ощутимые результаты в развитии теории и практики проектирования ЦВМ с аппаратурной реализацией элементарных функций.
УКАЗАТЕЛЬ ЛИ НАТУГИ
1.	Акушский Й. Я., Юдицкий Д. И. Некоторые вопросы логики и структуры ЭЦВМ высокой производительности.—«Вопр. радиоэлектроники», I960, сер. VII, вып. 3, с. 20—58.
2.	Байков В. Д., Смолов В. Б. Анализ одной группы погрешностей алгоритма Волдера —«Изв. вузов», сер. Приборостроение, 1973, т. 16, № 2, с. 60—62.
3.	Б а й к о в В. Д и др. Вопросы проектирования микропрограмм вычисления элементарных функций по методу «цифра за цифрой».— В кн.: Технические средства управляющих машин. Киев, 1973, с. 22—28
4.	Б а й к о в В. Д. Методика выбора длины разрядной сетки специализированного навигационного вычислительного устройства.— В кн.: Реферативная информация по радиоэлектронике, 1972, № 8, с. 138.
5.	Байков В. Д. Использование.метода вычисления «цифра за цифрой» в навигационных СЦВМ.— В кн.: Реферативная информация по радиоэлектронике, 1972, № 8, с. 153.
6.	Байков В Д., Смолов В. Б. Выбор разрядности вычислительного устройства, работающего по алгоритму Волдера.—«Йзв. вузов», сер. Приборостроение, 1973, т. 16, № 7, с. 53—57.
7.	Б а й к о в В. Д. Устройство деления. Авторское св.идетельство № 417790, кл. GO6/7/52.—«Открытия, изобретен., пром, образцы и тов. знаки», 1974, № 8, с. 139—140.
8.	Б а л а ш о в Ю. К., К У п р и я нов Б. И. Аппаратный метод вычисления функций arctg(y/x) и j/x2-|-y2 в СЦВМ.—«Вычислительная технике в машиностроении», 1967, июль, с. 139—143.
9.	Б а ш л а к о в Е. П и др. Выполнение арифметических операций в вычислительном устройстве, работающем по методу Волдера.— В кн.: Вопросы теории ЭЦВМ. Киев, 1968, вып. 2, с. 16—24.
10.	Башлаков Е П., Ерема-Еременко А. А. Быстродействующие итерационные схемы для вычисления тригонометрических функций.— В кн,: Математическое обеспечение ЭЦВМ. 1970, вып. 4, с. 62—73.
11.	Башлаков Е. П. и др. Вопросы развития структур малых ЦВМ с произвольной значностью используемой системы счисления.—«Кибернетика», 1972, № 1, с. 74—78.
12.	Г л у ш к о в В. М. и др. Вопросы развития структур ЦВМ в связи с системами их математического обеспечения —«Кибернетика», 1967, № 5, с. 15—28.
13.	Геллер С. И., Журавлев Ю. П. Основы логического проектирования ЦВМ. М., 1969. 272 с.
14.	Д е м и д о в и ч Б. П., Марон И, А. Основы вычислительной математики. М., 1970 664 с.
15-	Дородницына А. А. Микропрограммирование элементарных 'функций, представленных разложением в цепную дробь.—«Кибернетика», 1966, Ks 6, с. 34—40.
16.	Д о л м а т о в Б. П. Решение штурманских задач на малых вычислительных машинах. Мурманск, 1970. 1S8 с.
17.	Каневский Е, А. Вычисление элементарных функций в настольных ЭКВМ.— В кн.: Вычисление функций и алгебраических выражений. М., 1969, с. 2—64.
18.	Кхамбата. Большие интегральные схемы. М., 1971,. 256 с.
19.	Л а п ы г и н Е. Д. Аппаратные методы ускорения вычисления некоторых элементарных функций,—«Вопр радиоэлектроники», сер. VII, 1964, вып. 7, с. 3—17.
20.	Л а п ы г и н Е. Д. Аппаратные методы ускорения вычисления некоторых элементарных функций.—«Вопр. радиоэлектроники», сер. XII, 1965, вып. 4, с. 3—14.
21	Л и ж д в о й Г. Л., Ш и л е й к о А. В. Принципы построения вычислительного модуля, реализующего укрупненные операции.— В кн.: Вычислительные системы и среды. Таганрог, 1972, с. 170—172.
22.	Л и в ш и ц С. Е. О погрешностях округления при решении экономических задач на ЭЦВМ.— В кн.: Вычислительная техника и механизация управленческого труда. Л., 1965, вып. 55, с. 72—78.
23.	Л и и с к и й В. С. Вычисление элементарных функций на автоматических цифровых машинах.— В 'кн.: Вычислительная математика. 1957 № 2 •с. 90—119.	'
24.	Л ю с т е р н и к Л. А. и др Вычисление элементарных функций, 1963. 247 с.
25.	Масуока Т. Идея создания единого технического и математического обеспечений.—«Дэнки гидзюцу» («Electronic Engineering”). 1971, vol. 13, № 3, р. 111—115.	-• Л
26.	О ж и г а н о в Л. И., К у л е е в X. Ф. Один из способов практической реализации табличного метода получения прямых и обратных тригонометрических функций в ЦВУ.—«Труды Казанского авиационного института», 1968, вып. 94, с. 83—87.
27.	О р а н с к и й А. М. и др. Быстродействующее устройство вычисления синусно-косинусных функций.—«Вестник БГУ», сер. I, 1969, № 3, с. 72—78.
28	Оранский А. М., Рейхенберг А Л. Методы и средства цифрового функционального преобразования. — В кн.': Функциональное преобразование информации. Минск, 1971, с. 44- 46.
29.	Оранский А. М., Рейхенберг А. Л. Таблично-алгоритмические методы вычисления арифметических и элементарных функций,— В кн.: Функциональное преобразование информации. Минск, 1971, с. 41—43
30.	П а п е р н о в А. А. Логические основы цифровых машин и программирования. М., 1972. 592 с.
31.	Папер в о в А. А., Петрова Т. И. К вопросу об округлении произведения при умножении со старших разрядов множителя.— В кн.: Цифровая вычислительная техника и программирование. 1966, вып. 1, с. 5—11.
32.	П а р и н и Д. «Дивик» решает комплекс навигационных вопросов.— «Электроника», 1966, № 18, с. 30—38.
33.	Песлйк Е. А. Точность вычисления элементарных функций на цифровых вычислителях—«Вопр. радиоэлектроники», 1968, вып. 23, с. 124—131.
34.	Плотников А. В., Степашкин Г. И. Оценка инструментальной точности специализированного вычислителя.— В кн.: Вычислительная техника. Под ред. Смолова В. Б_, 1970, № 1, с. 187—194.
35.	Проектирование и расчет вычислительных машин непрерывного действия. Под ред. А. Н. Лебедева и В. Б. Смолова. М., 1966. 336 с.
36.	П осп ел о в Д А. Арифметические основы вычислительных машин дискретного действия. М., 1970. 308 с.
37.	П р е с н у х и н Н. И. и др. Основы теории и проектирования вычислительных приборов и машин управления. М., 1970. 631 с.
38.	П а л а г и н Д. В., К у р г а е в А. Ф., К о н д р а ч у к И. М. К выбору метода вычисления элементарных функций в мини-ЭВМ.—«Управляющие системы и машины», 1973, № 5, с. 65—69.
39.	Радиоэлектроника в 1970 г.— В кн.: Обзор зарубежной печати, 1971, т. VI, с. VI—2.
40.	Рейхенберг А. Л., Шевченко Р. Я. Ускоренные итерационные алгоритмы для вычисления прямых и обратных тригонометрических и гиперболических функций методами «цифра за' цифрой». В кн.: Функциональное преобразование информации. Минск, 1971, с. 38—40.
41.	Смирнов Н. В.,г Д v н и н - Б а р ко в с к и й И. В. Курс теории вероятностей и математической статистики. М., 1969. 511 с.
42.	С м о л о в В. Б., Байков В. Д. Погрешности выполнения арифметических операций на ЦВМ с фиксированной запятой.—«Изв. вузов», сер. Приборостроение, 1972, т. 15, № 4, с. 65—68.
43.	С м о л о в В. Б., Байков В. Д. Анализ погрешностей вычислений на СЦВМ элементарных функций по методу «цифра за цифрой».— В кн.: Кибернетическая техника. Киеь, 1971, с. 30—39.
44.	Шилин И. Ф. Некоторые аппаратные способы вычисления тригонометрических функций sin х, cos х в ЦВМ.—«Вопр. радиоэлектроники», сер. XII, 1969, вып. 14, с. 47—55.
45.	Aus Н. М., Korn G. A. Table-Iook-up/interpolation function generation for fixed-point digital computations.—-IEEE Trans, on Comp., 1969, C-18, N 8, 745—749.
46.	Berner R. W. A subroutine method for calculating logarithms.— Common. ACM, J958, vol. 1, N 5, p. 5—7.
47.	Bruce D., Shriver S. Microprogramming and numerical 'analysis.—IEEE Trans, on Comp., 1971, C-20, N 7, p. 808—811.
48.	Cantor D. G. et al. Logarithmic and exponential function evaluation in a variable structure digital computers.— IRE Trans, on Electronic Comp., 1962, EC-11, N 4, p. 155—164.
49.	C h e n T. C. Automatic computation of exponentials; logarithms, rations and square roots.— IBM J. Res. a. Develop., 1972, vol. 16, N 4, p. 380—388.
50.	С1 u 11 e r h a m D. Vector technique speeds computer capability.— «Missiles and Rockets», 1963. vol. 13, N 23, p. 32—34.
51.	D a g g e 11 D. H. Decimal-binary conversions in CORDIC.— IRE Trans, on Electronic Comp., 1959, EC-8, N 3, p. 335—339.
52.	D а у a M. Digit by digit method for the simultaneous evaluation of sine and cosine functions.— South Afr. J. Sci. 1969, vol. 65, N 4, p. 115—118.
53.	D о b r i n e r R. New computers spur airborne Loran.— «Electronic Design», 1964, vol. 12, N 26, p. 12—15.
54.	Em tno tt . N. W. Computers and navigation systems.— Proc. Nat, Aerosp. Electronic Cqnc Dayton, 1969, p. 305—310.
55.	G a r w i c k I. V. The accuracy of floating point computers.—«Nordisk tidskrift for information behandlrfig», 1961, Bd. 1, N 2, p. 87—88.
56.	G r e g о г у R. On the design of the arithmetic unit of a fixed-word length computer from the standpoint of computational accuracy.—IEEE Trans, on Electronic Comp., 1966, EC-15, N 2, p. 255 256.
57.	G г о о t L. Navigation and control from Loran C. <— «Navigation» (USA), 1964, vol. 11, N 3, p. 213—227.
58.	Henderson D. S. Machine evaluation of common functions.— South Afr. J. of Sci., 1966, vol. 62, N 4, p. 100—102.
 59. Hewlett-Packard. 9100a computing calculator.— Hewlett-Packard J., 1968, vol. 20, N 1, p. 3—19.
60.	H о b b s L. C. Effects of large arrays on machine organization and hardware/software tradeoffs.— Proc. Fall Joint Comp. Conf., 1966, p. 89.
61.	Hull T. E., Swenson J. R. Tests of probabilistic models for propagation of Roundoff errors.— Commun. ACM, 1966, vol. 9, N 2, p. 108—113.
62.	К1 a s s P. J. Computer simplifies Loran C navigation.— «Aviation Week and Space Technology», 1964, vol. 80, N 24, p. 93—97.
63.	Kogbetliantz E. G. Generation of elementary functions. Mathematical methods for digital computer. N. Y., 1960. p. 7—35.
64.	К у d d J. Design aspects of a digital airborne navigation computer.— «Electronics and Communications», 1966, vol. 14, N 2, p. 21—23.
65.	L i n h a r d t R. J., M i 11 e r H. S. Digit by digit transcendental function computation.— RCA Review, 1969, vol. 30, N 2, p. 209—247.
66.	Lucaszewicz L. Accumulation of errors in approximate calculations.— Bui. Acad. Pol. Sci., 1958, vol. VI, N 4, p. 233—239.
67.	L u 11 о n T. Hyperbolic coordinate converter general purpose airborne navigation computer.— VHIth Intern. Conf, on Lighthouses a. other Aids to Nav.„ 1970. Stockholm, p. 7.9.2—7.9.17.
68.	M e g g i 11 J. E. Pseudodivision and pseudomultiplication processes.— IBiM J. Res. a. Develop., 1962, vol. 6, N 2, p. 210—226.
69.	M e g g i 11 J. E. Digit by digit methods for polynomials.— IBM J. Res» a. Develop., 1963, vol. 7, N 3, p. 237—245.
70.	P e r 1 e M. D. The dual logarithm algorithm.— «Computer Design». 1970, vol. 9, N 1, p. 88—90.
71.	Р е г 1 е М. D. CORDIC technique reduces trigonometric functions, look-up.— «Computer Design», 1971, vol. 10, N 6, p. 72—78.
72	Q'uinn G. H. Loran C computer evaluation.— U. S.— Govern. Res. and Develop. Rep., 1970, vol. 70, N 16, p. 95.
73.	Racy R. A. A digital computer for the Loran C navigation system.— Proc, of the 11th Annual East Coast Conf, on Aerosp. and Navig. Electronics. Baltymore, 1964, p. 3.2.2-1—3.2.2-11.
74.	S a г к a r B. P_, Kr is hnamurt hy E. V. Economic pseudodivision processes for obtaining square root, logarithm and arctan.— IEEE Trans., Comp., 1971, vol. 20, N 12, p. 1589—1593.
75.	Schmid H. BCD: trig and hyperbolic, functions.—«Electronic Design», 1973, vol. 21, N 19, p. 68—73.	'
76.	S p e с к e r W. H. Class of algorithms for evaluation In x, exp x,. sin x, cos x, arctg x, arcctg x.— IRE Trans. Electronic Comp., 1965, vol. 14, N 1, p. 85—86.
77.	U r a b e M. Roundoff error distribution in fixed-point multiplication and a remark about the rounding rule.— SIAM J. Numerical Anal., 1968, vol. 5,. N 2, p. 202—210.
78.	V о 1 d e r J. E. The CORDIC trigonometric computing technique.— IRE Trans, on Electronic Comp., 1959, vol. 8, N 3, p. 330—334.
79.	Voider J. E. The CORDIC computing technique.— „Proc. West Joint Comp. Conf.,” 1959, p. 257—261.	'
80.	W a 11 h e r S. A unified algorithm for elementary functions.— Spring: Joint Computer Conf. New Jersey, 1971, vol. 38, p. 379—385.
81.	Wensley J. H A class of non-analytical iterative processes.—Comp, J., 1959, v. 1, N 4, p. 163—167.