JP3535808B2 - Pair-down multiplication method, pair-down multiplication device, and computer-readable recording medium - Google Patents

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a multiplication method and an apparatus therefor, and more particularly to a pair-down multiplication method and a pair-down multiplication apparatus suitable for multiplication between huge numbers having a large number of digits.

[0002]

2. Description of the Related Art Multiplication of huge numbers is required in the fields of space science and nonlinear programming (NP), for example. However, in a normal arithmetic method based on binary numbers and floating point arithmetic, a calculation error is large and practical. Cannot be used for Therefore, the present inventor utilizes a new product, which is an order product that is completely different from the conventional multiplication method, and can obtain the final product at high speed without error (hereinafter referred to as a conventional multiplication device). ) Has already been proposed (Japanese Patent No. 2818512).

(A) If the multiplicand X is a numerical value of N (N ≧ 2) digits represented by an L-adic number (L ≧ 2), and the multiplier Y is also an L-adic numerical value of M (M ≧ 2) digits, First, all combinations of any one numerical value that constitutes the multiplicand X and any one numerical value that constitutes the multiplier Y are the multiplicands of the two numerical values to be combined, and the digits 0 to N-1 indicating the place in the multiplier. ，
From the sum of orders 0 to (N-1) for each type of sum of 0 to M-1
Group into groups up to + (M-1).

(B) Next, for each group, the multiplication value of two numerical values to be combined is added for all combinations belonging to that group. This added value is the order product of the group.

(C) Next, the least significant digit of the product of the groups in which the sum of the orders is 0 is output as the tail number, and all digits other than the least significant digit are lowered by one digit, that is, 1 The digit-shifted one is the remaining number at the present time, and the sum of orders is (N-1) + (M-1) from the product of orders of the group where the sum of orders is 1.
In order up to the order product of the group of, the current residual number and the order product are added, the lowest digit of the added value is output as the tail number, and all digits other than the lowest digit of the added value are output. Repeat the calculation with the remaining number at the current value reduced by one digit.

The product Q of the multiplicand X and the multiplier Y is given as an array of the output tail number and the residual number at the end of the calculation.

[0007]

According to the above-described conventional multiplication device, by the unit operation by the product of orders and the number of tails, calculation is performed only on a number having a digit far smaller than the original multiplicand and multiplier. Thus, it was possible to execute multiplication of huge numbers with many digits at high speed and without error.

However, the conventional multiplication device still has a problem to be improved. That is, in the conventional multiplier,
In the process of (c), the order products to be currently processed are sequentially switched, but the number of order products to be switched is about N + M. Therefore, frequent switching of the order product to be currently processed occurs, which causes an overhead of arithmetic processing. In addition, since the digits of the order product are not the same in all groups, it is not possible to use a uniform addition method when adding the residual number and the order product at the present time. The intervening shift operation for lowering the value by one digit is also a factor of decreasing the operation speed particularly when the multiplication is executed by software of the computer.

Therefore, an object of the present invention is to enable multiplication of huge numbers to be obtained with high accuracy and at high speed.

Another object of the present invention is to repeat a process of sequentially obtaining a part of a multiplication value which is an operation result,
A numerical value of the same digit can be treated in the same way every time, and the shift operation is eliminated to further increase the operation speed.

Another object of the present invention is to reduce the storage capacity required in the process of arithmetic processing.

[0012]

A pair-down multiplication device of the present invention is an N-digit (N ≧ 2) multiplicand X represented by an L-adic number (L ≧ 2) and an M-digit represented by the L-adic number ( In a multiplication device for obtaining a product Q of M ≧ 2) with a multiplier Y, a part for calculating, for each numerical value of each digit in the multiplier Y, a partial product of N + 1 digits which is a multiplication value of the numerical value and the multiplicand X. The product calculating means and the partial product calculated by the partial product calculating means,
From the partial product corresponding to the 0th digit of the multiplier Y, M-1
Partial products 2 that are sequentially adjacent to the partial product corresponding to the digit in the second digit
And pair-down arithmetic means for sequentially deriving a numerical value of each digit forming the product Q by pairing the two and performing a diagonal addition process and a carry process. More specifically, N + 1 from the 0th array element storing the numerical value of the least significant digit of the partial product calculated by the partial product calculating means to the Nth array element storing the numerical value of the most significant digit. Further comprising a plurality of arrays including a plurality of array elements, wherein the pair-down operation means is the multiplier Y
The numerical value of the least significant digit in the partial product corresponding to the numerical value of 0th digit is output as a part of the product Q, and the multiplier Y
From the partial product corresponding to the numerical value of the first digit to the partial product corresponding to the numerical value of the M-2 digit, two adjacent partial products are paired to form the i + 1 (i = 1 to M-3) digit The k−1 th (k = 1 to N +) on the array which stores the partial product corresponding to the numerical value.
1) Add the value of the k-th array element on the array storing the partial product corresponding to the i-th digit numerical value to the value of the 1st-th array element, and then add the partial product corresponding to the i + 1-th numerical value The process of carrying the addition result between adjacent array elements is performed to digitize the value of each array element, and then the value of the 0th array element is output as a part of the product Q. For the partial product corresponding to the M-th digit of the multiplier Y,
The k−1th (k = 1 to 1) on the array which stores the partial product
The value of the (N + 1) th array element stores the partial product corresponding to the numerical value at the (M-2) th digit of the multiplier Y.
After adding the value of the th array element, carry out the carry process of the addition result between adjacent array elements of the partial product corresponding to the numerical value of the M-1st digit, and after digitizing the value of each array element, It is configured to output the numerical values stored in the array as part of the product Q. Also, as the plurality of sequences, aiming to reduce the serial憶容amount, in synchronization with the processing by the Peadaun multiplying means the partial product calculating said by means multiplier Y 0
Ru comprises two sequence partial products alternately is stored from the partial product corresponding to the digit numbers to the partial product corresponding to the M-1 digit numbers.

In the pair-down multiplication device of the present invention,
In the pair-down arithmetic means for sequentially deriving the numerical values of each digit forming the product Q, the number of partial products to be processed is about M.
Since the number of individual processing objects is changed, the frequency of switching the pair of processing targets is reduced to half that of the conventional multiplication device, and the overhead of the arithmetic processing is reduced accordingly. Further, since the processing target in the pair-down calculation means for sequentially obtaining a part of the multiplication value as the calculation result is always the same number of digits of N + 1 digits, the processing of executing two adjacent partial products as a pair is standardized. it can.
Further, since the processing contents are the diagonal addition processing and the carry processing, and the shift processing is not required, the calculation speed can be further increased.

Further , the pair-down multiplication method of the present invention uses L
N digit (N ≧ 2) multiplicand X represented by a base number (L ≧ 2)
And a multiplier Y of M digits (M ≧ 2) represented by the L-adic number, i in the multiplier Y is obtained.
When the multiplication value of the (i = 0 to M−1) -th digit value and the multiplicand X is referred to as the i-th digit corresponding partial product, two including N + 1 array elements from the 0th to the Nth Calculating and storing a 0th digit corresponding partial product in one of the arrays and storing and calculating a 1st digit corresponding partial product in the other array; The numerical value of the 0th array element of the array storing the eye-corresponding partial product is output as a part of the product Q, and the k-1th (k = 1 to 1) on the array storing the first digit corresponding partial product. The value of the (N + 1) th array element is added to the value of the kth array element on the array that stores the 0th digit corresponding partial product, and then the result of the addition is calculated between adjacent array elements of the 1st digit corresponding partial product. Performs carry processing to digitize the value of each array element and outputs the numerical value of the 0th array element as a part of the product Q. Comprising the steps of, in order from the value of the second digit in the multiplier Y to a value of M-2 digit, of the two sequences to calculate the i-th digit corresponding partial product, i-2
After overwriting the array storing the digit-corresponding partial product, the value of the k−1 (k = 1 to N + 1) th array element on the overwritten array is set to the kth array element on the other array. After adding the array element values, carry out the carry processing of the addition result between adjacent array elements of the i-th digit corresponding partial product, and set the value of each array element to 1
A step of repeating the process of digitizing the numerical value of the 0th array element as a part of the product Q, and calculating a partial product corresponding to the (M-1) th digit to calculate M among the two arrays. -3
After overwriting the array storing the digit-corresponding partial product, the value of the k−1 (k = 1 to N + 1) th array element on the overwritten array is set to the kth array element on the other array. After the values of the array elements are added, carry processing of the addition result is performed between adjacent array elements of the M-1 digit corresponding partial product, and the value of each array element is digitized and stored in the overwritten array. Outputting the calculated numerical value as a part of the Q.

[0015]

BEST MODE FOR CARRYING OUT THE INVENTION Next will be described the actual 施例 with reference to the drawings in detail of the present invention, prior to it, the basic principle of the decimal Peadaun multiplication scheme in which the present invention is applied to the multiplication of decimal explain.

When the multiplicand X is an N-digit decimal number in the present decimal number pair down multiplication system, it is shown as follows. Here, [] indicates an array, and x is an array name. The number in parentheses is a positive integer from 0, this number is called a subscript and gives the digit of the original number in the array. For example, when the multiplicand X is a four-digit decimal number 6957, N = 4, so x
[N-1] = x [3] = 6, and similarly, x [2] =
9, x [1] = 5 and x [0] = 7.

