JPH07248902A - Floating-point arithmetic unit and its error correction method, linear programming problem optimizing unit and its optimal solution - Google Patents

Abstract

(57) [Summary] [Objective] Regarding the floating-point arithmetic unit and its error correction method, and the linear programming problem optimizing unit equipped with the floating-point arithmetic unit and its optimum solution finding method, the influence of the error of the arithmetic result follows. The purpose is not to affect the calculation of. [Structure] Exponent holding unit A (10) for normalized floating point numbers,
Exponent holding part B (13) of normalized floating point number of operation result,
The threshold value holding unit (11) that holds the threshold value of the criterion for determining whether or not to correct the calculation result is compared with the comparison result of the exponent before the calculation and the index after the calculation and the threshold value to correct the calculation result. An exponent comparison unit (12) for deciding whether to perform or not and an operation result changing unit (14) for correcting the operation result based on the comparison result of the exponent comparison unit (12) If the comparison result of the exponent after the calculation is larger than the threshold value, the calculation result is corrected to 0.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a floating point arithmetic unit, an error correction method therefor, a linear programming problem optimizing apparatus equipped with the floating point arithmetic unit, and a method for finding an optimum solution thereof.

When floating-point arithmetic is performed by a computer, an error may occur due to the finite number of calculation digits. In particular, the linear programming problem optimizer requires a huge amount of floating-point arithmetic to obtain an optimal solution, and therefore the above numerical errors are accumulated in the process, so that the calculation time increases due to an increase in the number of sweeps. Becoming longer,
It often happens that an infinite loop occurs and does not converge to the optimum solution (sweeping will be described later).

[0003]

2. Description of the Related Art Conventionally, in order to avoid such an error-based obstacle, when a sweep point is selected, a sweep point that does not generate an error is selected as much as possible. Further, when an error occurs, the rounding process correction is performed with a predetermined small value (tolerance value) as a boundary so that a small value equal to or smaller than a predetermined value is set to 0.

A method of obtaining an optimum solution of a linear programming problem by the simplex method will be described with reference to FIGS. 7 and 8. The linear programming problem is shown in Fig. 7 (a).
At x, the solution that maximizes z of the objective function, x ₁ , x
_This is a problem of finding ₂ , ..., X _k .

Here, as shown in FIG. 7B, a slack variable is introduced to form a standard simultaneous equation (for the slack variable, see the example). At this time, d ₁ ≧ 0 , D
₂ ≧ 0, ..., D _m ≧ 0.

[0006] simplex method, as shown in FIG. 7 at this time _{(c), x 1, x} 2, ···, finding an optimal solution by performing the following operations in a matrix to make the coefficient of x _n and a constant term Is the way.

If there is no negative component in steps 1 c ₁ , c ₂ , ..., C _{n ,} it is already an optimal solution _,
The process ends. If there is a negative component _, its absolute value is the maximum. Let it be c _s .

Step 2 In the s-th column, a _is > 0 a
ask for all _is . Step 3 For a _is obtained in Step 2, d _i / a
Calculate _is and take the smallest one. When there are two or more minimum ones, any one may be used. Let it be _ars .

Step 4 Perform pivot deformation with a _rs as the pivot and return to step 1 (for the pivot deformation, refer to the example). The above method will be described with reference to FIG.

Based on the constraint condition of FIG. 8 (a), x and y that maximize the objective function are obtained. Introduce the slack variables (x ₃ , x ₄ ) into the problem expression (a) to make it a standard form, and z
Let also be a variable, and obtain the simultaneous equations in Fig. 8 (b).

Therefore, a matrix consisting of coefficients of x ₁ , x ₂ , x ₃ , and x ₄ and a constant term is created (FIG. 8 (c)). Figure 8 (c)
Step 1 is performed on the matrix of.

C _s is c ₂ = -4 of the (3,2) component. The one in the second column that is positive in step 2 is a ₁₂
= 1 and a ₂₂ = 3. In step 3, 20/1 = 20
And 32/3 = 10.66 ... Since 32/3 is smaller, a _rs = a ₂₂ is set as the pivot.

