Scientific journal
Fundamental research
ISSN 1812-7339
"Перечень" ВАК
ИФ РИНЦ = 1,674

NON-ANALYTICAL METHODS OF CALCULATIONS FOR MICROPROCESSORS

Bulatnikova I.N. 1 Gershunina N.N. 1
1 Federal state budgetary educational institution of higher professional education Kuban State Technologic University
The present article is devoted to the presentation of the design principles of the so-called non-analytical algorithms. They are characterized by the fact that they are not built along the analytical expressions of the essence of the transformation of information, and on the basis of model properties of mathematical objects (vectors, iterative processes, etc.). Their appearance is caused by the widespread availability of microprocessors, represent the requirement for the algorithms – the absence of operations of multiplications and divisions (the integrality of the algorithms). There is proposed development of a differential-iterative algorithms, including the well-known algorithm of Oranskiy and Reichenberg, made modifications to ensure the realization of a wide class of functional transformations. The total error of such algorithms (accuracy at the level of 10–12 bits) allows to successfully use them in microprocessor-based local automation devices.
microprocessors
fast integer algorithms
local automation devices
1. Bulatnikova I.N., Kljuchko V.I. i.dr. Informacionnye tehnologii s ispolzovaniem celochislennoj arifmetiki // Analiticheskij nauchno-tehnicheskij zhurnal «Geoinzhiniring», NIPI «Inzhgeo». 2011. no. 2(11). рр. 54–58.
2. Gershunina N.N. Chastikov A.P. i dr. Avtomatizirovannyj informacionno-vychislitelnyj punkt jekspress-analiza kachestva dlja pivo- i bezalkogolnyh proizvodstv // Izv. Vuzov. Pishhevaja tehnologija. 1999. no. 1. рр. 34–36.
3. Oranskij A.M. Apparatnye metody v cifrovoj vychislitelnoj tehnike. Minsk: Izd-vo BGU, 1977. 208 р.
4. A.s. 744595 SSSR, MKI2 G06F7/34. Cifrovoj funkcionalnyj preobrazovatel / A.M. Oranskij, A.L. Rejhenberg. Opubl. 30.06.1980 g. Bjul. no. 24.
5. Meggitt J.E. Pseudo division and pseudo multiplication processes // IBM J. Res. And Develop. 1962. Vol. 6. no. 2. рр. 220–226.
6. Volder J.E. The CORDIC trigonometric computing // The Trans. On Electric Corp. 1959. Vol. 8. no. 3. рр. 330–340.

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

Ранее все ЭВМ считали вдоль аналитического выражения реализуемой функции преобразования информации, т.е. повторяли человеческие расчеты по формулам. Отсюда обязательность операций (+ , –, ×, /). Но это не соответствовало идеологии МП (максимум быстродействия при минимуме аппаратурных затрат).

Уже в 60-х годах прошлого столетия появились первые быстродействующие алгоритмы неаналитических вычислений, сокращавших аппаратурные затраты. Это алгоритмы Волдера [6] и Меджитта [5], имевшие в русскоязычной технической литературе название «шаг за шагом» (от английского “step by step”). Они имели исключительно аппаратурное применение в быстродействующих специальных вычислителях (навигация, ракетное дело и др.). При всех преимуществах они имели ограниченный класс функций, реализуемых ими. Их развитие не происходило из-за сложности технической (аппаратурной) реализации. Будучи по сути разностно-итерационными алгоритмами (РИА), они требовали создания методологии проектирования новых функций. Один из авторов подобных РИА, А.М. Оранский, отмечает – «теория РИА разработана недостаточно, и синтез алгоритмов идет эвристическим путем» [3, с. 143].

В основе РИА лежат методы цифрового моделирования какого-либо математического или геометрического объекта (вращающийся вектор, как у [5, 6], или итерационный сходящийся процесс, конечным результатом которого будет искомая функция [3]). В последнем варианте – это будет геометрический объект в виде плоских фигур различной конфигурации.

Методы псевдоповоротов вектора

Это частный случай алгоритмов Волдера [6] и Меджитта [5]. В их основу заложена такая замечательная особенность: два комплексных числа вида (a + jb) и (1 ± j∙2–i), где i = 0, 1, 2, …, могут быть легко перемножены с применением только линейных операторов, так как умножения на 2–i заменяются арифметическими сдвигами

(a + jb)∙(1 ± j∙2–i) = (a ± b∙2–i) + j∙(b ± a∙2–i). (1)