When the multiplier Y is an M-digit decimal number,
It is shown as follows. For example, when the multiplier Y is a four-digit decimal number 8134, M
= 4, y [M-1] = y [3] = 8, y [2] =
1, y [1] = 3 and y [0] = 4. Furthermore, the multiplier Y
One digit of is represented as:

In the decimal pair down multiplication method, first, the digit of the multiplicand X is N and the digit of the multiplier Y is M, and the lower digit of the multiplier Y is 1 from the lower digit as shown in (A4) below.
A partial product with the multiplicand X is created for each digit and placed in a two-dimensional equal-length partial product array.

This two-dimensional isometric partial product array is represented by p [i] i
Abbreviated as = 0, 1, ..., M-1. As a number array, this partial product is N + 1 digits, or N digits, and if the integer of the one-digit multiplier y [i] is small, it becomes N digits. At this time, 1 digit decimal number 0 is placed at the beginning to make N + 1 digits. , All partial products are placed in a two-dimensional equal-length partial product array of N + 1 digits.

The first subscript i of the two-dimensional equal-length partial product array shown in (A4) above is the first subscript common to each array term of one array, and at the same time the digit of the one-digit component of the multiplier Y is Lowest 0
Give in order. The second subscript N, N-1, ..., 0 corresponds to the digit N of the multiplicand X and is given in the same shape in each array as in (A4). The sum of the subscripts in [] [] of the two-dimensional isometric partial product array gives the digit of the term. For example, the digit of u [i] [1] is i + 1. This is the above (A
In 4), it is shown in parentheses.

The two-dimensional isometric partial product array p [i] is i =
0, 1, 2, ..., M-1, and there are M as shown below.

Decimal pair-down multiplication starts with a pair-down operation of equal-length partial product arrays p [0] and p [1]. In the following (A6),) indicates a pair addition operation, and a diagonal line with a plus sign is a diagonal addition symbol. In the pair addition operation, N 1-digit diagonal additions are performed, and u [1] of p [1]
Place it in [N-1] to u [1] [0]. The sum of diagonal addition is 0
At 18, there is no other value. p [1] bottom symbol |
Indicates a down operation in which an array of only one digit is calculated by carrying out a two-digit sum or the like. p [1] ^* is a one-digit array obtained by digitizing the p [1] array. This (A6) is the first pair down and the upper array p of the first pair.
The rightmost term u [0] [0] of [0] does not participate in the diagonal addition and is the lowest product q [0].

Once the sequence p [1] ^* has been obtained, then p
A second pair down p [2] ^* is obtained from [1] ^* , p [2]. Repeating this, the M-1th pair down, At this time, the product of the N-digit multiplicand and the M-digit multiplier is Given in. The tail of this product is the rightmost term of the upper array of pairs arranged in reverse order, giving M-1 decimal one-digit products. This value is quickly determined during the pair down calculation.

A calculation example is shown below.

Calculation example: 6957 × 8134 The multiplicand X is a 4-digit decimal number 6957, and the multiplier Y is 4
The digit is a decimal number 8134. N = 4. M = 4.

In this way, since the lower and upper digits of the product are obtained separately, a huge error in carry calculation does not occur. The lower order of the product with the M digit multiplier may be the bit sequence of the last term value sequence q [0] q [1] ... q [M-2] of the two-dimensional equal-length partial product array. If this is confirmed, p [M-3] to p [0]
May be deleted, and the product top is given at high speed and high precision by pair-down multiplication of p [M-2] ^* , p [3].

The features of the decimal pair down multiplication method according to the present invention will be described below.

1. The high precision and high speed failure of the conventional calculation of huge number products in all Western countries and the Middle East is based on the huge addition of shifting partial products. However, in the present invention, a unique equal-length two-dimensional partial product array is devised, and this pair arrangement is devised,
The upper right array element of the equal-length two-dimensional partial product array forming the pair is determined only by the operation of a small number such as 1-digit decimal number addition of 2 and the lower-order automatic determination of the huge number product is performed. What is shown is a digit change due to the array position of the equal-length two-dimensional partial product array due to the two-dimensionalization of the partial product array. In the present invention, the equal-length two-dimensional partial product array is one larger than the multiplicand digit N, but becomes N digits when the multiplier is small. At this time, 0 is placed in the head array N + 1 digit.

2. The equal-length two-dimensional partial product array has p [i]: u [i] [N] u [i] [N−1] ...
u [i] [1] u [i] [0] i = 0, 1, 2, ..., M
-1 M rows are obtained, and from the pair of p [0] and p [1],
N-digit one-digit decimal numbers of the array elements having the same digits are added, and this addition is oblique addition. This sum is placed in the array below. Since it is a two-dimensional array, the sum of the original subscripts above and below the diagonal lines, that is, the digits can be added equally. 0 + N = 1 + N-
1, 0 + N-1 = 1 + N-2, .... U [0] at the end
Other than the terms [0] and u [1] [N], diagonal addition is possible and the sum is placed in the descending array.

3. The diagonal addition of a pair is the addition of two numbers of one digit 0-9, and the sum is 0-18. In this multiplication method, the sum exceeding this does not appear. The first pair down This two-dimensional isometric partial product array has two types of subscripts.
The first subscript has the same value on one isometric partial product array, and p
[0] is 0, and p [1] is 1 and the above pair is diagonally shaded, the digits are the same, and addition is possible. The sum is placed in the lower array p [1]. For example, As described above, the one-digit sum or the two-digit sum is placed in the second and subsequent terms of the lower array of the p [0] to p [1] pair. This one-digit sum may be used as it is, but when the two-digit sum is 10 to 18, an operation of adding the two-digit high-order digit 1 as a carry to the low-order number of the left array item to form an array of only one digit is called down. At this time, in the N + 1 digit term u [1] [N] of the lower row array p [1], the upper digit of the partial product is placed, so that even if there is a carry from the lower digit, 9
This is not the case and the isometric property of the two-dimensional isometric partial product array is maintained. In this way, p [1], which has a one-digit number, becomes p
[1] ^* Anyway. The next pair down operation is p [1] ^* Pair with p [2] at the beginning.

4. As described above, a sequence of N + 1 digits, which is one digit more than the digit N of the decimal multiplicand to be partially multiplied, is formed by multiplying the multiplicand and the lower digit of the multiplier by one digit. If it becomes N digits, put 0 at the beginning. This number is p
0, p1, p2, ..., pM. Take this as a pair like p0 to p1, calculate diagonal addition and carry-off, and p1 to p1 ^*
Perform pair down to convert to 1 digit, and then p
Enter the second pair as in 1 ^* -p2 and issue p2 ^* . With the following equal-length parallel arrays, multiplication of huge numbers can be performed at extremely high speed without error. The enormous product is also given by the final array p (M-1) ^* having a width of N + 1 digits and the fraction of the down column.

5. In the system of the present invention, simple decimal processing, that is, processing such as addition and carry, is suitable for software, processed at high speed, and results can be obtained at high speed. It is written in the language C ++, and a pair-down process is performed by repeating a do-while statement, so that a huge number product can be correctly answered at high speed.

Next, the basic principle of the binary number pair-down multiplication system in which the present invention is applied to binary multiplication will be described.

In the binary number pair-down multiplication method multiplication method, a correct answer can be obtained without problem for multiplication of numbers up to about 100 million, but in the case of a large number, a large error occurs due to carry. This binary pair-down multiplication method can very easily find a huge product. When giving the binary number of the multiplicand, consider the one with bit 0 added to the beginning, consider a binary number sequence of only 0 equivalent to this, and consider the pair down method with the multiplier, so that multiplication can be done accurately at high speed . Here, a pair is a parallel addition of 1-digit binary numbers, and a down means a high-speed 1-digit addition of 2-digit addition sums. A pair product and a down operation are combined, and a huge product is serial type and parallel type. Therefore, high-speed calculation is possible without error. It is particularly fast for binary numbers. It will be useful for calculating huge quantities related to space.

The features of the binary pair-down multiplication system will be described below. (1) Unlike normal multiplication, a multiplier is created using only two types, that is, the same length horizontally arranged binary multiplicand and the same array as the partial product array with 0-bit head number and an array of all 0 bits, without using shift. (2) The binary multiplier is y [0], y [1], in order from the lower digit.
When written as ..., y [M-1], this array is either 1 or 0. When y [i], i = 0, ..., M-1 is set, the subscript i gives the digit position of the multiplier. At the same time, it also serves as a subscript of the same-length horizontal N + 1 digit 0-bit head multiplicand partial product array of (1). If this same-length sequence is p [i], i = 0,1,
2, ..., M-1.

Such an array of the same length can be converted into p from i = 0.
The diagonal addition of [0] and p [1] and the sum at p [1] are N
An array p [1] ^* of +1 digit and 1 digit binary number is obtained. This diagonal addition is called a pair, and digitization of the sum is called a down. Then p [1]
^A second pair down p [2] ^* is obtained by ^* , p [2]. A huge product can be obtained accurately and rapidly by the M-1th pair down.
The product in the middle of each pair can be obtained one digit at an extremely high speed for each pair in the middle.

