Компьютер для операций с функциями

Компьютер для операций с математическими функциями (в отличие от обычного компьютера) оперирует с функциями на аппаратном уровне (то есть без программирования этих операций).^[1][2][3]

История

Вычислительная машина для операций с функциями была предложена и разработана Карцевым в 1967 году^[1]. В число операций этой вычислительной машины входили сложение, вычитание и умножение функций, сравнение функций, аналогичные операции над функцией и числом, отыскание максимума функций, вычисление неопределенного интеграла, вычисление определенного интеграла от производной двух функций, сдвиг функции по абсциссе и т. д. По архитектуре эта вычислительная машина являлась (пользуясь современной терминологией) векторным процессором. В ней использовался тот факт, что многие из этих операций могут быть истолкованы как известные операции над векторами: сложение и вычитание функций — как сложение и вычитание векторов, вычисление определенного интеграла от производной двух функций — как вычисление скалярного произведения двух векторов, сдвиг функций по абсциссе — как поворот вектора относительно осей координат и т. д.^[1] В 1966 году Хмельник предложил метод кодирования функций^[2] , то есть представления функции единым (для функции в целом) позиционным кодом. При этом указанные операции с функциями выполняются как уникальные машинные операции с такими кодами на единственном арифметическом устройстве^[3]

Позиционные коды функций одного аргумента^[2][3]

См. также: Позиционное кодирование (значения)

Основная идея

Позиционный код целого числа $A$ представляет собой запись цифр $\alpha$ этого числа в некоторой позиционной системе счисления, имеющую вид

$A = \alpha_{0} \alpha_{1} \dots \alpha_k \dots \alpha_{n}$

Такой код можно назвать линейным. В отличие от него позиционный код функции $F(x)$ одного аргумента $x$ имеет вид

$F(x) = \begin{pmatrix} \ & \ & \cdots \\ \ & \ & \alpha_{22} \cdots \alpha_{2k} \cdots \\ \ & \alpha_{11} & \alpha_{12} \cdots \alpha_{1k} \cdots \\ \alpha_{00} & \alpha_{01} & \alpha_{02} \cdots \alpha_{0k} \cdots \end{pmatrix}$

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

$A = \sum_{k=0}^{n} \alpha_k \rho^k$,.

где $\rho$ — основание данной системы счисления. Указанному позиционному коду функции одного аргумента соответствует двойная сумма вида

$F(x) = \sum_{k=0}^{n} \sum_{m=0}^{k} \alpha_{mk} R^ky^{k-m}(1-y)^m$,

где $R$ — целое положительное число, количество значений цифры $\alpha$, $y$ — определенная функция аргумента $x$.
Сложение позиционных кодов чисел связано с передачей переноса в старший разряд по схеме

$\alpha_{k} \longrightarrow \alpha_{k+1}$.

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

$\begin{pmatrix} \ \ & \alpha_{k+1,m+1} \\ \ \nearrow & \ \\ \alpha_{k,m} \longrightarrow & \alpha_{k+1,m} \end{pmatrix}$.

При этом один и тот же перенос передается одновременно в два старших разряда.

R-е треугольные коды

Треугольный код называется R-м (и обозначается как $TK_R$), если числа $\alpha_{mk}$ принимают значения из множества

$D_R = \{-r_1,-r_1+1,\dots, -1,0,1,\dots,r_2-1,r_2 \},$ где $r_1,\;r_2\geq 0$ и $R_{}^{} =r_1+r_2+1$.

Например, треугольный код является троичным $TK_3$, если $\alpha_{mk} \in (-1,0,1)$, и — четверичным $TK_4$, если $\alpha_{mk} \in (-2,-1,0,1)$.
Для R-х треугольных кодов справедливы следующие равенства:

$\begin{pmatrix} \ \ & 0 \\ \ \nearrow & \ \\ aR \longrightarrow & 0 \end{pmatrix}=\begin{pmatrix} \ \ & a \\ \ \nearrow & \ \\ 0 \longrightarrow & a \end{pmatrix}, \begin{pmatrix} \ \ & a \\ \ \nearrow & \ \\ 0 \longrightarrow & 0 \end{pmatrix}=\begin{pmatrix} \ \ & 0 \\ \ \nearrow & \ \\ aR \longrightarrow & -a \end{pmatrix}, \begin{pmatrix} \ \ & 0 \\ \ \nearrow & \ \\ 0 \longrightarrow & a \end{pmatrix}=\begin{pmatrix} \ \ & -a \\ \ \nearrow & \ \\ aR \longrightarrow & 0 \end{pmatrix}$,

где a — любое число. Существует $TK_R$ любого целого действительного числа. В частности, $TK_R(\alpha)=\alpha$. Также существует $TK_R$ любой функции вида $y^{k}$. В частности, $TK_R(y^{2})=(0\ 0\ 1)$.

Одноразрядное сложение

в R-х треугольных кодах состоит в том, что

• в данном $(mk)$-разряде определяется сумма $S_{mk}^{}$ слагаемых разрядов $\alpha_{mk}, \ \beta_{mk}$ и двух переносов $p_{m,k-1}, \ p_{m-1,k-1}$, поступивших в данный разряд слева, то есть