In step 4, a matrix of FIG. 8 (d) is obtained by performing pivot transformation with a ₂₂ as the pivot (pivot transformation is performed by pivoting in the column with the pivoted element a ₂₂ as shown in (d)). This is a transformation in which the elements are 1 and the others are 0. This process is called sweeping).

Now, return to step 1. c ₁ = -1 /
Since 3 is a negative term, the process proceeds to step 2. a ₁₁ = 4 /
3> 0 and a ₂₁ = 2/3> 0. In Step 3, (2
8/3) / (4/3) = 28/4 = 7, (32/3) /
(2/3) = 32/2 = 16. Since 7 is smaller, a _rs = a ₁₁ = _4/3 is the pivot.

In step 4, pivot transformation is performed by using a ₁₁ as the pivot to obtain the matrix of FIG. 8E (sweep out). Return to step 1. c ₁ ≧ 0, ..., c ₄ ≧
0, that is, all are non-negative, so the process ends.

With x ₃ = 0 and x ₄ = 0, the optimum solution is shown in FIG. 8 (f). At this time, the value of the objective function z is z = 45, which is the maximum (in the above, the explanation of the simplex method is published by Kinokuniya Shoten, Noboru Ito, Saira Iwai, Chokei Iwahori, Tatsuharu Uebayashi, Kaoru Sekino, Takahashi. See Shuichi, "Matrix for Economics and Engineering and Its Applications").

FIG. 9 shows a flow chart of addition / subtraction processing of a floating point arithmetic unit used in a conventional linear programming problem optimizing apparatus. A description will be given according to the numbers shown.

S1 Input the normalized floating point data. S2 Add or subtract. S3 Rounding is performed for small values.

S4 The calculation result is output.

[0020]

As described above, when there are many variables, in order to obtain the optimum solution of the linear programming problem,
A huge number of arithmetic processes must be performed. As a result, errors due to the finite precision of computer digits may be accumulated, and the number of sweeps may increase, the processing may loop, and the optimum solution may not converge.

The influence of the error will be described with reference to FIG. FIG. 10 is an explanatory diagram of a problem of error in floating point arithmetic. FIG. 10A is an explanatory diagram of normalization in floating point arithmetic.

In floating point arithmetic, all numerical values are normalized so that significant figures are divided into a mantissa part and an exponent part so as to start from the first decimal place. For example, 1234 having 4 significant figures is 0.1234 × 10 ⁴ , the sign part is a positive or negative sign, the exponent part is an exponent of 10 ⁴ , and the mantissa part is the mantissa 1
Represented as 234.

Next, referring to FIG. 10, the error in the case of calculating AB = C and C × 1000 = D by the floating point calculation will be described. It is assumed that B is obtained by another calculation process.

It is assumed that B is normalized and B = 0.4 × 10 is a correct value, but an error occurs in the calculation process of B, and B is normalized to obtain 0.39999999 × 10.

In FIG. 10, data A is input. Then, the normalized floating point number A is input to.

A calculation process of B is performed. And
The floating-point number B normalized to is input. B is 0.
4 × 10 is the correct value (desired value), but due to the calculation error, 0.39999999 × 10 is calculated,
Entered in.

In, C = AB is calculated and normalized to obtain C = 0.1 × 10 ^-6 . The desired correct C value is C = 0.4 × 10−0.4 × 10 = 0
However, due to an error in the calculation process of B, C = 0.1 ×
10 ⁻⁶ is calculated.

Then, the processing of C × 1000 = D is performed.
D = 0.1 × 10 ⁻³ is obtained from the calculation result C of, and is output. If B is correctly obtained in the calculation process of B, D = 0 should be obtained, but since an error has occurred, the error of B is enlarged and output.

In the floating point arithmetic, the present invention prevents the influence of the error of the arithmetic result from affecting the succeeding arithmetic.
In particular, it is an object of the present invention to provide a floating-point arithmetic unit and an error correction method that are effective when applied to a linear programming problem, an apparatus for optimizing the linear programming problem, and a method for solving the optimum solution.

[0030]