The multiplication is more complicated than the addition, and a huge error occurs particularly in the multiplication of a huge number. However, in the present method, only a binary addition of one digit of the same binary digit is necessary. That is, there are four types of addition.

In the pair stage, one-digit addition is performed obliquely according to the order of the multiplicand N digits, and the sum is placed in the lower array of the pair array. This sum far. There are N, and the sum form is only 0, 1, 10.

Next, assuming that the multiplicand is N digits in binary number, it is N or N + 1 digits in a normal partial product array, but in the present multiplication method, it is unified into an N + 1 digit partial product array, and there is no shift in two-dimensional equal length. Consider only partial product arrays. Let this be p [i],
You can write like (3). The multiplier y [i] is a binary number of M digits, and if i = 0, it is a binary digit of a 0-digit multiplier, which is either 1 or 0. i = 0, 1, ..., Corresponds to any of 0 to M digits of the M-1 multiplier, Therefore, the array of p [i] is an array of N digit multiplicands 0 and 1 with the leading N + 1 digit 0 added, and an array (4) of multiplier digit all 0s, a multiplier digit 1 and a multiplicand The cosmic huge multiplication can be performed without a high-speed error only by the pair-down calculation of the two types of arrays of the partial product array (5). This same-length partial product array is given by either (4) or (5). N + 1
It is a digit. However, the digits are different. The least significant digit of the upper array is i, j. The lowest digit of (4) is the i digit, and the (5) is the j digit.

The handling of numbers in this multiplication method is different from the conventional one in handling digits. Consider, as an example, an (N + 1) -th order two-dimensional equal-length partial product array. The first subscript i is a first subscript common to each array item of one array, and simultaneously gives the digits of the one-digit component of the multiplier in order from the lowest 0. The second subscripts N, N-1, ..., 0 correspond to the digit N of the multiplicand,
It is given in the same shape in each sequence as in (3). P in (3)
The order of [i] is However, the binary pair down multiplication is sequentially executed from the pair arrays p [0] and p [1] above this array.

The binary pair-down multiplication starts with the pair-down operation of the equal-length partial product arrays p [0] and p [1]. (7)
, Indicates a pair addition operation, where N 1-digit diagonal additions are performed, and u [1] [N-1] to u [1] of p [1]
Place in [0]. The lower-end symbol | of p [1] indicates a down operation in which an array of only one digit is calculated by carrying out a two-digit sum or the like. p
[1] ^* is a one-digit array in which the p [1] array is digitized. This (7) is the first pair down, and the upper array p of the first pair.
The rightmost term u [0] [0] of [0] does not participate in the diagonal addition and is the lowest product q [0].

In the conventional giant number multiplication, when the multiplication product becomes large, the carry increases, and when the product increases, a large error occurs.
However, in the pair-down multiplication method according to the present invention, a huge error does not occur, and there is no minute error. In the case of a binary number, two types of two-dimensional equal-length partial product arrays are given to speed up the calculation. Let Y be the multiplier, and y [i], i = 0, 1,
..., m-2, and m-1 are binary numbers 0 and 1. The digit of the binary number is indicated by i. There are m multiplier digits. The multiplier has digits up to m-1 digit when taking from 0 digit. The multiplicand is also binary and has N digits, and x [N-1] x [N-
2] ... A single digit binary number such as x [0] is used as the element of each array. The two-dimensional equal-length partial product array is a two-dimensional array of subscripts N, N-1, ..., 0 indicating the number of digits of the multiplicand and a single digit of the multiplier subscript i. The number of N is a two-dimensional array of N + 1. A two-dimensional equal-length partial product array of the subscript i is defined as p [i], and each array item is provided with a binary number 0 or 1 of the digit of each subscript sum. p [i]
The number of array terms of is N + 1. Letting the variable of the array term be u, the two-dimensional isometric partial product array p [i] can be written as follows.

[1] p [i] before the operation is u [i] [N] = 0, and the subsequent array items are either the binary bit pattern of the multiplicand or the bit pattern of all zeros. 1,
Corresponds to 0. [2] The original binary digit of each array term of p [i] is (1
It is the sum of subscripts in () of 0). In the above example, i + N digits to i digits. Each of these array terms is based on the binary numbers 0 and 1, but after the diagonal addition of the array is included, the down operation is performed to include the upper array 2
Move the base 1 to the left term and place 0 in that term. In the case where all the array terms of p [i] are 1 and 0, p [i] is written as p [i] ^* .

A two-dimensional isometric partial product array can be written in M rows as follows. … The pair down operation (9) is repeated from p [0] for this M row array by adding modified arrays p [1] ^* and p [2] ^* as follows. Repeating this, the M-1th pair down, At this time, the product of the N-digit multiplicand and the M-digit multiplier is Given in. The back of this product is the rightmost term of the upper array of pairs arranged in reverse order, giving M-1 binary one-digit products. This value is quickly determined during the pair down calculation.

A calculation example is shown below.

Calculation Example 1; 111110111 × 1111 In this case, since the multiplier is only 1, there is one type of two-dimensional same-length partial product array, and there is no all 0 in the form of 0 multiplicand. N = 9, M
= 4.

In this way, since the lower and upper digits of the product are obtained separately, a huge error in carry calculation does not occur,
Improve the reliability of long-distance observation. The present invention shows the possibility of product operation without approximation such as million years. The lower order of the product with the M digit multiplier is the tail term value sequence q [0] q of the two-dimensional same-length partial product array.
A bit sequence of [1] ... q [M-2] may be used. If this is confirmed, p [M-3] to p [0] may be deleted, and
[M-2] ^* , p [3] pair-down multiplication gives high-speed and high-precision product top. Although given by hand above, C ++
The ultra-high-speed error-free processing such as is obvious in the embodiment described later, and is a program of the 21st century including outer space.

Calculation example 2; if the multiplier is 1,0, p
[I] is an N + 1 digit two-type array, and a multiplier y = 10101.
1, multiplicand 111011, M = 6, N = 6,

The features of the binary pair-down multiplication method according to the present invention will be described below.

1. Let N be the digit of the multiplicand and be a binary number. This is bN-1 bN-2 ... b0. If the digit of the multiplier is M and the partial product with the multiplicand is created one digit each from the lower digit binary number, the N digit 2
A binary number array is obtained, but a one-digit binary number 0 is forced to the upper left, and a two-dimensional equal-length partial product array of N + 1 digits is obtained. This array is numerically 0bN-1 bN-2 ... b0 or 000 ...
The number is 0 and the number is M. Using this array, the product of the multiplicand and the multiplier of N digits and M digits can be obtained at high speed without error.

2. This array gives a fixed-length binary array, but at the same time gives the digits of the original array. This digit position is given by two sets of subscript sums of the two-dimensional equal-length partial product array, but the digit itself is not described in the arithmetic expression. This description method requires a supplement. The digit position of the binary one digit of the multiplier is represented by i with 0 digit being the least significant, and the one digit binary number is y [i], i = 0, 1, 2, ..., M−1,
A two-dimensional isometric partial product array is represented by p [i], i = 0, 1, 2,
..., M-1. When the multiplier digit is y [i] = 1: p
[I] = 0bN-1 bN-2 ... b0. When the multiplier digit is y [i] = 0: multiply by p [i] = 000 ... 0. p [i] takes either of these. However, since this array is two-dimensional, the first subscript subscript
An array function having (i) and a second subscript N is shown as follows. The first and second subscript sums indicate the digits of each array item binary number.

