5.4. МЕТОДЫ ВЫЧИСЛЕНИЯ ЭЛЕМЕНТАРНЫХ ФУНКЦИЙ

В цифровой вычислительной технике применяют следующие методы вычисления элементарных функций (ЭФ) [27, 38]: разложение в ряд Тейлора (степенные полиномы), аппроксимацию с помощью различных полиномов, табличные методы, рациональные приближения ЭФ, использование цепных дробей, итерационные (рекуррентные).

Степенные полиномы (отрезок ряда Тейлора, полином Чебышева и т. д.) вычисляются в ЭВМ чаще всего по схеме Горнера. При этом требуется выполнить операций умножения и операций сложения — степень полинома). К сожалению ряд Тейлора очень медленно сходится для некоторых функций (натуральный логарифм, обратные тригонометрические и гиперболические функции), и поэтому время вычисления будет большим, а инструментальная погрешность увеличивается. Методическая погрешность этого метода монотонно увеличивается с ростом аргумента, и поэтому приходится предварительно сводить аргумент в более узкую область с помощью соответствующих преобразований. Достоинством разложения в ряд Тейлора (в отличие от аппроксимации полинома Чебышева) является то, что можно вычислять коэффициенты членов ряда непосредственно при вычислении функций и не хранить их в памяти ЭВМ Однако при этом возрастает время вычисления ЭФ. Единообразие вычисления всех ЭФ трудно обеспечить из-за плохой сходимости ряда для некоторых функций.

Метод полиномиальной аппроксимации используется в ЭВМ наиболее часто. Он характеризуется достаточно высоким единообразием вычисления всех ЭФ, однако при этом в памяти необходимо хранить большое количество коэффициентов всех полиномов. Для ускорения сходимости полинома аргумент предварительно сводится в более

узкую область. Методическая погрешность знакопеременна и равномерно распределена на интервале изменения аргумента. Для вычисления ЭФ с произвольной разрядностью в некоторых ЭВМ используется комбинированный таблично-полиномиальный алгоритм. Приближение любой ЭФ в приведенном интервале ведется с помощью подпрограмм не одним ортогональным полиномом, а их набором, каждый из которых применяется на подынтервалах с возрастанием степени аппроксимации от одного подынтервала к следующему.

- Табличные методы основаны главным образом на кусочно-линейной и криволинейной аппроксимации. Для вычисления ЭФ этим методом требуется выполнить малое число арифметических операций, однако объем таблиц и время поиска в них может быть большим. Поэтому этот метод применяется в машинах с небольшой разрядностью слов.

При методе рационального приближения ЭФ функцию представляют в виде отношения двух полиномов, причем число членов в каждом полиноме намного меньше, чем при соответствующем разложении в ряд Тейлора. Однако коэффициенты полиномов должны обязательно храниться в памяти. Для вычисления ЭФ следует вычислить два полинома и выполнить операцию деления.

Метод цепных дробей характеризуется единообразием вычисления всех ЭФ, при этом количество констант мало. По сравнению с методом степенных полиномов при этом методе число шагов меньше, однако на каждом шаге выполняется операция деления, занимающая много времени. Хотя для цепных дробей область сходимости более широкая, чем для ряда Тейлора, но с ростом аргумента резко возрастает необходимое число звеньев дроби. Это заставляет приводить аргументы к интервалу, не более широкому чем при разложении ряд Тейлора. Оценка погрешности является сложной. Метод используется в малых машинах, где быстродействие не очень важно. Например, в машине «Проминь» метод цепных дробей реализован микропрограммно.

Итерационные методы предполагают вычисление последовательных приближений функции по итерационной формуле Необходимость в ряде случаев выполнять операции деления и умножения на каждой итерации уменьшает быстродействие вычислений. Оценка погрешности удобна, алгоритмы вычисления некоторых функций (базового набора) достаточно единообразны. Загрузка памяти наименьшая, так как константы можно вычислить непосредственно перед счетом функций по той же схеме. Это снижает быстродействие, но является решающим преимуществом при использовании в машинах с произвольной разрядностью [27].