In floating-point (particularly double-precision floating-point) addition and subtraction, the operation result may be a very small value (value close to 0) compared with the value before the operation. For example, there is a case where the value of the exponent part before calculation changes from 10 (data value has 10 digits) to 0 (data value has 1 digit). This is often caused by an error due to the finite number of digits in the computer,
The two numbers, which should be equal in nature, caused a very small value due to an error, and are considered to be 0 correctly.

According to the present invention, the arithmetic result is set to 0 when the value of the exponent part greatly changes before and after the addition and subtraction and a small value is generated. This process is called relative error correction.

FIG. 1 shows the basic configuration of the present invention. In FIG. 1, 1 is a floating point arithmetic unit.

Reference numeral 2 denotes an operation data input section for inputting normalized data. Reference numeral 3 denotes an operation data holding unit, which holds the normalized input data by dividing it into a sign part, an exponent part, and a mantissa part.

Reference numeral 4 is an arithmetic unit for adding and subtracting. Reference numeral 5 is a normalization processing unit. 6 is a calculation result holding unit.

Reference numeral 7 denotes a relative error correction unit, which determines a change in the exponent part before and after the calculation and corrects the calculation result according to the degree of the change. Reference numeral 8 is a calculation result output unit.

Reference numeral 10 denotes an exponent holding unit A, which holds the value of the exponent part of the input operation data. A threshold holding unit 11 holds a threshold for determining whether or not to change the calculation result.

Reference numeral 12 is an exponent comparison unit for comparing the exponent part of the input data before the operation with the exponent part of the operation result. An exponent holding unit B 13 holds the value of the exponent part of the calculation result.

Reference numeral 14 denotes a calculation result changing unit, which corrects the calculation result.

[0039]

The operation of the basic configuration of the present invention shown in FIG. 1 will be described with reference to FIG. FIG. 2 shows an operation example of the basic configuration of the present invention.

The operation data input unit 2 inputs the normalized operation data. In the case of FIG. 2, A = 0.4 × 10 and B = 0.39999999 × 10 are input. The arithmetic data holding unit 3 holds each input data by dividing it into a sign part, an exponent part, and a mantissa part. The operation unit 4 subtracts A and B, the normalization processing unit 5 performs normalization processing, and the operation result holding unit 6 outputs the normalized operation result 0.1 × 10 ⁻⁶ to the sign part, exponent part, and mantissa part. And hold them (the exponent is expressed as shown in the figure for convenience of explanation).

On the other hand, the exponent holding unit A (10) takes out and holds the exponent part (value 01) of the data held in the operation data holding unit 3. The exponent holding unit B (13) takes out and holds the value (-6) of the exponent part held in the calculation result holding unit 6. Then, the exponent comparing unit 12 takes the difference between the exponent taken out by the exponent holding unit A (10) and the exponent taken out by the exponent holding unit B (13) to obtain the value 5 held in the threshold holding unit 11, for example. Compare. When the difference between the exponents is larger than the threshold value, the calculation result changing unit 14 is instructed to correct the calculation result. In the case of the figure, since the difference between the indexes is 7 and the threshold value is 5, the calculation result changing unit 14 is instructed to correct the calculation result.

According to the instruction from the exponent comparison unit 12, the operation result changing unit 14 changes the operation result held in the operation result holding unit 6 to 0 and outputs 0 if there is a correction instruction. If there is no change instruction, the value held in the calculation result holding unit 6 is output.

According to the present invention, even if the value of the operation result is large,
If the value of the exponent part is obtained by a large change and should be 0 originally, judge that fact,
Correct it to 0 correctly.

Therefore, according to the present invention, it is possible to perform an accurate arithmetic process for the arithmetic process for finding the solution of the multidimensional simultaneous equations such as the linear programming problem optimizing device.

[0045]

FIG. 3 shows a structural embodiment of a linear programming problem optimizing apparatus equipped with a floating point arithmetic unit according to the present invention.

In FIG. 3, reference numeral 20 denotes a linear programming problem optimizing device, which is a floating point having a linear programming problem optimal solution solving means for finding an optimal solution of the linear programming problem by a simplex method, and a relative error correction part of the present invention. It is equipped with an arithmetic unit.

Reference numeral 21 is a CPU. 22 is a main memory. Reference numeral 23 is an input means for calculating data, constraint conditions,
The objective function etc. are input.