3. i = 0, 1, ..., M-1 indicates a multiplier digit, but at the same time gives the order of a two-dimensional same-length partial product array, and p
[0]) p [1] is the first binary addition, and 0 + 1 =
The sum S of 1,0 + 0 = 0 and 1 + 1 = 10 is obtained in N pairs and is replaced with the descending array p [1]. This operation is called a pair operation. When S = 0 or 1, 1 bit may be used as it is, but when S = 10, the array term occupies 2 bits, so that term is set to 0 bit and carry bit C
If 1 is added to the left term and the term is S = 0, then S = 1, and if the term is S = 1, S = 0 and the carry bit C1 is set to the left term. This operation is called down. p [1] ^* is u [1] [N] = 0, and u [1] [N−
Even if the sum S of [1] is S = 10, digit spreading does not occur. N + 1 digits of the two-dimensional same-length partial product array are retained. As described above, two binary numbers of the pair p [0] and p [1] of the same digit are obliquely added, and the sum S is u [1] [N-1] ... Of the lower column p [1].
u [1] [0]. S = 0,1,10. The steps so far are called pair steps. The rightmost array item u [0] [0] of the above pair of upper arrays p [0] does not participate in the diagonal addition and gives the bottom of the true huge product. Now, when the pair stage is drawn, the addition sum S = 0, 1, 10 is p
From the Nth term u [1] [N-1] of [1], the first term u
[1] [0] is diagonally added, and the sum is placed in p [1]. Write down below. When the 2-digit binary sum S = 10, the digit is set to 0 bit and the carry C1 is set up and added to the left term sum S. S
If = 0, S = 1. If S = 1, left term sum S = 10 and left term S
= 0, and the carry C1 moves to the left side. In this way, the sum of paired arrays is made into a one-digit binary sequence, which is called the down method. The left-most term u [1] [N] of the pair lower array is originally 0, but when u [1] [N-1] is S = 10, u
Only [1] [N] = 1, the array under the pair remains at N + 1 digits, and the symbol * is added after the end of down. p [1] ^* .
The first pair down is shown below. The rightmost array term of the upper array p [0] of the above first pair-down gives the least significant digit of the true huge product without explicitly participating in the diagonal addition.

4. While repeating the pair down operation as described above, the lower digits of the huge product are sequentially determined at high speed, and the upper N digits of the huge product are accurately determined at high speed. The second pair-down operation is p [1] ^* and the two-dimensional same-length partial product array p
It is performed in [2], and p
[2] Decide ^* . Similarly, when continuing up to the multiplier y [M-1], the last pair down is This huge product is p [M-1] ^* q [M-2] q [M-3]
It is obtained by q [1] q [0]. Multiplicand is N digit 2
The base number is a binary number having M digits. In this pair-down multiplication method, the binary pattern of the multiplicand and the multiplier bit of 1,0
It suffices to use M types of two 0-bit head equal length bits N + 1 digit arrays that are distinguished by. That is, when the i-th p [i] is taken out, if the multiplier i digit is 0, the first bit is always 0 if the multiplicand N = 14 digits, and if the multiplier i digit is bit 0, the partial product bits 00 ... 0, A two-dimensional isometric partial product array has p [i] = 000000000000000000. If the multiplier i digit is bit 1, the multiplicand N = 14 digits and 1010
In the case of 1010101010, the above p [i] is only 0 and the multiplicand bit, and p [i] = 010101010101010 p [i] are only these two types. can get.

5. In the system of the present invention, simple processing of binary numbers 1, 0, that is, processing such as addition and carry-over, is suitable for software, processed at high speed, and results are obtained at high speed. It is written in the language C ++, and a pair-down process is performed by repeating a do-while statement, so that a huge number product can be correctly answered at high speed.

[0055]

[Precondition] Next precondition decimal Peadaun multiplication method according to the present invention will be described in detail.

Referring to FIG. 1, a premise example of a computer 1 to which the present invention is applied is connected to an input device 2, an output device 3 and a recording medium 4, and internally has an input means 11, a partial product calculation means 12 and a pair down. It has a functional unit such as an arithmetic unit 13 and an output unit 14, and a storage unit such as an input memory 15, a work memory 16 and an output memory 17. Each of the storage units 15 to 17 is composed of a main storage device constituting the computer 1, and each of the functional units 11 to 14 is composed of an MPU constituting the computer 1 and a multiplication program. The multiplication program is a machine-readable recording medium 4 such as a CD-ROM, a floppy disk, or a semiconductor memory.
When the computer 1 is started, the multiplication program in the recording medium 4 is read by the computer 1, and the operation of the computer 1 is controlled. The storage units 15 to 17 are generated.

The input device 2 is composed of a keyboard, a disk device, etc., and the multiplicand X and the multiplier Y are input to the computer 1 from the input device 2.

The input means 11 is a part for storing in the input memory 15 the multiplicand X, the multiplier Y and the digits N and M thereof inputted from the input device 2.

The partial product calculating means 12 calculates, for each numerical value of each digit in the multiplier Y stored in the input memory 15, a partial product of N + 1 digits which is a multiplication value of the numerical value and the multiplicand X, and the work memory 16 Is a means for storing in. Here, each partial product is a 0th array element u [first subscript] [second subscript] having two subscripts of a first subscript and a second subscript.
To an N-th array element u [first subscript] [second subscript], represented as an array p having N + 1 array elements,
It is stored in the work memory 16. Here, each array element of the array p has a capacity for storing a numerical value for two digits in preparation for the calculation by the pair-down calculation means 13 described later.

The work memory 16 is a partial product calculating means 12
Is a memory having a capacity for storing a plurality of arrays p generated as described above.

The pair-down operation means 13 calculates the partial product calculated by the partial product calculation means 12 and stored in the work memory 16 as an array from the partial product corresponding to the 0th digit of the multiplier Y to the (M-1) th digit. In order up to the partial product corresponding to the numerical value of, two adjacent partial products are paired and the numerical value of each digit forming the product Q of the multiplicand X and the multiplier Y is sequentially derived by diagonal addition processing and carry processing. This is a part for outputting to the output memory 17. The product Q is from the 0th array element q [0] to the N + th array element.
It is expressed as an array q having N + M array elements up to the M−1th array element q [N + M−1].

The output means 14 is a part for outputting the product Q stored in the output memory 17 to the output device 3. A display device, a disk device, or the like is used as the output device 3.

Next, the operation of this premise example will be described. It should be noted that the present invention is capable of calculating multiplication of a huge number without error, but in the following, for convenience of explanation, a multiplicand X of four decimal digits is used.
The product Q “5” is obtained by multiplying “6957” by the multiplier Y “8134”.
For example, a case of calculating “6588238” will be described.

When the multiplicand X and the multiplier Y are input from the input device 2, the input means 11 checks the number of digits of the multiplicand X and the multiplier Y, and the input memory 15 stores the number of digits of the multiplicand X as shown in FIG. N “4”, the digit number M “4” of the multiplier Y are stored, and the array x of the multiplicand X and the array y of the multiplier Y are also stored. Then, the partial product calculating means 12 is activated.

The partial product calculating means 12 obtains the value of M from the input memory 15 and arranges M arrays p [0] to p [M-1].
After allocating the area of 3 to the work memory 16, the processing shown in FIG. 3 is started. The number of array elements in each array p [0] to p [M-1] is the same N + 1, and the capacity of one array element is a capacity capable of storing a 2-digit numerical value. For example, 1
When a 1-digit number in the 0-ary number is represented by a binary coded decimal code (BCD), each array element has a size of 4 bits × 2 = 8 bits.

Referring to FIG. 3, the partial product calculating means 12
First initializes the internal variable i to 0 (step S
1) Next, the loop processing of steps S2 to S9 is repeated until the variable i exceeds M-1, and then the pair-down calculation means 13 is activated (step S10), and the processing ends.

The loop processing of steps S2 to S9 calculates, for each numerical value of each digit in the multiplier Y, a partial product of N + 1 digits which is a multiplication value of the numerical value and the multiplicand X, and applies the calculated partial product. Corresponding to the process of storing in the array
One partial product is processed in one loop. Specifically, the processing is as follows.

First, the internal variable k is initialized to 0 (step S2), and the value obtained by multiplying x [0] and y [0] is 10
The remainder (% lo) divided by is the array element u of array p [0]
Stored in [0] [0] (step S3). x [0] =
Since 7, y [0] = 4, 4 × 7 = 28/10 = remainder 8
And u [0] [0] = 8.

Next, the product of x [0] and y [0] divided by 10 is the quotient (/ lo), and x [1] and y
The value obtained by adding the remainder obtained by multiplying [0] by 10 is stored in the array element u [0] [1] of the array p [0] (step S5). x [0] = 7, x [1] =
5, y [0] = 4, so 4 × 7 = 28/10 = quotient 2,
4 × 5 = 20/10 = remainder 0, so u [0] [1] =
It is 2. Next, k is incremented by 1 to 1 (step S
6), step S5 is executed again, and u [0] [2] = 8
And Next, k is incremented by 1 to 2 (step S6), and step S5 is executed again to set u [0] [3] = 7 (step S5). Next, if k is incremented by 1 (step S
6), k = 3, and the continuation condition of k ≧ N−2 = 2 is not satisfied, so the process proceeds from step S4 to step S7.

In step S7, the quotient = 2 obtained by dividing x = [3] by y [0] = 24 by 10 is set to the array element u [0] [4] of the array p [0]. Store.

By the above processing, the value of the partial product of the 0th digit 4 of the multiplier Y and the multiplicand X is stored in the array p [0] on the work memory 16 as shown in FIG. become.

The partial product calculating means 12 then sets the variable i to +1.
Then, the value is set to 1 (step S8), and the process is returned to step S2 in order to calculate the partial product of the first digit "3" of the multiplier Y. Thus, the partial product corresponding to the first digit "3" of the multiplier Y, the partial product corresponding to the second digit "1", 3
The partial products corresponding to the digit number “8” are sequentially obtained, and when i reaches 4, the loop processing is exited in step S9. At this point, as shown in FIG. 4, in the work memory 16, each array of the array p corresponding to each partial product from the numerical value “4” of the 0th digit of the multiplier Y to the numerical value “8” of the third digit The element value is fixed.

The array element u [1] of the array p [1]
The value of [3] is 10, array element u [3] of array p [3]
The value of [3] is 15 and both have two digits, but in the present precondition example, the carry process is omitted and the two digits are left as they are. The reason is that the processing of the pair-down calculation means 13 described later is 1
This is because it is not necessary to dare digitize at this stage because digitization is performed. Of course, the digit may be digitized at this stage.

When the multiplication program is described in, for example, C ++ language, steps S2 to S9 are executed by the DO statement.
Each of steps S4 to S6 can be easily described by a for sentence.

Next, the pair-down calculation means 13 will be described. The pair-down calculation means 13 is a partial product calculation means 12
When the values of N and M are obtained from the input memory 15 and the area of the array q having N + M array elements q [0] to q [N + M−1] is secured in the output memory 17, Figure 5
The process shown in is started.

Referring to FIG. 5, the pair-down calculation means 1
3 first initializes the internal variable i to 0 (step S1
1) Next, the loop processing of steps S12 to S25 is repeated until the variable i exceeds M-3, after which the internal variable k is initialized to M-1 (step S26), and then the loop of steps S27 to S29. The processing is repeated until the variable k exceeds N + M-1, and the output means 14 is activated (step S30), and the processing is ended.

The loop process of steps S12 to S25 is
The partial product corresponding to the 0th digit of the multiplier Y to the partial product corresponding to the M-1st digit is paired with two adjacent partial products to form a product Q by diagonal addition processing and carry processing. This is equivalent to the process of sequentially deriving the numerical value of each digit, and the numerical value of one digit forming the product Q is derived by one loop. Specifically, the processing is as follows.

First, the internal variable k is set to 0 (step S12), and the value of the array element u [0] [0] of the array p [0] on the work memory 16 is set to the value of the 0th digit of the product Q. q [0]
Is output to the output memory 17 (step S13).

Then, the internal variable k is initialized to 1 (step S14), the loop processing of steps S15 to S17 is continued until the variable k exceeds N, and then the variable k is initialized to 0 (step S18). The loop process of steps S20 to S23 is continued until the variable k exceeds N.

The loop process of steps S15 to S17 is
This is a part for performing diagonal addition processing by pairing two adjacent partial products, and specifically under the condition of variable i = 0, the following processing is performed.

The value obtained by adding the value of the array element u [0] [1] of the array p [0] and the value of the array element u [1] [0] of the array p [1] to the array p [1 ] Array element u [1] [0]
(Step S16). Referring to FIG. 4, u
Since [0] [1] = 2 and u [1] [0] = 1, u
[1] and [0] are updated to 3. Next, increment k by 2
(Step S17), step S16 is executed again, and the value of the array element u [0] [2] of the array p [0] and the value of the array element u [1] [2] of the array p [1] are set. The value obtained by adding and is written back to the array element u [1] [2] of the array p [1]. Referring to FIG. 4, u [0] [2] = 8, u [1]
Since [1] = 7, u [1] [1] is updated to 15. Similarly, the value "7" of the array elements u [0] [3]
And the value “8” of the array element u [1] [2] are added to write back the value “15” to the array element u [1] [2], and the value “2” of the array element u [0] [4]. ] And array element u [1] [3]
The value "12" obtained by adding the value "10" of the array element u
Write back to [1] and [3]. Then, if k is incremented by 1, then 5
Since the continuation condition of k ≦ N is not satisfied, the process proceeds from step S15 to step S18.

