Computer for operations with functions explained

Within computer engineering and computer science, a computer for operations with (mathematical) functions (unlike the usual computer) operates with functions at the hardware level (i.e. without programming these operations).^[1] ^[2] ^[3]

History

A computing machine for operations with functions was presented and developed by Mikhail Kartsev in 1967.^[1] Among the operations of this computing machine were the functions addition, subtraction and multiplication, functions comparison, the same operations between a function and a number, finding the function maximum, computing indefinite integral, computing definite integral of derivative of two functions, derivative of two functions, shift of a function along the X-axis etc. By its architecture this computing machine was (using the modern terminology) a vector processor or array processor, a central processing unit (CPU) that implements an instruction set containing instructions that operate on one-dimensional arrays of data called vectors. In it there has been used the fact that many of these operations may be interpreted as the known operation on vectors: addition and subtraction of functions - as addition and subtraction of vectors, computing a definite integral of two functions derivative— as computing the vector product of two vectors, function shift along the X-axis – as vector rotation about axes, etc.^[1] In 1966 Khmelnik had proposed a functions coding method, i.e. the functions representation by a "uniform" (for a function as a whole) positional code. And so the mentioned operations with functions are performed as unique computer operations with such codes on a "single" arithmetic unit.

Positional codes of one-variable functions

Source:

The main idea

The positional code of an integer number

is a numeral notation of digits

\alpha

in a certain positional number system of the form

A=\alpha₀\alpha₁...\alpha_k...\alpha_n

.Such code may be called "linear". Unlike it a positional code of one-variable

function

F(x)

has the form:

F(x)=\begin{pmatrix} & & … \ & &\alpha₂₂ … \alpha_2k … \ &\alpha₁₁&\alpha₁₂ … \alpha_1k … \ \alpha₀₀&\alpha₀₁&\alpha₀₂ … \alpha_0k … \end{pmatrix}

and so it is flat and "triangular", as the digits in it comprise a triangle.

The value of the positional number

above is that of the sum

	n
\sum
	k=0

\alpha_k\rho^k

,where

\rho

is the radix of the said number system. The positional code of a one-variable function correspond to a 'double' code of the form

F(x)=

	n
\sum
	k=0

	k
\sum
	m=0

\alpha_mkR^ky^k-m(1-y)^m

,where

is an integer positive number, quantity of values that taken

\alpha

, and

is a certain function of argument

Addition of positional codes of numbers is associated with the carry transfer to a higher digit according to the scheme

\alpha_k\longrightarrow\alpha_k+1

.Addition of positional codes of one-variable functions is also associated with the carry transfer to higher digits according to the scheme:

\begin{pmatrix} &\alpha_k+1,m+1\ \nearrow& \ \alpha_k,m\longrightarrow&\alpha_k+1,m\end{pmatrix}

.Here the same transfer is carried simultaneously to two higher digits.

R-nary triangular code

A triangular code is called R-nary (and is denoted as

TK_R

), if the numbers

\alpha_mk

take their values from the set

D_R=\{-r_1,-r_1+1,...,-1,0,1,...,r_2-1,r₂\}

, where

r_1, r_2\geq0

and


R

=r_1+r₂₊₁

.For example, a triangular code is a ternary code

TK₃

, if

\alpha_mk\in(-1,0,1)

, and quaternary

TK₄

, if

\alpha_mk\in(-2,-1,0,1)

.
For R-nary triangular codes the following equalities are valid:

\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}

,where

is an arbitrary number. There exists

TK_R

of an arbitrary integer real number. In particular,

TK_{R(\alpha)=\alpha}

. Also there exists

TK_R

of any function of the form

y^k

. For instance,

	2
TK
	R(y

)=(0 0 1)

Single-digit addition

in R-nary triangular codes consists in the following:

in the given

(mk)

-digit there is determined the sum


S
	mk

of the digits that are being added

\alpha_mk, \beta_mk

and two carries

p_m,k-1, p_m-1,k-1

, transferred into this digit from the left, i.e.


S
	mk

=\alpha_mk+\beta_mk+p_m,k-1+p_m-1,k-1

this sum is presented in the form


S
	mk

=\sigma_mk+Rp_mk

, where

\sigma_mk\inD_R

\sigma_mk