An output means 24 is a display, a printing device or the like for outputting the calculation result. 25 is a floating point arithmetic unit.

Reference numeral 26 denotes a multiplication / division unit, which performs multiplication or division. An adder / subtractor 27 adds or subtracts. Reference numeral 28 is a relative error correction unit, which has been described above.

Reference numeral 30 denotes an optimal solution for a linear programming problem, which seeks an optimal solution for the linear programming problem by the simplex method. 31 is step 1 (see above).

Step 32 is step 2 (see above). Three
Step 3 is step 3 (see above). 34 is step 4
That is, the sweeping process is performed (see above).

Reference numeral 35 is a constraint condition. 36 is an objective function. 37 is calculation data.

In the configuration of FIG. 3, the optimum solution for linear programming problem solving means 30 uses the floating point arithmetic unit 25,
Based on the constraint condition 35 and the calculation data 37, step 1 (3
The optimum solution of the objective function 36 is obtained according to 1), step 2 (32), step 3 (32), and step 4 (34). In the floating-point arithmetic unit 25, the relative error correction unit 28 determines the above-mentioned relative error in the calculation result of the addition / subtraction processing, and if correction is necessary, corrects the calculation result to 0 and performs floating-point calculation. .

FIG. 4 is a flow chart of an embodiment of the floating point arithmetic unit of the present invention. FIG. 4 shows the operation in the case of a double precision floating point arithmetic unit. S1 Double-precision floating-point number addition / subtraction processing is started.

S2 The exponent part of the double precision floating point number is taken out (the value of the exponent part is m. If there are two or more operation data, any of them may be used). S3 Addition or subtraction of double precision floating point numbers.

S4 The exponent part of the double precision floating point number is extracted (the extracted value is n). S5 m-n is calculated, and mn is compared with a certain value (threshold value). If m−n ≧ a certain value, the process proceeds to S6, and if m−n <a certain value, the process ends.

S6 Difference m between exponent before operation and after operation
-N is larger than a certain value, so the calculation result C is C = 0.0
And An embodiment of the floating point arithmetic unit of the present invention will be described with reference to FIG.

FIG. 5 shows an example in which simultaneous equations are solved by the floating point arithmetic unit of the present invention. In FIG. 5, each floating point is a value output by the C language function printf (“% e”, floating point variable name). Floating point number is 32
It shall be declared in bits. The determination value (threshold value) used in the relative error correction is 5.

The simultaneous equations in (a) are to be solved. (a)
The value on the right side of the equation (2) is obtained by adding 0.1 for 100 times. The calculation method is as follows.

Int i; float rhs2 = 0.0; for (i = 1; i <= 100; i ++) rhs2 + = 0.01; the correct calculation result is 1, but as shown in the figure due to a calculation error. It is 9.999993e-01 (e-01 represents 10 ^-1 ).

By sweeping out the equation (a) and solving it, the equation (b) is obtained. Therefore, when solving the equation (a) while performing the relative error correction of the present invention, the result is as follows.

In the equation (c) (the equation (c) is the same as the equation (a)), the underlined portion is swept out. Therefore,
When (2) − (1) is calculated, the calculation on the right side is (d). Here, relative error correction is performed on the calculation result in (d).

When the exponent part of the right side of 9.9999993e-01 in the equation (2) is taken out, m = -1. (Alternatively, the exponent part of 1.00000e + 00 on the right side of the equation (1) may be taken out and m = 0 may be used). The calculated value of −6.556511e
Taking out the exponent part of −07, n = −7. Next, when the difference between the respective exponents is obtained, m−n = −1 − (− 7)
= 6 (or m-n = 0-(-7) = 7).

When this value is compared with the judgment value (threshold value), it is greater than 5. Therefore, the value on the right side of equation (d) is error-corrected to 0, and equation (f) is obtained. As a result, the correct equation (g) is obtained.

Next, sweeping is performed for y in the equation (g). That is, (1)-(2) '/ 2.0000e + of equation (g)
When 00 is calculated, formula (h) is obtained.