Для большинства других методов характерно отсутствие единообразной методики вычисления всех ЭФ. Это приводило к тому, что выбирался набор так называемых базовых функций, вычисляемых выбранным методом, а остальные ЭФ выражались через базовые и вычислялись на их основе. Например, в машине МИР базовый набор ЭФ состоит из функций Такая методика приводит к многоуровневой организации управления, усложнению структуры управляющего устройства и к увеличению времени вычисления.

Разработаны новые эффективные итерационные алгоритмы вычисления ЭФ. Этот метод чаще всего называется методом «цифра за

цифрой», так как после итераций алгоритма получается значение функции с точностью до единицы -го разряда. Однако следует заметить, что в отличие от традиционных методов «цифра за цифрой» (например, деление) в данном методе на каждом шаге итерации получается полноразрядный приближенный результат, а приращение прибавляется к нему, так что на любом шаге из-за переносов может измениться любая цифра результата, вплоть до старшего разряда. Тем не менее этот метод обычно называется методом «цифра за цифрой». Важным преимуществом этого метода является его эффективность для непосредственного вычисления почти всех ЭФ. С помощью этого метода можно также находить корни полиномов, выполнять преобразования координат и преобразования систем счисления чисел. Погрешность вычислений легко компенсируется с помощью дополнительных разрядов. Области сходимости достаточно широкие, а для некоторых функций вообще не требуется приведения аргумента. Так как алгоритмы метода построены на простых операциях сдвига и сложения, то их аппаратная реализация является простой и эффективной. Метод позволяет вычислять большинство ЭФ за время трех операций деления (если не учитывать приведение аргумента), причем его алгоритмам присущ внутренний параллелизм, позволяющий еще более повысить быстродействие за счет совмещения операций в одном процессоре. Недостатками метода является большое количество используемых констант и применение операционного устройства со специфической структурой.

Таким образом, метод «цифра за цифрой» обладает следующими преимуществами при структурной реализации; высокое быстродействие алгоритмов, основанных на операциях сдвига и сложения; единообразие вычисления почти всех ЭФ и оправданные аппаратурные затраты; простая организация вычислительного процесса, малое число уровней управления; удобство аппаратной компенсации погрешностей, возникающих при реализации алгоритмов на ЭВМ.

Метод «цифра за цифрой»

В основе данного метода лежит процедура преобразования прямот угольных координат точки в полярную, которую приспособили для вычисления большинства ЭФ. Метод «цифра за цифрой» в геометрическом смысле есть последовательность преобразований вектора в плоскости т. е. последовательность поворотов радиуса вектора на стандартные углы вокруг начала координат с одновременным изменением длины вектора В машине этот процесс представляется арифметическими преобразованиями координат вектора.

Например, для вычисления функций берется исходный вектор с координатами и поворачивается последовательно на углы так, чтобы алгебраическая сумма всех этих углов была равна Тогда, очевидно, координаты итогового вектора равны искомым функциям Согласно известным формулам, при каждом повороте вектора на угол а, новые координаты вектора выражаются через предыдущие [27]:

Стандартные углы заранее выбирают такими, чтобы были равны целой степени основания системы счисления, используемой в ЭВМ. Тогда операция умножения на превращается в операцию сдвига. Для того чтобы вектор в процессе таких поворотов приближался к требуемому положению, определяемому аргументом необходимо поворачивать его на каждом шаге по (или против) часовой стрелке, в зависимости от того, является ли текущий угол наклона вектора к оси абсцисс больше или меньше аргумента знак очередного угла поворота выбирается из условия

Кроме того, абсолютные значения углов поворота должны уменьшаться по мере приближения вектора к требуемому положению. Доказано, что для двоичной системы счисления такой процесс сходится при т. е., что в результате поворотов исходного вектора последовательно на углы вектор приближается к требуемому (под углом к оси абсцисс) с методической погрешностью, равной последнему из примененных углов поворота. Поэтому для -разрядных двоичных чисел достаточно выполнить поворотов. При дальнейших поворотах на углы приращения координат при использовании чисел с фиксированной запятой будут равны машинному нулю.