is written in the

(mk)

-digit of summary code, and the carry

p_mk

from the given digit is carried into

(m,k+1)

-digit and

(m+1,k+1)

—digit.This procedure is described (as also for one-digit addition of the numbers) by a table of one-digit addition, where all the values of the terms

\alpha_mk\inD_R

and

\beta_mk\inD_R

must be present and all the values of carries appearing at decomposition of the sum


S
	mk

=\sigma_mk+Rp_mk

. Such a table may be synthesized for

R>2.

Below we have written the table of one-digit addition for

R=3

Smk

TK(Smk)


\sigma
	mk


p
	mk

(-1)

(-2)

(-1)

(-3)

(-1)

(-4)

(-1)

One-digit subtraction

in R-nary triangular codes differs from the one-digit addition only by the fact that in the given

(mk)

-digit the value


S
	mk

is determined by the formula


S
	mk

=\alpha_mk-\beta_mk+p_m,k-1+p_m-1,k-1

One-digit division by the parameter R

in R-nary triangular codes is based on using the correlation:

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

,from this it follows that the division of each digit causes carries into two lowest digits. Hence, the digits result in this operation is a sum of the quotient from the division of this digit by R and two carries from two highest digits. Thus, when divided by parameter R

in the given

(mk)

-digit the following sum is determined


S
	mk

=\alpha_mk/R-p_m+1,k/R+p_m+1,k+1

this sum is presented as


S
	mk

=\sigma_mk+p_mk/R

, where

\sigma_mk\inD_R

\sigma_mk

is written into

(mk)

—digit of the resulting code, and carry

p_mk

from the given digit is transferred into the

(m-1,k-1)

-digit and

(m-1,k)

-digit.This procedure is described by the table of one-digit division by parameter R, where all the values of terms and all values of carries, appearing at the decomposition of the sum


S
	mk

=\sigma_mk+p_mk/R

, must be present. Such table may be synthesized for

R>2.

Below the table will be given for the one-digit division by the parameter R for

R=3

Smk

TK(Smk)


\sigma
	mk


p
	mk

(-1)

1/3

(-1/3)

2/3

(-1)

1/3

(-1)

4/3

(-1/3)

5/3

(-1)

1/3

(-1)

(-1/3)

(-1)

1/3

(-1)

(-2/3)

(-1/3)

(-1)

(-4/3)

(-1)

1/3

(-1)

(-2)

(-5/3)

(-1/3)

(-2)

Addition and subtraction

of R-nary triangular codes consists (as in positional codes of numbers) in subsequently performed one-digit operations. Mind that the one-digit operations in all digits of each column are performed simultaneously.

Multiplication

of R-nary triangular codes. Multiplication of a code


TK
	R'

(mk)

-digit of another code


TK
	R''

consists in

(mk)

-shift of the code


TK
	R'

, i.e. its shift k columns left and m rows up. Multiplication of codes


TK
	R'

and


TK
	R''

consists in subsequent

(mk)

-shifts of the code


TK
	R'

and addition of the shifted code


TK
	R'

with the part-product (as in the positional codes of numbers).

Derivation

of R-nary triangular codes. The derivative of function

F(x)

, defined above, is

	\partialF(x)	=
	\partialx

	\partialy
	\partialx

	\partialF(x)
	\partialy

.So the derivation of triangular codes of a function

F(x)

consists in determining the triangular code of the partial derivative

	\partialF(x)
	\partialy

and its multiplication by the known triangular code of the derivative

	\partialy
	\partialx

. The determination of the triangular code of the partial derivative

	\partialF(x)
	\partialy

is based on the correlation

	\partial
	\partialx

\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}

.The derivation method consists of organizing carries from mk-digit into (m+1,k)-digit and into (m-1,k)-digit, and their summing in the given digit is performed in the same way as in one-digit addition.

Coding and decoding

of R-nary triangular codes. A function represented by series of the form

F(x)=

	n
\sum
	k=0

A_ky^k

,with integer coefficients

A_k

, may be represented by R-nary triangular codes, for these coefficients and functions

y^k

have R-nary triangular codes (which was mentioned in the beginning of the section). On the other hand, R-nary triangular code may be represented by the said series, as any term

\alpha_mkR^ky^k(1-y)^m