$S_{mk}^{}=\alpha_{mk}+\beta_{mk}+p_{m,k-1}+p_{m-1,k-1}$,

• эта сумма представляется в виде $S_{mk}^{}=\sigma_{mk}+Rp_{mk}$, где $\sigma_{mk} \in D_R$,
• $\sigma_{mk}$ записывается в $(mk)$-разряд суммарного кода, а перенос $p_{mk}$ из данного разряда передается в $(m,k+1)$-разряд и $(m+1,k+1)$-разряд.

Эта процедура описывается (как и при одноразрядном сложении чисел) таблицей одноразрядного сложения, где должны присутствовать все значения слагаемых $\alpha_{mk} \in D_R$ и $\beta_{mk} \in D_R$ и все значения переносов, возникающих при разложении суммы $S_{mk}^{}=\sigma_{mk}+Rp_{mk}$. Такая таблица может быть синтезирована при $R>2.$
Ниже приведена таблица одноразрядного сложения при $R=3$:

Smk	TK(Smk)		$\sigma_{mk}^{}$	$p_{mk}^{}$
.	.	0	.	.
0	0	0	0	0
.	.	0	.	.
1	1	0	1	0
.	.	0	.	.
(-1)	(-1)	0	(-1)	0
.	.	1	.	.
2	(-1)	1	(-1)	1
.	.	1	.	.
3	0	1	0	1
.	.	1	.	.
4	1	1	1	1
.	.	(-1)	.	.
(-2)	1	(-1)	1	(-1)
.	.	(-1)	.	.
(-3)	0	(-1)	0	(-1)
.	.	(-1)	.	.
(-4)	(-1)	(-1)	(-1)	(-1)

Одноразрядное вычитание

в R-х треугольных кодах отличается от одноразрядного сложения только тем, что в данном $(mk)$-разряде величина $S_{mk}^{}$ определяется по формуле

$S_{mk}^{}=\alpha_{mk}-\beta_{mk}+p_{m,k-1}+p_{m-1,k-1}$.

Одноразрядное деление на параметр R

в R-х треугольных кодах основано на использовании соотношения

$\begin{pmatrix} \ \ & a \\ \ \nearrow & \ \\ 0 \longrightarrow & 0 \end{pmatrix}=\begin{pmatrix} \ \ & 0 \\ \ \nearrow & \ \\ aR \longrightarrow & -a \end{pmatrix}$,

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

• в данном $(mk)$-разряде определяется сумма

$S_{mk}^{}=\alpha_{mk}/R-p_{m+1,k}/R+p_{m+1,k+1}$,

• эта сумма представляется в виде $S_{mk}^{}=\sigma_{mk}+p_{mk}/R$, где $\sigma_{mk} \in D_R$,
• $\sigma_{mk}$ записывается в $(mk)$-разряд результирующего кода, а перенос $p_{mk}$ из данного разряда передается в $(m-1,k-1)$-разряд и $(m-1,k)$-разряд.

Эта процедура описывается таблицей одноразрядного деления на параметр R, где должны присутствовать все значения слагаемых и все значения переносов, возникающих при разложении суммы $S_{mk}^{}=\sigma_{mk}+p_{mk}/R$. Такая таблица может быть синтезирована при $R>2.$
Ниже приведена таблица одноразрядного деления на параметр R при $R=3$:

Smk	TK(Smk)		$\sigma_{mk}^{}$	$p_{mk}^{}$
.	.	0	.	.
0	0	0	0	0
.	.	1	.	.
1	0	0	1	0
.	.	(-1)	.	.
(-1)	0	0	(-1)	0
.	.	0	.	.
1/3	1	(-1/3)	0	1
.	.	1	.	.
2/3	(-1)	1/3	1	(-1)
.	.	1	.	.
4/3	1	(-1/3)	1	1
.	.	2	.	.
5/3	(-1)	1/3	2	(-1)
.	.	0	.	.
(-1/3)	(-1)	1/3	0	(-1)
.	.	(-1)	.	.
(-2/3)	1	(-1/3)	(-1)	1
.	.	(-1)	.	.
(-4/3)	(-1)	1/3	(-1)	(-1)
.	.	(-2)	.	.
(-5/3)	1	(-1/3)	(-2)	1

Сложение и вычитание

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

Умножение

R-х треугольных кодов. Умножение некоторого кода $TK_R'^{}$ на $(mk)$-разряд другого кода $TK_R''^{}$ заключается в $(mk)$-сдвиге кода $TK_R'^{}$, то есть сдвиге его на k столбцов влево и на m строк вверх. Умножение кодов $TK_R'^{}$ и $TK_R''^{}$ заключается в последовательных $(mk)$-сдвигах кода $TK_R'^{}$ и сложениях сдвинутого кода $TK_R'^{}$ с частичным произведением (как и в позиционных кодах чисел).

Дифференцирование

R-х треугольных кодов. Производная функции $F(x)$, определенной выше,