Если в формулах (5.2) и (5.10) отбросить множитель , то они будут описывать поворот вектора с одновременным увеличением его длины в раз. Тогда в результате -кратного итерационного применения формул длина вектора увеличится в раз называют коэффициентом деформации тригонометрического вектора). Чтобы скомпенсировать это удлинение, в качестве начального вектора берут вектор длиной .

Таким образом, с учетом изложенного процесс вычисления функций описывается формулами:

Формулы (5.12) применяются раз итерационно при начальных значениях координат

Рис. 5.3

Рис. 5.4

и в итоге получается с точностью до

С помощью такого алгоритма легко вычислить функцию

Для этого берется исходный вектор и поворачивается на такие же стандартные углы таким образом, чтобы положить итоговый вектор на ось абсцисс (рис. 5.3). Когда это достигнуто, то накопленная к концу алгоритма алгебраическая сумма углов поворотов равна Вычисления выполняются по формулам:

и в итоге имеем

Вычисление гиперболических функций аналогично описанным и имеют сходную геометрическую интерпретацию. Как известно, множество точек с координатами для всевозможных действительных образует на плоскости гиперболическую кривую (рис. 5.4). Поэтому для получения функций требуется найти точку на гиперболе, соответствующую значению аргумента Для этого берут исходный вектор и вращают его, одновременно изменяя длину вектора таким образом, чтобы конец вектора скользил по гиперболе. Одновременно с перемещением вектора подсчитывают значения аргумента, соответствующие его текущему положению. Когда текущее значение аргумента достигнет заданного координаты вектора будут равны При изменении аргумента на величину а координаты вектора, скользящего по гиперболе, изменятся согласно известным выражениям:

Для данного случая эти формулы удобно записать следующим образом:

где координаты вектора после приращения аргумента на величину . В качестве констант в двоичной системе счисления выбирают следующие константы: Для того чтобы описанный процесс перемещения вектора сходился в требуемую точку, необходимо использовать каждую из констант дважды. Аналогично тригонометрическим функциям, множитель в формулах (5.17) отбрасывают, в результате чего длина вектора будет дополнительно изменяться В результате приращений аргумента на указанные константы вектор изменится в раз

Назовем коэффициентом деформации гиперболического вектора. Деформация компенсируется аналогично тригонометрическим функциям.

С учетом вышеизложенного формулы вычисления функций принимают вид:

где

Задав начальные условия и применив формулы (5.19) итерационно раз, получим Для сходимости вычисления достаточно, чтобы

Вычисление функции заключается в следующем. Исходный вектор перемещается так, чтобы его конец скользил по гиперболе и попал в точку пересечения гиперболы с осью абсцисс. Когда это достигнуто, то алгебраическая сумма всех константа, соответствующих выполненным преобразованиям исходного вектора, равна искомому значению функции Этот процесс описывается формулами:

которые применяются раз итерационно при начальных значениях и дают в итоге

с точностью до -двоичных разрядов.

В описанных алгоритмах вычисления прямых тригонометрических и гиперболических функций происходит разложение значения аргумента в набор констант или т. е. аргумент как бы преобразуется в систему счисления с цифрами ±1 и с весами разрядов или соответственно, а функция вычисляется по набору . В алгоритмах вычисления соответствующих обратных функций получают «цифра за цифрой» значение функции в виде же промежуточной системе счисления, а затем преобразуют значение функции в двоичную систему счисления путем сложения соответствующих констант. Аналогично для вычисления логарифмической и экспоненциальной функций в двоичной системе применяются константы

Для вычисления функции аргумент преобразуют в сумму констант вида При этом знак следует выбирать на каждом шаге так, чтобы текущее промежуточное значение аргумента стремилось к заданному т. е.