FIG. 6 schematically shows a state of diagonal addition between partial products by the loop processing of steps S15 to S17.
In the figure, diagonally drawn lines are called diagonal addition symbols and indicate pairs of array elements to be added. In the case of the present premised example, the paired array elements have the same total value of the first subscript and the second subscript. That is, the loop process corresponds to obtaining the sum of two partial products. However, the shift operation is not performed for digit alignment, and as shown in the schematic diagram, the diagonal method, that is, the k−1th array element and the kth array element between two arrays having the same number of array elements are used. It just adds between the array elements. Such addition is referred to as diagonal addition in this specification. When digitizing at the time of partial product calculation, the diagonal addition is limited to the binary addition of 0 to 9 and therefore the sum does not exceed 18. In the down operation after the pair operation, the sum of 10 to 18 is digitized. Since there is no addition of hundreds, thousands, tens of thousands, etc. of the vertical direction addition that accompanies the normal shift, a huge carry does not occur,
High-speed and high-precision multiplication can be obtained by pair-down diagonal addition.

Next, the loop processing of steps S19 to S23 will be described. This loop processing corresponds to processing for converting the value of each array element of the array p [1] updated by diagonal addition into one digit. First, the array element u [1] of the array p [1]
Depending on whether the quotient obtained by dividing the value of [0] by 10 is 0, it is determined whether the value of the array element is 2 digits or 1 digit (step S
20). If it is 1 digit, the array element does not need to be converted to 1 digit, and therefore k to process the next array element u [1] [1].
Is incremented by 1 to 1 (step S23). If it has two digits, the value obtained by adding the quotient obtained by dividing the value of the array element u [1] [0] by 10 and the value of the adjacent array element u [1] [1] is the adjacent The array element u [1] [1] is overwritten (step S21), and the array element u [1] [0] is overwritten by the remainder obtained by dividing the value by 10 (step S22). That is, carry processing of the array elements u [1] [0] is performed. Then, the next array element u [1]
In order to process [1], k is incremented by 1 to 1 (step S
23). In the case of FIG. 6, since the value of u [1] [0] after the diagonal addition is “3”, which is one digit, steps S21 and S22 are not executed.

The value of the next array element u [1] [1] is "1".
5 ", so carry processing is performed and the array p at the bottom of FIG.
The value is set to "5" as shown in [1]. At this point, the values of the array elements u [1] [2] are “16”, but the value is “6” due to the carry process.
In this way, the carry process is performed in order, and the array p
All array elements u [1] [0] to u [1] of [1]
[4] is converted into a single digit as shown in the array p at the bottom of FIG.

When the process of pairing the array p [0] and the array p [1] is completed, the variable i is incremented by 1 to 1 (step S25), the process returns to step S12, and the digitizing process is performed this time. The array p [1] that has completed the above is paired with the next array p [2], and the same processing as the processing for the pair of the array p [0] and the array p [1] is repeated. In step S13 in this process, u [1] [0] of the array p [1] is stored in q [1] of the array q as the first digit value of the product Q.
In the loop processing of 15 to S17, the array p [1] and the array p
The values of array elements in which the sum of the first subscript and the second subscript of [2] are equal are added, and diagonal addition is performed to overwrite the array p [2], and the array p [2 is processed in steps S19 to S23. ]
Each array element of is converted into a single digit.

In this way, the same process is repeated while switching pairs in order, and the array p [M-
2] and the process of pairing the final array p [M−1] with each other, the value of the variable i is 2, and the condition of i ≦ M−3 is not satisfied. Therefore, the loop of steps S12 to S25 is performed. The process exits and the process proceeds to step S26. At this point, the numerical values of the digits from the 0th digit to the M-2nd digit of the product Q are derived and stored in q [0] to q [M-2] of the array q, and the last array p Since the digitizing process of [M-1] has been completed, the array p [M-1] stores the values of the M-1th digit and higher digits of the product Q. Therefore, in the example of the multiplication of the multiplicand X “6957” and the multiplier Y “8134”, q [0] = 8, q [1] = 3, q [2] = 2, and the array array p [ The states of 0] to p [3] are as shown in FIG. 7, and the value of the third digit or more of the product Q is stored in the array p [3].

Therefore, in step S26, the variable k is set to M.
-1 and the loop process of steps S27 to S29 is repeated until the value of the variable k exceeds N + M-1, so that the value stored in the array p [M-1] is set as the value forming the product Q. Output to array q. Specifically, first, the sequence p
The value of u [M-1] [0] of [M-1] is stored in q [M-1] (step S28), k is incremented by 1 to be M (step S29), and then u [M]. −1] [1] is set to q
The process of storing in [M] is repeated thereafter until the process of changing u [M-1] [N] to q [N + M-1]. As a result, q [3] = 8, q [4] = 8, q [5] = 5, q
[6] = 6 and q [7] = 5. After that, the pair-down calculation means 13 activates the output means 14 (step S3).
0).

The output means 14 reads the array q from the output memory 17 and outputs it to the output device 3. When the value of q [N + M-1] of the array q is 0, the output of the value of the array element may be omitted.

[0089] To explain the operation when applying the precondition technique of binary Peadaun multiplication method according to the present invention in the following on the computer 1 shown in FIG. The binary pair-down multiplication method according to the present invention is capable of calculating multiplication of a huge number without error. However, in the following, for convenience of explanation, a multiplicand X of 9 digits in binary number “111110111” and a binary number of 4 digits in binary number are used. Multiplier Y
The product Q “11101011110” is multiplied by “1111”.
Take "01" as an example.

When the multiplicand X and the multiplier Y are input from the input device 2, the input means 11 checks the digit numbers of the multiplicand X and the multiplier Y, and stores the digit numbers of the multiplicand X in the input memory 15 as shown in FIG. N “9”, the number of digits M “4” of the multiplier Y, and the array x of the multiplicand X and the array y of the multiplier Y are stored. Then, the partial product calculating means 12 is activated.

The partial product calculating means 12 obtains the value of M from the input memory 15 and arranges M arrays p [0] to p [M-1].
The area shown in FIG. 12 is secured in the work memory 16, and then the processing shown in FIG. 12 is started. Each array p [0] to p [M-1]
The number of array elements of N is the same N + 1, and the capacity of one array element is a capacity capable of storing a 2-digit numerical value. That is,
Each array element has a size of 2 bits.

Referring to FIG. 12, the partial product calculating means 12
First initializes the internal variable i to 0 (step S30
1) Next, the loop processing of steps S302 to S308 is repeated until the variable i exceeds M-1, and then the pair-down calculation means 13 is activated (step S309), and the processing is ended.

