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

Секция вычислительной техники

УДК 681.324

В.Ф. Гузик, В.Е. Золотовский

ВЫЧИСЛЕНИЕ ФУНКЦИЙ С АРГУМЕНТАМИ, ПРЕДСТАВЛЕННЫМИ

ПОЛЯМИ

Основные трудности численного определения элементарных функций с аргументами, представленными полями, является переменная точность вычислений, связанная с изменением формата данных в зависимости от задачи. Таким образом, в системах структурного моделирования используются как стандартные программы для фиксированных форматов данных (обычно п = 64 бита), так и программы вычисления функций с аргументом, заданных полями. Под полем понимаются данные, организованные в группы по т разрядов и содержащие неограниченное значение групп. Каждая группа снабжается дополнительным разрядом. Тогда число Х = 0.11.01.11.01.01 (п = 10, т = 4) представляется в виде Х = 0 . 1101 . 0 . 1101 . 0 . 0100.

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

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

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

В рассматриваемом случае наиболее удобными являются итерационные методы и разложения функции в ряды. Рассмотрим итерационные методы.

Пусть задано выражение

и требуется найти значение у в некоторой известной точке х = а, где а - фиксированная величина, заданная полем Ь(Ы) с числом групп N. Так как вычисление затруднительно, то будем искать значение у как корень уравнения Г(у, Ь(^). Организуем следующий итерационный процесс:

Последовательность уп+1 сходится к у, если выполняется условие Липшица с константой q

у = /

| Б(х, Уп) - Б(х, уп+1) | < q•| уп+1 - Уп |.

Тогда начальное приближение следует выбирать из окрестности, в которой

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

В этом случае вначале ищется приближение у для х = х1, где х1 - старшая

группа. Если Уп+1 Уп\ < Є , то условно

считать, что уп+1 » уп . Затем

переходим на следующий этап операции, увеличивая разрядность х = х1 + х2, где х2 - следующая группа разрядов. Тогда имеем

У п+2 = Уп

Откуда

ЛУп+2 = Уп+1

э

Эх0

Р

Р' ((Х1 + Х2 )? У2 ) '

Р

Ух0

У п+2 = Уп+1 +Ау

п+2

Далее процесс продолжается по схеме (1) до тех пор, пока не выполнится условие (2). Если условие выполняется, то входной аргумент увеличивается на следующую группу и так до окончания поля.

Вторым методом, позволяющим проводить вычисление функций с аргументом, представленным полем, является разложение в степенной ряд (ряд Тейлора или Макларена) [2]. Ряд Макларена имеет вид

/"

/(х) = /(0) + /’(0) х + • х 2 + ... +

• хр +...

Как известно из [1], ошибка вычисления функции /(х) определяется как раз-

г Ґ л /у ч V / №• х) к

Е0(х) = /(х)— X------------------,------ х ’

к=0 к

которая может быть оценена по остаточному члену полинома, так как 0 < 8 < 1 и | х | < 1, то \Кп (х)| < --—, что позволяет получить предварительную оценку

(Р +1)!'

-п

числа членов полинома Г £

1

(Р +1)!

где г - основание системы счисления.

Откуда — п 1п г = 1п

( р+1)!

р і -Р