Для того чтобы процесс представления аргумента суммой констант сходился, необходимо дважды использовать каждую из констант Видно, что приращению текущего значения на величину соответствует увеличение текущего значения функции раз, т. е. Таким образом, алгоритм вычисления описывается следующими итерационными формулами:

которые при начальных значениях дают после итераций

Для вычисления функции аргумент х преобразуют в произведение

Чтобы добиться такого разложения аргумента, т. е. найти берут заданное значение аргумента и последовательно умножают его на каждый раз выбирая знак таким образом, чтобы получаемое произведение стремилось к единице. Когда х представлено формулой (5,24),

логарифм находится как

Таким образом, алгоритм вычисления функции описывается формулами

которые при начальных значениях лают после итераций

Чтобы этот алгоритм был похожим на алгоритмы многих других функций, можно одновременно с вычислением величины вести подсчет величины Для этого достаточно установить начальное значение и прибавлять к приращения, противоположные приращениям величины Тогда формулы алгоритма вычисления примут вид

где

Другой способ вычисления функций использует алгоритмы вычисления функций и известные тождества

Аналогично вычисляют функцию с помощью алгоритма функции и тождества

В самом деле, согласно формуле (5.21) в результате вычисления получаем итоговое значение координаты Если установить начальные значения

то по алгоритму (5.20) согласно формуле (5.29) получим

Методом «цифра за цифрой» можно вычислять не только натуральный, но и любой другой логарифм, например, двоичный или десятичный. Для этого необходимы соответственно константы вида

Вычисление функции сводится к следующему: вектор с координатами поворачивается на набор стандартных углов так, что ордината принимает значения аргумента. Тогда алгебраическая сумма всех выполненных углов поворота равна искомой функции . Для реализации такого алгоритма используются те же стандартные углы и та же операция поворота вектора с одновременным его удлинением, что и в алгоритмах (5.12) и (5.14). Чтобы скомпенсировать итоговое удлинение вектора, в качестве начального берут укороченный вектор. При этом длина вращаемого вектора в процессе выполнения алгоритма растет от начального значения до единицы и соответственно этому претерпевают деформацию обе координаты так как в качестве критерия направления векторов в этом алгоритме используется знак разности то указанная деформация приводит к возможности выбора ошибочного направления поворота. Поэтому в отличие от алгоритмов (5.12) и (5.14) необходимо дважды использовать каждый из стандартных углов , кроме того, учитывать возможность выхода вектора во второй или третий квадранты плоскости . С учетом изложенного алгоритм вычисления описывается следующими формулами;

где

При начальных значениях получим . Как видим, алгоритм отличается от алгоритмов вычисления других тригонометрических функций наличием дополнительной операции для определения причем эту операцию необходимо выполнять после применения других формул системы (5.30). Чтобы избежать этого, можно параллельно с вычислением вести подсчет величины При этом алгоритм видоизменяется следующим образом:

При начальных условиях получим .

Другой способ вычисления функций основан на использовании тождества

Сначала вычисляют и находят величину (см. выражение Затем вычисляют с помощью операции умножения или алгоритма вычисления при и наконец, к найденным величинам применяют алгоритм (5.14) (вместо умножения у на можно выполнять деление на

Функцию можно вычислять аналогично функции т. е. взять вектор и повернуть его так, чтобы координата приняла значение аргумента. Иные способы нахождения сводятся к вычислению функций на основе тождества

Вычисление функций аналогично описанным выше для соответствующих обратных тригонометрических. Они отличаются тем, что вектор в процессе преобразования должен двигаться по гиперболе, а тождества имеют

причем величина вычисляется в алгоритме функции Остальные ЭФ вычисляются с помощью перечисленных выше алгоритмов на основе известных тождеств тригонометрии. Следует отметить, что операцию деления, используемую в этих тождествах, можно выполнять по подобному же алгоритму. Для этого делитель представляется в виде

и тогда функция вычисляется по формуле

При этом алгоритм деления записывается так!

где устанавливают начальные значения и получают в результате