Therefore, a correct expression can be obtained by performing the relative error correction (the value on the right side of (2) "in the expression (b) is corrected to a correct value.) FIG. The results are shown.

FIG. 6 shows a method according to the present invention and a conventional method for optimization of 81 linear programming problems in which the size of a matrix is several tens × several tens to several thousands × thousands by the simplex method. And the sweep time and the sweep time. The improvement rate is the amount of improvement divided by the amount without relative error correction (the amount by the conventional method) divided by the method of the present invention.

It has been shown that the number of sweeps and the sweep time are improved by the method of the present invention.

[0069]

According to the present invention, even if the value of the operation result is a large value, the value of the exponent part is obtained by a great change, and if it should originally be 0, it is determined. However, since it is corrected to 0 correctly, the calculation result is not corrected based on a small value determined in advance as in the past, but the error is corrected by the change in the value before and after the calculation. As a result, it becomes possible to perform reliable error correction. Therefore, according to the present invention, it becomes possible to perform an accurate arithmetic process with respect to an arithmetic process for finding a solution of a multidimensional simultaneous equation, such as a linear programming problem optimizing device, and also at an arithmetic speed. It will be faster.

[Brief description of drawings]

FIG. 1 is a diagram showing a basic configuration of the present invention.

FIG. 2 is a diagram showing an operation example of the basic configuration of the present invention.

FIG. 3 shows a structural embodiment of a linear programming problem optimizing apparatus having a floating point arithmetic unit according to the present invention.

FIG. 4 is a diagram showing a flowchart of an embodiment of a floating point arithmetic unit of the present invention.

FIG. 5 is a diagram showing an example of the present invention.

FIG. 6 is a diagram showing measurement results of effects of the present invention.

FIG. 7 is a diagram showing how to obtain an optimum solution of a linear programming problem.

FIG. 8 is a diagram showing an example (simplex method).

FIG. 9 is a diagram showing a flowchart of addition / subtraction processing of a floating-point arithmetic unit used in a conventional linear programming problem optimizing apparatus.

FIG. 10 is an explanatory diagram of an error problem in floating-point calculation.

[Explanation of symbols]

 1: Floating-point arithmetic unit 2: Arithmetic data input unit 3: Arithmetic data holding unit 4: Arithmetic unit (addition / subtraction) 5: Normalization processing unit 6: Arithmetic result holding unit 7: Relative error correction unit 8: Arithmetic result output unit 10 : Index holding unit A 11: Threshold holding unit 12: Index comparing unit 13: Index holding unit B 14: Calculation result changing unit

Claims (4)

[Claims] 1. A floating point arithmetic unit for adding / subtracting a normalized floating point number, wherein an exponent holding unit A (10) for the input normalized floating point number and an exponent holding unit for the normalized floating point number of the operation result. B (13), a threshold value holding unit (11) that holds a threshold value of a criterion for determining whether or not to correct the calculation result, and a comparison result of the index value before the calculation and the index value after the calculation with the threshold value. An exponent comparison unit (12) that determines whether or not the calculation result is corrected, and a calculation result change unit (14) that corrects the calculation result based on the comparison result of the exponent comparison unit (12) Floating point arithmetic unit characterized by the following. 2. An error correction method in a floating-point arithmetic unit for adding / subtracting normalized floating-point numbers, wherein a comparison result between the exponent of the input normalized floating-point number and the exponent of the normalized floating-point number of the operation result An error correction method for a floating-point arithmetic unit, which corrects an arithmetic result based on a comparison result with a predetermined threshold. 3. A linear programming problem optimizing apparatus comprising the floating point arithmetic unit according to claim 1, further comprising a linear programming problem solving means for holding a constraint condition and an objective function and obtaining an optimum solution under the constraint condition. An apparatus for optimizing a linear programming problem, characterized in that an optimum solution is obtained by performing a floating point operation in the floating point operation device (1) by the linear programming problem solving means. 4. The floating point arithmetic unit according to claim 1.
In the method for finding an optimal solution in the linear programming problem optimizing device having (1), the exponent part of the input floating point number is compared with the exponent part of the normalized floating point number of the operation result, and the comparison result Is compared with a predetermined threshold value, and the optimum solution is calculated while correcting the calculation result based on the result, and a method for finding an optimum solution in a linear programming problem optimizing apparatus is characterized.