The loop process of steps S302 to S308 calculates, for each numerical value of each digit in the multiplier Y, a partial product of N + 1 digits which is a multiplication value of the numerical value and the multiplicand X, and applies the calculated partial product. Corresponding to the processing of storing in the array, and one partial product is processed in one loop.
Specifically, the processing is as follows.

First, the internal variable k is initialized to 0 (step S302), and the value obtained by multiplying x [0] and y [0] is set in the array element u [0] [0] of the array p [0]. It is stored (step S304). Since x [0] = 1 and y [0] = 1, u [0] [0] = 1. Next, k is incremented by 1 to 1 (step S305), and step S304 is executed again to set u [0] [1] = 1. Similarly, u
[0] [2] = 1, u [0] [3] = 0, u [0]
[4] = 1, u [0] [5] = 1, u [0] [6] =
1, u [0] [7] = 1 and u [0] [8] = 1.
Next, when k is incremented by 1 (step S305), k = 7 and the continuation condition of k ≧ N−1 = 8 is not satisfied, so the process proceeds from step S303 to step S306.

In step S306, 0 is stored in the array element u [0] [9] of the array p [0].

By the above processing, the value of the partial product of the 0th digit 1 of the multiplier Y and the multiplicand X is stored in the array p [0] on the work memory 16 as shown in FIG. become.

The partial product calculating means 12 then sets the variable i to +1.
Is set to 1 (step S307), and a partial product for the numerical value "1" in the first digit of the multiplier Y is calculated in step S302.
Return processing to. Thus, the first digit of the multiplier Y is "1"
The partial product corresponding to the second digit, the partial product corresponding to the second digit "1", and the partial product corresponding to the third digit "1" are sequentially obtained, and when i becomes 4, in step S308,
Get out of the loop. At this point, as shown in FIG. 13, in the work memory 16, each array of the array p corresponding to each partial product from the 0th digit “1” of the multiplier Y to the 3rd digit “1” The element value is fixed.

When the multiplication program is described in the C ++ language, for example, steps S302 to S309 can be easily described by a DO statement, and steps S304 to S306 can be easily described by a for statement.

Next, the pair-down calculation means 13 will be described. The pair-down calculation means 13 is a partial product calculation means 12
When the values of N and M are obtained from the input memory 15 and the area of the array q having N + M array elements q [0] to q [N + M−1] is secured in the output memory 17, Figure 1
The process shown in 4 is started.

Referring to FIG. 14, the pair-down computing means 13 first initializes the internal variable i to 0 (step S
311), and then the loop processing of steps S312 to S325 is repeated until the variable i becomes M-1 or more, and then the internal variable k is initialized to M-1 (step S32).
6) Next, the loop process of steps S327 to S329 is repeated until the variable k exceeds N + M-1, and the output means 14 is activated (step S330) to finish the process.

The loop processing of steps S312 to S325 is performed from the partial product corresponding to the 0th digit of the multiplier Y to M-1.
Partial products 2 that are sequentially adjacent to the partial product corresponding to the digit in the second digit
The two products are paired and the product Q is obtained by the diagonal addition process and the carry process.
Corresponds to the process of sequentially deriving the numerical value of each digit that constitutes
In one loop, the numerical value of one digit forming the product Q is derived. Specifically, the processing is as follows.

First, the internal variable k is set to 0 (step S312), and the value of the array element u [0] [0] of the array p [0] on the work memory 16 is set to the value of the 0th digit of the product Q. q
It is output to the output memory 17 as [0] (step S3).
13).

Next, the internal variable k is initialized to 1 (step S314), the loop processing of steps S315 to S317 is continued until the variable k exceeds N, and then the variable k is set to 0.
Is initialized (step S318), and steps S319-
The loop process of S323 is continued until the variable k exceeds N.

The loop process of steps S315 to S317 is a part for performing an oblique addition process by pairing two adjacent partial products, and under the condition of the variable i = 0, specifically, the following process is performed. Becomes

The value obtained by adding the value of the array element u [0] [1] of the array p [0] and the value of the array element u [1] [0] of the array p [1] to the array p [1 ] Array element u [1] [0]
(Step S316). Referring to FIG. 13, since u [0] [1] = 1 and u [1] [0] = 1, u [1] [0] is updated to 10. Next, add k
1 to 2 (step S317), and step S3 again
16 is executed and the array element u [0] of the array p [0] is executed.
Value of [2] and array element u [1] [2] of array p [1]
And the value of is added to the array element u of the array p [1].
Write back to [1] and [2]. Referring to FIG. 13, u
Since [0] [2] = 1 and u [1] [1] = 1, u
[1] [1] is updated to 10. The same operation is repeated thereafter, and when k reaches 10, the continuation condition of k ≦ N is no longer satisfied, and therefore steps S315 to S315 are performed.
Proceed to 318.

FIG. 15 schematically shows the state of diagonal addition between partial products by the loop processing of steps S315 to S317. In the figure, diagonally drawn lines are diagonal addition symbols, which indicate pairs of array elements to be added. In the case of the present premised example, the paired array elements have the same total value of the first subscript and the second subscript. That is, the loop process corresponds to obtaining the sum of two partial products.
However, the shift operation is not performed for digit alignment, and as shown in the schematic diagram, the diagonal method, that is, the k−1th array element and the kth array element between two arrays having the same number of array elements are used. It just adds between the array elements.

Next, the loop processing of steps S319 to S323 will be described. This loop processing corresponds to processing for converting the value of each array element of the array p [1] updated by diagonal addition into one digit. First, the array element u of the array p [1]
Depending on whether the quotient obtained by dividing the values of [1] and [0] by 2 is 0, it is checked whether the value of the array element has 2 digits or 1 digit (step S320). If it is one digit, it is not necessary to digitize the array element, so k is incremented by 1 to be 1 in order to process the next array element u [1] [1] (step S323). Two
If it is a digit, the value obtained by dividing the value of the array element u [1] [0] by 2 and the value of the adjacent array element u [1] [1] is added to the adjacent value. Array element u [1] [1] is overwritten (step S321), and array element u [1] [0]
Is overwritten by the remainder obtained by dividing the value by 2 (step S322). That is, carry processing of the array elements u [1] [0] is performed. Then, the next array element u
[1] To process [1], k is incremented by 1 to 1 (step S323).

In the case of FIG. 15, u [1] after diagonal addition
Since the value of [0] is “10” and has two digits, carry processing is performed and the value is set to “0” as shown in the array p [1] at the bottom of FIG. At this point, array element u [1] [1]
Has a value of "11", but the carry process results in a value of "1". In this way, carry processing is performed in order, so that all array elements u of the array p [1] are
[1] [0] to u [1] [9] are digitized into one digit as shown in the array p at the bottom of FIG.

When the process of pairing the array p [0] and the array p [1] is completed, the variable i is incremented by 1 to 1 (step S325), the process returns to step S312, and this time is set to 1
The array p [1] that has undergone digitization processing and the next array p [2] are paired, and the same processing as that for the pair of the array p [0] and the array p [1] is repeated. In this way, the same process is repeated while switching the pairs in order, and when the process of forming a pair of the array p [M-2] and the final array p [M-1] that have completed the one-digitization process is completed, the variable i Has a value of 4,
Since the condition of i <M-1 is not satisfied, step S3
The loop from 12 to S325 is exited, and step S326 is executed.
Proceed to processing. At this point, from the 0th digit of the product Q, M-2
Numerical values of the digits up to the digit are derived and q [0] to q of the array q
It is stored in [M-2], and the last array p [M-
Since the 1-digitization processing of [1] has also been completed, the array p [M-1]
The value of the digit of the product Q at the (M-1) th digit or more is stored in. Therefore, in the example of multiplication of the multiplicand X “111110111” and the multiplier Y “1111”, q [0] = 1,
q [1] = 0, q [2] = 0, and the states of the array arrays p [0] to p [3] are as shown in FIG.
The value of the third digit or more of the product Q is stored in the array p [3].

Therefore, in step S326, the variable k is initialized to M−1, and the loop processing of steps S327 to S329 is repeated until the value of the variable k exceeds N + M−1. The value stored in is output to the array q as a value forming the product Q. Specifically, first, the value of u [M-1] [0] of the array p [M-1] is set to q [M-
1] (step S328), k is incremented by 1 to be M (step S29), and then the value of u [M−1] [1] is stored in q [M]. [M-1]
The process is repeated until [N] is set to q [N + M-1]. As a result, q [3] = 1, q [4] = 1, q [5] =
1, q [6] = 1, q [7] = 0, q [8] = 1, q
[9] = 0, q [10] = 1, q [11] = 1, q [1
2] = 1. After that, the pair-down calculation means 13 activates the output means 14 (step S330).

The output means 14 reads the array q from the output memory 17 and outputs it to the output device 3. When the value of q [N + M-1] of the array q is 0, the output of the value of the array element may be omitted.

[0112]

Embodiments of the present invention will now be described in detail with reference to the drawings.

In the above-described precondition example, the partial product calculating means 12
After storing the array of partial products corresponding to the numerical values of all the digits in the multiplier Y in the work memory 16, the pair-down calculation means 1
Although the processing by 3 is started, in the present embodiment, the work memory 16 of the array related to the partial product by the partial product calculating means 12 is started.
To the work memory 1 by synchronizing and alternately executing the storage in the
The number of arrays that need to be stored at once in 6 is set to two, and the required storage capacity is reduced. Note that, also in the present embodiment, for convenience of explanation, a multiplicand X of four decimal digits X "695
7 ”and the multiplier Y“ 8134 ”are multiplied to obtain the product Q“ 56588 ”.
For example, the case of obtaining "238" is taken.

When the multiplicand X and the multiplier Y are input from the input device 2, the input means 11 checks the number of digits of the multiplicand X and the multiplier Y and stores the number of digits of the multiplicand X in the input memory 15 as shown in FIG. N “4”, the digit number M “4” of the multiplier Y are stored, and the array x of the multiplicand X and the array y of the multiplier Y are also stored. Then, the partial product calculating means 12 is activated.

The partial product calculating means 12, regardless of the value of M in the input memory 15, has two arrays p [0], p [0].
After allocating the area [1] in the work memory 16, the process shown in FIG. 8 is started. Here, each array p [0], p
The number of array elements in [1] is the same N + 1, and the capacity of one array element is a capacity capable of storing a 2-digit numerical value. For example, a binary digit decimal code (BC
When represented by D), each array element has a size of 4 bits × 2 = 8 bits.

The processing shown in FIG. 8 is basically the same as the processing shown in FIG. 3, but because the arrays p [0] and p [1] are alternately used in a plurality of partial products, Some parts have been added or modified. The added steps are S101 to S105.
And the corrected steps are S3, S5, S7, and S9. The internal variable j operated in step S101 is for selecting the array p [0] and the array p [1], and takes a value of either 0 or 1. The symbol notj shown in step S102 is a symbol that takes an inverted value of j, and j = 1.
Then, notj = 0, and if j = 0, notj = 1. This internal variable j is specifically, steps S3, S
5 and S7, it appears as the first subscript of the array element u in the array p [j].

As shown in FIG. 8, the partial product calculating means 12 initializes the internal variable j to 0 and sets the internal variable i to 0.
Is initialized (steps S101 and S1), and then the loop processing of steps S2 to S9 and S102 is repeated twice to calculate two partial products and store them in the work memory 106, and process them to the pair-down calculation means 13. Is requested (step S103). After that, the pair-down calculation means 1
Every time there is a processing request from 3 to calculate a partial product (step S104), the next one partial product is calculated and stored in the work memory 106, and the pair down calculation means 13 is requested to perform processing (step S102). , S2-S9, S10
3). Then, at the point of time when there is an end request from the pair-down calculation means 13 (step S105), the processing is ended.