$\frac{\partial F(x)}{\partial x}=\frac{\partial y}{\partial x} \frac{\partial F(x)}{\partial y}$.

Поэтому дифференцирование треугольных кодов функции $F(x)$ заключается в определении треугольного кода частной производной $\frac{\partial F(x)}{\partial y}$ и умножении его на известный треугольный код производной $\frac{\partial y}{\partial x}$. Определение треугольного кода частной производной $\frac{\partial F(x)}{\partial y}$ основано на соотношении

$\frac{\partial }{\partial x} \begin{pmatrix} \ & \ & 0 \\ \ & 0 & \alpha_{mk} \\ 0 & 0 & 0 \end{pmatrix}=\begin{pmatrix} \ & \ & (k-m) \alpha_{mk} \\ \ & 0 & (k-2m) \alpha_{mk} \\ 0 & 0 & (-m) \alpha_{mk} \end{pmatrix}$.

Cпособ дифференцирования заключается в организации переносов из mk-разряда в (m+1,k)-разряд и в (m-1,k)-разряд, а их суммирование в данном разряде производится аналогично одноразрядному сложению.

Кодирование и декодирование

R-х треугольных кодов. Функция, представленная рядом вида

$F(x) = \sum_{k=0}^{n} A_k y^k$,

с целыми коэффициентами $A_k$, может быть представлена R-м треугольным кодом, так как эти коэффициенты и функции $y^k$ имеют R-е треугольные коды (о чем сказано в начале раздела). С другой стороны, R-й треугольный код может быть представлен указанным рядом, так как любое слагаемое $\alpha_{mk} R^ky^k(1-y)^m$ в позиционном разложении функции (соответствующем этому коду) может быть представлено таким же рядом.

Укорочение

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

Масштабный коэффициент

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

Позиционные коды функций многих аргументов^[4]

Рис. 1. Пирамидальный код функции двух аргументов

Позиционный код функции двух аргументов изображен на рис. 1. Ему соответствует тройная сумма вида

$F(x,v) = \sum_{k=0}^{n} \sum_{m1=0}^{k} \sum_{m2=0}^{k} \alpha_{m1,m2,k} R^k y^{k-m1}(1-y)^{m1} z^{k-m2}(1-z)^{m2}$,

где $R$ — целое положительное число, количество значений цифры $\alpha_{m1,m2,k}$, а $y(x), ~ z(v)$ — определенные функции аргументов $x, ~ v$ соответственно. На рис. 1 узлы соответствуют цифрам $\alpha_{m1,m2,k}$, а в кружках показаны значения индексов ${m1,m2,k}$ соответствующей цифры. Позиционный код функции двух аргументов называется пирамидальным. Позиционный код называется R-м (и обозначается как $PK_R$), если числа $\alpha_{m1,m2,k}$ принимают значения из множества $D_R$. При сложении кодов $PK_R$ перенос распространяется в четыре разряда и поэтому $R \geq 7$.

Позиционному коду функции нескольких аргументов соответствует сумма вида

$F(x_1,\ldots, x_i, \ldots, x_a ) = \sum_{k=0}^{n} \sum_{m_1=0}^{k} \ldots \sum_{m_a=0}^{k} (\alpha_{m_1, \ldots, m_a,k} R^k \prod^a_{i=1}(y_i^{k-m_i}(1-y_i)^{m_i}))$,

Рис. 2. Гиперпирамидальный код функции трех аргументов

где $R$ — целое положительное число, количество значений цифры $\alpha_{m_1, \ldots, m_a,k}$, а $y_i(x_i)$ — определенные функции аргументов $x_i$. Позиционный код функции нескольких аргументов называется гиперпирамидальным. На рис. 2 показан для примера позиционный гиперпирамидальный код функции трех аргументов. В нем узлы соответствуют цифрам $\alpha_{m1,m2,m3,k}$, а в кружках показаны значения индексов ${m1,m2,m3,k}$ соответствующей цифры. Позиционный гиперпирамидальный код называется R-м (и обозначается как $GPK_R$), если числа $\alpha_{m_1, \ldots, m_a,k}$ принимают значения из множества $D_R$. При сложении кодов $GPK_R$ перенос распространяется в a-мерный куб, содержащий $2^a$ разрядов и поэтому $R \geq (2^{a-1}-1)$.

Примечания

1. ↑ ^{1 2 3} Малиновский Б. Н. История вычислительной техники в лицах. — Киев, Фирма "КИТ", ПТОО "АСК". — 1995. — ISBN 5-7707-6131-8
2. ↑ ^{1 2 3} Хмельник С. И. Кодирование функций // Кибернетика, АН УССР. — 1966. — Т. 4.
3. ↑ ^{1 2 3} Хмельник С. И. Компьютерная арифметика функций. Алгоритмы и аппаратура. — Mathematics in Computers. — Россия-Израиль, 2004. — ISBN 978-0-557-07520-1
4. ↑ Хмельник С. И. Несколько типов позиционных кодов функций // Кибернетика, АН УССР. — 1970. — Т. 5.