in the positional expansion of the function (corresponding to this code) may be represented by a similar series.

Truncation

of R-nary triangular codes. This is the name of an operation of reducing the number of "non"-zero columns. The necessity of truncation appears at the emergence of carries beyond the digit net. The truncation consists in division by parameter R. All coefficients of the series represented by the code are reduced R times, and the fractional parts of these coefficients are discarded. The first term of the series is also discarded. Such reduction is acceptable if it is known that the series of functions converge. Truncation consists in subsequently performed one-digit operations of division by parameter R. The one-digit operations in all the digits of a row are performed simultaneously, and the carries from lower row are discarded.

Scale factor

R-nary triangular code is accompanied by a scale factor M, similar to exponent for floating-point number. Factor M permits to display all coefficients of the coded series as integer numbers. Factor M is multiplied by R at the code truncation. For addition factors M are aligned, to do so one of added codes must be truncated. For multiplication the factors M are also multiplied.

Positional code for functions of many variables

Source:^[4]

Positional code for function of two variables is depicted on Figure 1. It corresponds to a "triple" sum of the form::

F(x,v)=

	n
\sum
	k=0

	k
\sum
	m1=0

	k
\sum
	m2=0

\alpha_m1,m2,kR^ky^k-m1(1-y)^m1z^k-m2(1-z)^m2

,
where

is an integer positive number, number of values of the figure

\alpha_m1,m2,k

, and

y(x),~z(v)

— certain functions of arguments

x,~v

correspondingly. On Figure 1 the nodes correspond to digits

\alpha_m1,m2,k

, and in the circles the values of indexes

{m1,m2,k}

of the corresponding digit are shown. The positional code of the function of two variables is called "pyramidal". Positional code is called R-nary (and is denoted as

PK_R

), if the numbers

\alpha_m1,m2,k

assume the values from the set

D_R

. At the addition of the codes

PK_R

the carry extends to four digits and hence

R\geq7

A positional code for the function from several variables corresponds to a sum of the form

F(x_1,\ldots,x_i,\ldots,x_a)=

	n
\sum
	k=0

	k
\sum
	m₁₌₀

\ldots

	k
\sum
	m_a=0

(\alpha
	m_1,\ldots,m_a,k

R^k

	a
\prod
	i=1

	k-m_i
(y
	i

	m_i
(1-y
	i)

))

where

is an integer positive number, number of values of the digit

\alpha
	m_1,\ldots,m_a,k

, and

y_i(x_i)

certain functions of arguments

x_i

. A positional code of a function of several variables is called "hyperpyramidal". Of Figure 2 is depicted for example a positional hyperpyramidal code of a function of three variables. On it the nodes correspond to the digits

\alpha_m1,m2,m3,k

, and the circles contain the values of indexes

{m1,m2,m3,k}

of the corresponding digit. A positional hyperpyramidal code is called R-nary (and is denoted as

GPK_R

), if the numbers

\alpha
	m_1,\ldots,m_a,k

assume the values from the set

D_R

. At the codes addition

GPK_R

the carry extends on a-dimensional cube, containing

2^a

digits, and hence

R\geq(2^a-1-1)

Notes and References

Book: Malinovsky, B.N. . The history of computer technology in their faces (in Russian) . Firm "KIT" . Kiew . 1995 . 5-7707-6131-8 . (see also here http://www.sigcis.org/files/SIGCISMC2010_001.pdf and english version here)
Khmelnik . S.I. . Coding of functions . Cybernetics, USSR Academy of Sciences . 1966 . 4 . (see also here in Russian)
Book: Khmelnik, S.I. . Computer Arithmetic of Functions. Algorithms and Hardware Design . Mathematics in Computers . Israel . 2004 . 978-0-557-07520-1 . (see also here in Russian)
Khmelnik . S.I. . Several types of positional functions codes . Cybernetics, USSR Academy of Sciences . 1970 . 5 . (see also here in Russian)

Computer for operations with functions explained

History

Positional codes of one-variable functions

The main idea

R-nary triangular code

Single-digit addition

One-digit subtraction

One-digit division by the parameter R

Addition and subtraction

Multiplication

Derivation

Coding and decoding

Truncation

Scale factor

Positional code for functions of many variables

See also

Notes and References