On the other hand, the pair-down operation means 13 is activated when the first processing request is issued from the partial product calculation means 12, obtains the values of N and M from the input memory 15, and outputs N + M array elements q [ After securing the area of the array q having 0] to q [N + M−1] in the output memory 17, the process shown in FIG. 9 is started.

The processing shown in FIG. 9 is basically the same as the processing shown in FIG. 5, but since the arrays p [0] and p [1] are alternately used in a plurality of partial products, Some parts have been added or modified. The added steps are S201 to S205.
And the corrected steps are S16, S20 to S22,
It is S28. As shown in FIG. 9, the pair-down operation means 13 first initializes the internal variable j to 0 and the internal variable i to 0 (steps S201 and S201).
11) Next, the processes of steps S12 to S25 and S202 are executed to perform the diagonal addition of one pair and the digitizing process, and request the partial product calculating means 12 to calculate the next partial product ( Step S203). Then, the process waits for a processing request from the partial product calculating means 12 (step S204), and if there is a request, the process returns to step S12 to execute the diagonal addition and the digitizing process for the next pair. When the processing is completed up to the last pair (NO in step S24), the internal variable k is initialized to M-1 (step S26), and then the loop processing of steps S27 to S29 is performed with the variable k being N + M-.
Repeat until it exceeds 1, and then the partial product calculating means 12
Is notified of the end request and the output means 14 is activated (steps S205, S30), and the process is ended.

FIG. 10 shows the multiplicand X "6957" and the multiplier Y.
The transition of the values of the arrays p [0] and p [1] on the work memory 16 in the multiplication process with "8134" is shown.

Since the partial product calculating means 12 initializes the variable j to 0 at the start of processing, the multiplier Y obtained in the first execution of steps S2 to S7 (execution under i = 0) is 0. The partial product “27828” of the digit value “4” and the multiplicand X “6957” is the array element u [0] of the array p [0].
[4], u [0] [3], u [0] [2], u [0]
It is stored in [1], u [0] [0] (30 in FIG. 10).
1). Further, the second execution of steps S2 to S7 (i =
Execution under 1) reverses j in step S102,
Since it is performed after setting it to 1, the partial product “110871” of the numerical value “3” of the first digit of the multiplier Y and the multiplicand X “6957”.
Are array elements u [1] [4], u [1] of array p [1]
[3], u [1] [2], u [1] [1], u [1]
It is stored in [0] (302 in FIG. 10). at this point,
The partial product calculation means 12 requests the pair-down calculation means 13 to perform processing (step S103). The value of the variable j in the partial product calculation means 12 at the time of the processing request is 1.

Since the pair-down calculation means 13 initializes the variable j to 0 at the time of starting the processing, the steps S12 to S2 are executed.
In the first execution of 3 (execution under i = 0), first,
In step S13, the value "8" of u [0] [0] of the array p [0] is set to q [0]. In addition, steps S14 to S17
The diagonal addition process is performed as indicated by 303 in FIG. 10, and the one-digit conversion process in steps S18 to S23 is performed in the array p.
It is performed for [1]. As a result, the array p [1] makes a transition as indicated by 304 in FIG. Pair-down calculation means 1
3 then reverses the variable j to 1 (step S2
02), and requests the partial product calculator 12 to calculate the next partial product (step S203).

Upon receiving the above request (step S104), the partial product calculating means 12 inverts the variable j to 0. As a result, the third execution of steps S2 to S7 (i
= 2), the partial product “0695” of the second digit “1” of the multiplier Y and the multiplicand X “6957”.
7 "is the array element u [0] [4], u of the array p [0].
[0] [3], u [0] [2], u [0] [1], u
It is stored in [0] and [0] (305 in FIG. 10). Then, processing is requested of the pair-down calculation means 13 (step S103).

Since the value of the variable j at the present time is 1, the pair-down computing means 13 first executes step S1 in the second execution of steps S12 to S23 (execution under i = 1).
In 3, the value “3” of u [1] [0] of the array p [1] is changed to q
[1]. The diagonal addition process of steps S14 to S17 is performed as indicated by 306 in FIG. 10, and the single digitizing process of steps S18 to S23 is performed on the array p [0]. As a result, the array p [0] makes a transition like 307 in FIG. After that, the pair-down calculation means 13 inverts the variable j to 0 (step S202), and requests the partial product calculation means 12 to calculate the next partial product (step S203).

Upon receipt of the above request (step S104), the partial product calculating means 12 inverts the variable j and sets it to 1. As a result, the fourth execution of steps S2 to S7 (i
= 3), the partial product "41565" of the third digit number "8" of the multiplier Y and the multiplicand X "6957" is obtained.
6 "is the array element u [1] [4], u of the array p [1]
[1] [3], u [1] [2], u [1] [1], u
It is stored in [1] and [0] (308 in FIG. 10). Then, processing is requested of the pair-down calculation means 13 (step S103).

Since the value of the variable j at the present time is 0, the pair-down calculating means 13 first executes step S1 in the third execution of steps S12 to S23 (execution under i = 2).
In step 3, the value “2” of u [0] [0] of the array p [0] is changed to q
[2]. The diagonal addition process of steps S14 to S17 is performed as indicated by 309 in FIG. 10, and the single digitizing process of steps S18 to S23 is performed on the array p [1]. As a result, the array p [1] makes a transition as indicated by 310 in FIG. Since the pair-down calculation means 13 has completed the processing of all pairs (NO in step S24), the processing proceeds to step S26 and subsequent steps.

Since the value of the variable j at the present time is 0, in the loop processing of steps S27 to S29, the value "56588" stored in the array p [1] in the state 310 of FIG. 10 is changed from q [3] to q. It is output as [7].

[0128] While the present invention is applied to a multiplier decimal in the embodiment of the following, binary multiplication, multiplication of octal, hexadecimal or multiplication, generally applicable to multiply the L (≧ 2) Decimal Ah
It

[0129]

As described above, according to the present invention, it is possible to perform an operation for obtaining multiplication of huge numbers without error at a higher speed. The reason for this is that the number of repetitions of the processing in the pair-down arithmetic means for sequentially obtaining a part of the multiplication value which is the arithmetic result is halved compared to the conventional multiplication device, and a partial product with the same number of digits is handled every time, which is uniform. This is because the processing can be carried out dynamically and the shift operation is unnecessary and only the diagonal addition processing and the carry processing are required.

Further, in synchronization with the processing by the pair-down multiplication means, the partial product calculation means starts from the 0th digit of the multiplier Y to M-
A configuration in which partial products up to the first digit are stored alternately in two arrays
Because it is, regardless of the number of digits of the multiplier Y, only two sequences can perform Peadaun multiplication processing, it is possible to significantly reduce the required storage capacity in the course of processing.