Но эту процедуру (1) можно представить так: вектор (а, b) поворачивается на угол ±arctg 2–i и дополнительно удлиняется в bulatnik01.wmf раз.

Организовав слежение за текущим углом поворота вектора, можно получить координаты его конца, пропорциональные косинусу и синусу этого угла. И, наоборот, следя за достижением проекцией конца вектора на оси определенного значения х, можем получить угол, равный arcsin x или arсcos x. Вот этот алгоритм:

bulatnik02.wmf

Y0 = y; Yi = Yi–1 – Ei–1 2–(i–1)∙Xi–1; Yn → 0;

X0 = x; Xi = Xi–1 – Ei–1 2–(i–1)∙Yi–1;

bulatnik03.wmf (2)

Q0 = 0; Qi = Qi–1 – Ei–1 2–(i–1); bulatnik04.wmf

где i = 1, 2, …, n – номер итерации; n – разрядность чисел; bulatnik05.wmf

Нами разработана модификация РИА (2) для реализации на МП. За основу взят более точный алгоритм Меджитта, а второй этап позаимствован из алгоритма Волдера. Получается более точный и более быстрый РИА:

bulatnik06.wmf

Y0 = y; Yi+1 = 2(Yi – Ei–1∙Xi); Ym → 0;

X0 = x; Xi+1 = Xi + Ei–1 2–2i∙Yi;

bulatnik07.wmf (3)

Q0 = 0; Qi+1 = Qi + Ei–1 arctg 2–i;

bulatnik08.wmf

где i = 0, 1, 2,…, m – номер итерации; m – половинная разрядность чисел bulatnik09.wmf.

Обращаем внимание на то, что число итераций сокращено вдвое.

При всех достоинствах РИА (2) и (3) они имеют недостаток – необходимость наличия констант arctg 2–i.

Простой разностно-итерационный алгоритм

Он называется РИА квазиделения без восстановления остатка и квазиумножения [3]. В немного модернизированном нами (для расширения области сходимости) он имеет такой вид:

qi–1 = sign Wi–1sign y;

W0 = w; Wi = Wi–1 – qi–1∙2–i+1∙y; Wn → 0;

V0 = v; Vi = Vi–1 + qi–1∙2–i+1∙x;

bulatnik10.wmf (4)

где i = 1, 2, …, n – номер итерации; n – разрядность чисел.

Хотя он и называется самым простым, но его основные компоненты (строчки с итерационными выражениями) входят во многие другие более сложные РИА. Например, первая и вторая строки играют роль аддитивного разложения отношения bulatnik11.wmf:

bulatnik12.wmf (5)

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

Известен и другой – мультипликативный вид разложения bulatnik13.wmf (при w > y > 0):

bulatnik14.wmf

W0 = 2∙(w – y); Wi+1 = 2∙(Wi – qi∙Yi); (6)

Y0 = y; Yi+1 = Yi + qi∙2–i∙Yi,

где i = 0, 1, 2..., n – номер итерации; n – разрядность чисел.

В итоге получаем разложения bulatnik15.wmf в виде

bulatnik16.wmf (7)

которое используется в следующих итерационных выражениях, обеспечивающих различные функциональные преобразования (возведение в целую положительную степень отношения bulatnik17.wmf, взятие логарифма bulatnik18.wmf и др.).

Алгоритм Оранского и Рейхенберга

Он изобретен [4] для аппаратурной реализации и имеет такой вид (для х > 0, y > 0):

bulatnik19.wmf

X0 = x; Xi = Xi–1 – qi–1∙y∙2–i;

bulatnik20.wmf (8)

Y0 = y; Yi = Yi–1 + qi–1∙x∙2–i; Yn → Xn,

где i = 1, 2, ..., n – номер итерации; n – разрядность чисел.

РИА (8) имеет ограниченную возможность, он вычисляет одну единственную функцию bulatnik21.wmf от двух переменных.

С целью расширения области применимости РИА нами были произведены исследования его математической модели и на этой основе – модификация РИА [2].

qi–1 = sign (Xi–1 – Yi–1)∙sign (u + w);

X0 = x; Xi = Xi–1 – qi–1∙w∙2–i+1;

bulatnik22.wmf (9)

Y0 = y; Yi = Yi–1 + qi–1∙u∙2–i+1; Yn → Xn,

где i – то же самое, что и в (8).

Условие сходимости этого РИА (8) таковы:

bulatnik23.wmf (10)

где р (р ≥ 0) – минимальное целое число, обеспечивающее выполнение неравенства

