# Device for determination of number signs in system of remainder classes

FIELD: physics.

SUBSTANCE: device comprises the set of input registers for storage of number composed by the code of symmetric system of remainder classes. Permanent registers are used for storage of interval-position characteristics of constant, i.e., a positive number in symmetric system of remainder classes. Besides, it incorporates the unit for computation of interval-position characteristics and unit to test for accuracy of interval-position characteristics. Also, it includes comparator of interval-position characteristics and two-way binary decoder.

EFFECT: higher response and control over accuracy of sign definition.

3 dwg

The invention relates to computing and is designed to perform the operation of determining the sign of the number represented in the system of residual classes.

A device for determining the sign of the number represented in the system of residual classes (A. S. SU # 1552181, BI No. 11, 23.03.1990), which comprises a unit 1 for determining the number of the interval, the group of information inputs of the device 2, first 3 and second 4 of the comparator circuit, the first 5 and second 6 elements OR, the first 7 and second 8 inputs the constants of the device, the first 9 and second 10 output device. The device is based on identifying the affiliation of the interval in which is a number expressed in the system of residual classes (JUICE), to the group of positive or negative intervals on this basis, the JUICE of p_{i}that broken full modular range [0, P-1], where P is the product of all of the bases JUICE. The disadvantage of this device is the biggest challenge and low performance because to determine the sign of the number you want to work with (P/p_{i})-bit integers.

The closest to the claimed invention is a device for determining the sign of the modular number based on the approximate method (A. S. RU # 2503995, BI # 1, 10.01.2014) containing the input registers for the modules p_{1}p_{2}, ..., p_{n}for temporary storage of bits �OK
parallel adder for summing

The technical result of the claimed device for determining the signs of the numbers in the system of residual classes is to improve the performance compared to devices based on the exact methods, and ensuring control of correctness of determination of the sign. Presents the provisions provided through the use of a new interval-positional characteristics of modular arithmetic, which approximates with two sided�n the relative magnitude of the numbers in the modular view.

Device description: the basis for operation of the claimed device for determining the signs of the numbers in the residue number system is a new method of interval estimation of the relative value of modular code. Will consider it.

Let the basis set JUICE set pairwise coprime odd modules p_{1}p_{2}, ..., p_{n}and_{1}, x_{2}, ..., x_{n}and

where B_{1}B_{2}, ..., B_{n}orthogonal bases of JUICE, each i-th of which the essence is the product of P_{i}=P/p_{i}and_{i}modulo p_{i}).

The sign of the number in the system of residual classes can be introduced in various ways. The most common way is to use a symmetric JUICE. In this case, if P is an odd number, then the entire numeric range [0, P-1] is split into two equal intervals [0, (P-1)/2] and [(P+1)/2, P-1], and positive numbers are represented in the younger interval and negative at older. Thus, the problem of determining the sign of X, represented in symmetric JUICE is determining its position relative to the split point (P-1)/2. To solve this problem requires the estimation of the positional value of the number X. Since the computation of its absolute value (1) time-consuming because each term has a value of order of the product modules P, and its length can substantially exceed the size of the machine word, the claimed device, also known as the analogue of (A. S. RU # 2503995, BI # 1, 10.01.2014) based on an assessment of relative values.

The relative magnitude of E(X/P) of the modular number X is the ratio of its positional integer Zn�tion to the work of all the modules P, that is,

Since the exact rational value of E(X/P), varying in the interval [0, 1), in General not representable in a computer with limited bit net, there is a task of its approximation. To solve this problem, we use a new interval-positional characteristic (TOC)

The boundaries of the TOC are represented as binary floating point numbers, and when calculating lower bounds is always rounded up to the bitness of the machine word with a negative ("down"), and when calculating the upper bound is rounded up to the bitness of the machine word in abundance ("up"). This ensures the inclusion I(X/P)∈E(X/P), that is accurate relative value (2) modular number X is localized it to the TOC. The lower bound is calculated by the formula

and the upper limit, by the formula

where x_{i}- the i-th residue number X, | |_{1}- fractional part of the argument, and the arrows correspond to directed rounding up to the bitness of the machine word in the calculation and summation of terms: ↓ - rounding with the disadvantage, ↑ - rounding to excess.

In the consistent case, to calculate formulas (3) and (4) requires O(n) elementary operations floating-point parallel O(log n). For comparison, the known conversion algorithms the code system of residual classes in the system with mixed bases require, respectively, O(n^{2}) and O(n) operations.

Absolute error TOC characterizes its diameter, equal to the difference between boundaries

Let n be the dimension of the basis of the JUICE, and k is the number of bits in the mantissas in the binary representation of the boundaries of the TOC, then in the calculation according to the formulas (3) and (4) diameter (5) does not exceed n2^{-k}. If necessary, a more accurate calculation of the TOC instead of the formulas (3) and (4) can be used the original high-accuracy algorithm (Isupov, K. S., an Algorithm for computing interval-positional characteristics to perform non-modular operations in residue number systems // Bulletin of SUSU. A series of Computer technologies, control and radio electronics". - 2014. - Vol. 14, No. 1. - P. 89-97). This algorithm is based on fast and error-free division of boundaries TOC, presents the normalized binary floating point numbers, the natural powers of two and allows us to calculate the TOC with the relative error, defined for X≠0 the ratio of the diameter (5) to the exact relative value (2), not exceeding a priori specified limit ε, thereby to obtain accurate information on the size of the numbers in the modular representation without the use of multi-bit arithmetic and time-consuming conversion in a positional system.

Due to the direction of the rounding error arising in the calculation of the boundaries of the TOC, lead only to increase in diameter (5), not rendering in General influence on the property of the inclusion E(X/P)∈I(X/P). But because the area W�of acini boundaries is limited to the interval [0,
1), in some cases this property may be violated. This occurs when the number X is very small relative to P, or Vice versa, is in the immediate vicinity of the point P-1. In the first case incorrectly calculated the lower bound of the TOC, and the second upper. In any case, diam I(X/P)<0, i.e. the lower bound greater than the upper. This TOC is called wrong by Kougeru or just wrong. The first formal condition for a correct determination of the sign - correct TOC number X, represented in symmetric JUICE. If this condition is satisfied, then the final conclusion about the correctness of the sign is formulated based on the review of the second formal condition, which consists in the absence of intersection (collision) TOC

If the diameter (5) of this interval is less than zero, the TOC does not intersect the standard set-theoretic sense, i.e., do not contain common points. In the degenerate case it may be that X=(P-1)/2. Therefore, the second formal condition for a correct computation of the sign of the number is defined as follows:

Let the symmetric JUICE modules with p_{1}p_{2}, ..., p_{n}given a number X=〈x_{1}, x_{2}, ..., x_{n}〉. The algorithm for determining the sign sgn(X) of X based on the use of technology interval-positional characteristics is formulated as follows.

ALGORITHM.

Step 0. Pre-calculated and stored in computer memory TOC

Step 1. For the number X is calculated

Step 2. Checked the first formal condition for a correct determination of the sign: if

Step 3. If

Step 4. If

Step 5. If improving the accuracy of calculating the TOC in step 1 is not feasible within the capacity of the used data formats, you must convert the number X from the JUICE in the numeral system with mixed bases to opredelit his mark on the basis of comparison of numbers obtained politicheskogo code with the corresponding figures calculated in advance politicheskogo code number (P-1)/2, or to generate and output a signal of the inability to determine the sign of X due to insufficient accuracy of his calculations of the TOC. The algorithm thus terminates.

EXAMPLE.

You want to determine the sign of the modular X=〈6, 8, 10, 1〉, presented in a symmetrical JUICE.

1. Calculate the constants:

- a set of weights for orthogonal bases(7):{6, 5, 9, 10}.

2. Calculated TOC number X by the formulas (3) and (4) rounded up to two digits

Thus, the obtained TOC I(X/P)=[0,52, 0,56], which is correct, so is the first formal condition for a correct determination of the sign of the number is made.

3. The condition$$$\stackrel{}{X/P}\le \frac{P-1}{\underset{\_}{2P}}$$$not performed (0,56>0,49), proceed to the next step.

4. Compare the opposite border of the TOC: 0,52>0,50 therefore, X is a negative number in the symmetry�hexadecimal JUICE and sgn(X)=1.

5. Checking: P=9009, (P-1)/2=4504, convert to the decimal system gives X=4850. Thus, the number X lies in the second half of the full range, therefore, is negative in the symmetric residue number system.

A diagram of the inventive device for determining the signs of the numbers in the system of residual classes, functioning in accordance with the presented algorithm, shown in Fig.2. The device contains a group of input registers 1 to store the number, the sign of which it is necessary to define non-volatile registers 2, 3 storage respectively lower

The work of the proposed device for determining the signs of the numbers in the system of residual classes is as follows. In advance and once the computed interval-positional characteristic