In the present invention, the multiplier Y is 0, 1, ..., M-
Basically, a two-dimensional partial product array p [0] ... P [M-1] of N + 1 digits of equal length is used in correspondence with the numerical value of each digit of 1. Since all the arrays are of equal length, the pair configuration has the same length vertically, diagonal addition is always performed N times in the same way, and the right end of the ascending array of pairs sends out the lower digit of the true product one by one. The high-order digit of the product is given by a down array of M down pairs.

[Brief description of drawings]

FIG. 1 is a block diagram of an embodiment of a computer 1 to which the present invention has been applied.

FIG. 2 is a diagram showing an example of data stored in an input memory.

FIG. 3 is a flowchart showing a processing example of a partial product calculating means in the premise example of the present invention.

FIG. 4 is a diagram showing a state of an array stored in a work memory at the time when the operation of the partial product calculating means is completed in the precondition example of the present invention.

FIG. 5 is a flowchart showing a processing example of a pair-down calculation means in the premise example of the present invention.

FIG. 6 is an explanatory diagram of diagonal addition and digitizing processing executed by a pair-down calculation means.

FIG. 7 is a diagram showing a state of an array stored in a work memory at the time when the pair-down calculation means finishes processing for all pairs in the precondition example of the present invention.

8 is a flowchart showing a process example of a partial product calculating means in real施例of the present invention.

9 is a flowchart showing a process example of Peadaun calculating means in real施例of the present invention.

10 is a state transition diagram of the sequence on the work memory in the real施例of the present invention.

FIG. 11 shows a binary pair-down multiplication system according to the present invention.
It is a figure which shows the example of the data stored in an input memory in a premise example .

FIG. 12 illustrates a binary pair-down multiplication system according to the present invention.
It is a flowchart which shows the example of a process of the partial product calculation means in a premise example .

FIG. 13 shows a binary pair-down multiplication system according to the present invention.
FIG. 11 is a diagram showing a state of an array stored in a work memory at the time when the operation of the partial product calculating means is ended in the premise example .

FIG. 14 shows a binary pair-down multiplication system according to the present invention.
It is a flowchart which shows the example of a process of the pair down calculation means in a premise example .

FIG. 15 shows a binary pair-down multiplication system according to the present invention.
It is explanatory drawing of the diagonal addition and digitization processing which the pair-down arithmetic means in a premise example performs.

FIG. 16 shows a binary pair-down multiplication system according to the present invention.
FIG. 8 is a diagram showing a state of an array stored in a work memory at the time when the pair-down calculation means finishes processing for all pairs in the premise example .

[Explanation of symbols]

1 ... Computer 11 ... Input means 12 ... Partial product calculation means 13 ... Pair-down calculation means 14 ... Output means 15 ... Input memory 16 ... Work memory 17 ... Output memory 2 ... Input device 3 ... Output device 4 ... Recording medium

Claims (3)

(57) [Claims] 1. N digits (N ≧ 2) represented by an L-adic number (L ≧ 2)
2) Multiplicand X and M digits represented by the L-adic number (M ≧
2) In a multiplication device for obtaining a product Q with a multiplier Y, for each numerical value of each digit in the multiplier Y, a partial product calculation for calculating a N + 1 digit partial product which is a multiplication value of the numerical value and the multiplicand X Means and N + 1 number of arrays from the 0th array element storing the numerical value of the least significant digit of the partial product calculated by the partial product calculating means to the Nth array element storing the numerical value of the most significant digit A plurality of arrays including elements, and the numerical value of the least significant digit in the partial product corresponding to the 0th digit of the multiplier Y is output as a part of the product Q,
From the partial product corresponding to the first digit of the multiplier Y, M-2
Partial products 2 that are sequentially adjacent to the partial product corresponding to the digit in the second digit
Pair, and stores the partial product corresponding to the numerical value of the i + 1 (i = 1 to M−3) digit, and the k−1th (k−1) th array on the array.
= 1 to N + 1) -th array element value is added to the value of the k-th array element on the array that stores the partial product corresponding to the i-th digit value, and then the i + 1-th digit value is obtained. Carry out the carry operation of the addition result between the adjacent array elements of the partial product, digitize the value of each array element to one digit, and then output the numerical value of the 0th array element as a part of the product Q. Repeatingly, for the partial product corresponding to the value of the M−1th digit of the multiplier Y, the k−1th array on the array in which the partial product is stored is stored.
The multiplier Y is added to the value of the (k = 1 to N + 1) th array element.
Between the adjacent array elements of the partial products corresponding to the numerical value of the M-1th digit after adding the value of the k-th array element on the array storing the partial product corresponding to the numerical value of the M-2nd digit of A carry-down process of the addition result to digitize the value of each array element and output the numerical value stored in the array as a part of the product Q. As the above, the multiplier Y is calculated by the partial product calculating means in synchronization with the processing by the pair-down multiplying means.
2. The pair-down multiplication device, comprising: two arrays in which partial products are alternately stored from the partial product corresponding to the 0th digit value to the M-1th digit value. 2. N digits (N ≧ 2) represented by an L-adic number (L ≧ 2)
2) Multiplicand X and M digits represented by the L-adic number (M ≧
2) In the multiplication method for obtaining the product Q with the multiplier Y, the product value of the i-th digit (i = 0 to M-1) in the multiplier Y and the multiplicand X is called an i-th digit corresponding partial product. At this time, the 0th digit corresponding partial product is calculated and stored in one of the two arrays including the N + 1th array elements from the 0th to the Nth, and the 1st digit corresponding portion is stored in the other array. Calculating and storing a product; outputting the numerical value of the 0th array element of the array storing the 0th digit corresponding partial product of the two arrays as a part of the product Q; 0 is added to the value of the k−1 (k = 1 to N + 1) th array element on the array that stores the digit-corresponding partial product.
The value of each array element is calculated by adding the value of the k-th array element on the array storing the digit-corresponding partial product, and then carrying the addition result between adjacent array elements of the first-digit corresponding partial product. And digitizing the numerical value of the 0-th array element as a part of the product Q, and the i-th digit in order from the second digit of the multiplier Y to the M−2nd digit. After calculating the eye-corresponding partial product and overwriting the one of the two arrays in which the i-2 digit corresponding partial product is stored, the k-1th (k = 1 to 1) on the overwritten array is calculated.
After adding the value of the (k + 1) th array element on the other array to the value of the (N + 1) th array element, carry processing of the addition result is performed between adjacent array elements of the i-th digit corresponding partial product. Repeating the process of converting the value of the array element into one digit and then outputting the numerical value of the 0th array element as a part of the product Q; and calculating the M-1 digit corresponding partial product Of the above array, the one storing the partial product corresponding to the M-3rd digit is overwritten, and the k−1th (k = 1 to N +) on the overwritten array is overwritten.
1) After adding the value of the k-th array element on the other array to the value of the 1st array element, carry the result of addition between adjacent array elements of the M-1 digit corresponding partial product And digitizing the value of each array element to one digit, and then outputting the numerical value stored in the overwritten array as a part of the Q, the pair-down multiplication method. 3. N digits (N ≧ 2) represented by an L-adic number (L ≧ 2)
2) Multiplicand X and M digits represented by the L-adic number (M ≧
2) A machine-readable recording medium in which a multiplication program for obtaining a product Q of the multiplier Y and the multiplier Y is stored in a computer, the numerical value at the i (i = 0 to M-1) digit of the multiplier Y and the multiplicand. When the multiplication value with X is called the i-th digit corresponding partial product, the 0-th digit corresponding partial product is calculated in one of the two arrays including N + 1 array elements from the 0th to the Nth. A process of calculating and storing the first digit corresponding partial product in the other array while storing the numerical value of the 0th array element of the array storing the 0th digit corresponding partial product in the two arrays Is output as a part of the product Q and the value of the (k−1) th (k = 1 to N + 1) th array element on the array storing the first digit corresponding partial product is 0.
The value of each array element is calculated by adding the value of the k-th array element on the array storing the digit-corresponding partial product, and then carrying the addition result between adjacent array elements of the first-digit corresponding partial product. In which the numerical value of the 0th array element is output as a part of the product Q after the digit is converted to a single digit, and the i-th digit is calculated in order from the second digit of the multiplier Y to the M-2 digit. After calculating the corresponding partial product and overwriting the one of the two arrays in which the i-2 digit corresponding partial product is stored, the k-1th (k = 1 to 1) on the overwritten array is calculated.
After adding the value of the (k + 1) th array element on the other array to the value of the (N + 1) th array element, carry processing of the addition result is performed between adjacent array elements of the i-th digit corresponding partial product. The process of repeating the process of converting the value of the array element into one digit and outputting the numerical value of the 0th array element as a part of the product Q, calculating the M-1 digit corresponding partial product, After overwriting the array storing the partial product corresponding to the M-3rd digit of the array, the value of the k-1 (k = 1 to N + 1) th array element on the overwritten array is set to the other one. After adding the value of the kth array element on the array, M-
The value stored in the overwritten array is digitized after carrying out a carry process of the addition result between adjacent array elements of the first digit corresponding partial product, and the value stored in the overwritten array is used as a part of the Q. A computer-readable recording medium that records a program that causes output processing to be executed.