2∙|u∙2p + w∙2p| > |x – y|. (11)

Величина, вычисляемая с помощью РИА (9), является средневзвешенной двух величин х и у, взятых с весами u и w. То есть это функция четырех переменных.

Расширение областей применения РИА

Оно состоит в замене исходных значений итерируемых величин некоторыми функциями одного или двух аргументов, которые сами просто вычисляются (т.е. без операций умножения и деления). То есть переходом к сложным функциям (суперпозициям функций) РИА значительно расширяют класс реализуемых функций. Например, простой РИА (4) сможет вычислять не только bulatnik24.wmf, но и такую, например, функцию – bulatnik25.wmf. Деля ее числитель на знаменатель (как многочлен на многочлен – «уголком»), получаем нужное представление для РИА (4).

bulatnik26.wmf (12)

Заменяя u = s + t + 1; w = – (4s + 1); y = s + t; x = t и подставляя их в качестве исходных данных для РИА (4), в итоге получаем сложную функцию

bulatnik27.wmf

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

Приведем пример таких преобразований для модифицированного РИА (9). Представим x, y, u, w так:

x = kx∙t + mx; w = kw∙t + mw;

y = ky∙t + my; u = ku∙t + mu. (13)

Тогда

bulatnik28.wmf (14)

где A = kx∙ku + ky∙kw;

В = kx∙mu + ku∙mx + ky∙mw + kw∙my;

С = mx∙mu + my∙mw;

D = ku + kw;

E = mu + mw.

Для того чтобы упростить предварительное вычисление x, y, u, w для заданного t, выберем ki (i Î {x, y, u, w}), равным 0, ±1; ±0,5; ±0,25; …. и т.д. Это позволит заменить умножение ki∙t арифметическим сдвигом вправо аргумента t c возможностью инвертирования знака результата, если знак у ki – минус.

Если же требуется решить обратную задачу: назначить такие ki и mi, чтобы Yn = Xn были равны требуемой функции F(t) на заданном интервале i ∈ (α, β), то находим одну из аппроксимаций F(t) в виде (14), т.е. соответствующий набор коэффициентов А, В, С, D, E.

Опираясь на них, составляем и решаем следующую систему уравнений:

kx ku + ky∙kw = γ∙A;

kx∙mu + ku∙mx + ky∙mw + kw∙my = γ∙B;

mx∙mu + my∙mw = γ∙C; (15)

ku + kw = γ∙D;

mu + mw = γ∙E,

где γ – технологический коэффициент, сокращающий дробь (14) до значений числителя и знаменателя, удобных для решения системы (15).

Авторами [2] разработан алгоритм и программы решения системы (15) на персональном компьютере с получением ki и mi (i ∈ {x, y, u, w}).

Например, для F(t) = tg(t), t ∈ (0, π/4) имеем такой набор коэффициентов ki и mi (i ∈ {x, y, u, w}), который позволяет вычислять функцию F(t) (14), максимально приближенную к tg(t) на указанном интервале

kx = 1; ky = –1; ku = 1; kw = 1/8;

mx = 0,041332; my = 1,000000;

mu = –1,502386; mw = 0,060741.

В таблице приведены абсолютные погрешности вычисления функции tg(t).

Абсолютная погрешность ∙103 при различных t

t (радиан)

0

0,08

0,16

0,24

0,32

0,44

0,56

0,68

0,78

tg(t)

0,944

0,873

0,731

0,345

0,223

0,452

0,510

0,310

0,259

Заметим, что в погрешность вошла и погрешность аппроксимации.

Преимущество микропроцессорной реализации функций по РИА (9) с заменой переменных по формулам (13) состоит в том, что подпрограмма вычислений различных функций одна и та же. Меняются только коэффициенты ki и mi. Кроме того, этот путь позволяет реализовать не только аналитически, но и таблично заданные функции.

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

Ограниченная точность предлагаемых РИА и их модификаций (обеспечивают точность в пределах 10–12 двоичных разрядов) не препятствует их использованию в микропроцессорных системах локальной автоматики. Микропроцессоры оперируют с входными данными от 10–12-разрядных аналого-цифровых преобразователей и выдают такой же точности выходные данные на цифро-аналоговые преобразователи и исполнительные органы управления [1].

Рецензенты:

Ключко В.И., д.т.н., профессор кафедры информационных систем и программирования Кубанского государственного технологического университета, г. Краснодар;

Анишин Н.С., д.т.н., профессор, Академия маркетинга и социально-информационных технологий, г. Краснодар.