= —X 1п(к +1) и ]---------X1п(к + 1 -

1п г К=1

п.

1

К =1

Для двоичной системы счисления

п

= 1,5Х !п( к +1).

К=1

Например, если п = 128, то р » 43. Ясно, что данная оценка, как правило, является завышенной. Для организации вычислительного процесса используем метод Горнера. В этом случае имеем [1]

/ ( х):

р!

(Р — 1)!

х +

/р-2 І0 (Р — 2)!

х + ... + / '

х + / (0).

Вычисление начинаем со старшей скобки, тогда

1

(Р +1)!

/р (0) Р

\

• х + 1

Для исключения деления представим Р в виде произведения простых чисел. В табл. 1 представлены простые числа и их обратная величина.

Таблица 1

К 1/К в десятичном коде 1/К в двоичном коде

2 0,5

3 0.

5 0.2

7 0.

11 0.

13 0.

17 0.

19 0.

23 0.04347826086956521738

29 0.

31 0.0322

37 0.

41 0.

Таким образом, для вычисления выражения (4) величина Р представляется

как произведение простых чисел

Р = П Рк

где рк - простое число. Тогда ум-

К=1

ножение выполняется следующим образом:

1

х---=

Р

х •

Рх

\_

Р 2

Рп

/

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

1

1

Вычисление значений показательной функции. Пусть задана функция у = ех, где х - аргумент, представленный полем, в полулогарифмической форме, т.е.

х = х -2м -2т,

где N - порядок, определяющий количество сдвигов на число разрядов групп, а т - порядок сдвига на число незначащих разрядов внутри старшей группы.

Следует отметить, что если N - положительное число, то число групп результата экспоненциально возрастает. Действительно, при N = 1 число групп при п = 16 (число разрядов в группе) возрастает до 16. При N = 2 до 256 и т.д. В связи с этим введем ограничение. Если N достигает максимально-разрешённого значения Р, то это считается переполнением, и вычисления прекращаются. Величина Р устанавливается исходя из возможностей аппаратуры. Вторым фактором, устанавливающим ограничение на величину N является необходимость представления величины е с требуемой точностью. Определим погрешность вычисления экспоненты. Для простоты изложения положим т = 0, тогда х представляется следующим образом (рис. 1.):

XXX... X.XXX ..X, XXX... X...........X......XXX... X

х = V---------- ----------; >•--------------------------'

N - группа (Ь - N группа

Рис. 1

Разобьем х на две части - целую и дробную, т.е. X — Ху + Хур, тогда у — e^ • еХДД .

Максимальная погрешность образуется при Хмдх, тогда

гуП'N гу — (L-N )• П

max .

xy —2—(L—N0n Откуда y — e ' e .

x — 2n'N x

Величина ут — e может быть найдена как произведение yx — Kp,

где Ki — K—, Kо — e, i = 0, 1, ..., p - nN.

Т аким образом, если l найдена с погрешностью e, то

ух —(e + e)2nN » e2n'N + 2nN'e2

= ух- у; = 2 пм-е2п -1.

е = 2 2п м -1+пМ

Полагая, что е > 2, получим е у* = 2 , откуда следует, что общая

длина дробной части при условии, что погрешность не превзойдет значения младшего разряда поля, должна быть равна Ьдр = № +Яп, где Я - число групп дробной части.

Длина целой части равна Ьцел = Ып, а общая длина поля Ь = 2N + Я групп. Общая длина в разрядах равна Ь = (2N + Я)  п.

и

В настоящее время величина е определена с точностью приблизительно до 310 десятичных знаков (п » 1023 двоичных разрядов или поле длиной Ь = 64 группы). Указанную длину поля можно считать предельной при построении систем моделирования. Если N <0, то для вычисления используется непосредственно формула разложения

х л х2 ХК

е — 1 + х +-----------+... +-----

2! В!

16 ЫВ Яп —

1 ((2-16)— * )К — 2 -Яп, (2—16Ы  г)— 2

—Я  п

В!

В — Я В — Яп N ’ В! пЫ

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

чк+1

Я <

В!  В

Откуда

(2—16 Г

,В+1

В!  В

где 0 < q < 1.

Путем несложных преобразований q всегда можно привести к интервалу 0 < < 1/2. Действительно, если х лежит в интервале % < 1, то, полагая

х = 1 - (1 - х), получим ех = е  еу, где у = - (1 - х).

Т аким образом, имеем Окончательно имеем

2-^ —

2

-

В! В

- 16N = - (к + 1) - 1од2 к! - 1од2 к.

1Ш 1ё2 = (к + 1) 1ё2 + !ёк! + 1§ к.

Выражение (6) используется для итерационной оценки числа членов разложения. Для этого составляется таблица логарифмов факториала (табл. 2). Затем подбором находят значение К, обеспечивающее заданное значение разрядов. Например, для N = 64 необходимо сохранять 8 членов ряда.

Таблица 2

п п! 1/п!

2 2 0.5

3 6 0.1

4 24 0.25- 0.1

5 120 0.8(3) - 10-2

6 720 0.19889 - 10-2

7 5040 0.19841 - 10-3

8 40320 0.24802 - 10-4

9 362880 0.27557 - 10-5

10 3628800 0.27557 - 10-6

11 39916800 0.25052 - 10-7

12 479001600 0.20877 - 10-8

13 6227020800 0.16059 - 10-9

Окончание табл. 2

14 S717S291200 0.11471 • 10-10

15 130767436S000 0.76472 • 10-12

16 209227S9SSS000 0.47795 • 10-13

17 3556S742S096000 0.2S115 • 10-14

1S 640237370572S000 0.15619 • 10-15

19 12164510040SS32000 0.S2206 • 10-17

20 243290200S176640000 0.41103 • 10-1S

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

Л

у = (Ы + т) 1п2 + 2

( t 2 t2n-1 ^

t +-------+... +------------

3 2n - І

v /

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

БИБЛИОГРАФИЧЕСКИМ СПИСОК Золотовский В.Е. Проблемно-ориентированные системы структурного моделирования. - Таганрог: Изд-во ТРТУ, 2006. - 187 с.

Люстерник Л.А., Абрамов А.А., Шестаков В.И. , Шура-Бура М.Р. Решение математических задач на автоматических цифровых машинах. - М.: Изд-во АН СССР, 1952. Смирнов В.И. Курс высшей математики. Т.1. - М.: Физматлит, 1961.

1

2

3

УДК 681.324

Ю.В. Чернухин, М.В. Крамарь

ПРОБЛЕМЫ ИСПОЛЬЗОВАНИЯ МНОГОЯЗЫКОВОЙ ТРАНСЛЯЦИИ В КОНТЕКСТНО-ЗАВИСИМЫХ ЯЗЫКОВЫХ СРЕДАХ

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

В 70-х годах ХХ в. Т. Виноград разработал систему «SHRDLU», понимающую естественный язык. В ней использовалась системная грамматика, реализованная в виде программ на различных специальных языках (PROGRAMMAR, Planner и др.). Суть системы «SHRDLU» - разбор с выделением признаков, таких как число, тип предложения и т.д., которые используются на лексическом и семантическом уровнях. При этом для каждого из языков требовался свой транслятор, что усложняло процесс трансляции.

На кафедре вычислительной техники ТТИ ЮФУ была разработана среда «Мультитранслятор» - гибкая и универсальная система продукционного типа. В число применений системы входит трансляция языков моделирования, языков описания аппаратуры и языков программирования высокого уровня.