Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-09-27
2002-11-05
Ngo, Chuong Dinh (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S655000
Reexamination Certificate
active
06477556
ABSTRACT:
TECHNICAL FIELD
This invention relates to an operation apparatus, an operation method for calculating a remainder, and a recording medium thereof. In particular, the invention relates to an operation apparatus, an operation method for calculating a remainder using a computer, and a recording medium thereof.
BACKGROUND ART
Related Art 1.
In the following, as the first conventional related art, an example of the conventional technique, where a remainder operating method disclosed in U.S. Pat. No. 5,463,690 is applied, will be explained referring to FIG.
15
. This relates to an operation method for calculating a remainder of an integer Z divided by a prime number P. Here, it is assumed that the prime number P is limited to be a number which can be represented by 2
q
−C (q: a natural number; C: a relatively small odd number). By limiting the prime number as the above, the remainder can be calculated using only shift operation, addition and subtraction. Here, the calculation of remainder is performed by a computer having 2
M
as a basic operational unit.
For example, as shown in
FIG. 15
, the remainder of the integer
685
divided by the prime number
13
(q=4, C=3) can be calculated using the computer having 2
3
(3 bits) as the basic operational unit, and the operation will be described in the following: When represented by binary number,
685
becomes (1010101101).
First, the lowest bits q=4 bits
1401
(1101) of the integer Z=685 are latched. Next, data
1403
(1111110), which is the remaining bits
1402
(101010) multiplied by C=3, is calculated by shift operation and addition. Then, the obtained data
1403
is added to the data
1401
(1101) to obtain data
1404
(10001011).
Then, the lowest bits q=4 bits
1405
(1011) of the data
1404
are latched. Subsequently, data
1407
(11000), which is the remaining bits
1406
(1000) multiplied by C=3, is calculated by shift operation and addition. Further, the data
1407
is added to the data
1405
to produce data
1408
(100011).
Then, the lowest bits q=4 bits
1409
(0011) of the obtained data
1408
are latched. Subsequently, data
1411
(110), which is the remaining bits
1410
(10) multiplied by C=3, is calculated by shift operation and addition. Further, the data
1411
is added to the data
1409
to produce data
1412
(10001).
The data
1412
includes q bits where q is q=4 or q=less than 4, and is a remainder of the integer Z divided by the prime number P. Namely, (1001)=9, and the remainder 9 of 685 divided by 13 is obtained.
Related Art 2.
In the following, as the second conventional related art, an operating method for calculating a remainder R of a division of an integer Z by an integer I will be explained referring to FIG.
16
. The operating method is considered basically in the same way as the first related art, however, the concrete number used therein is different from the first related art. The operating method implemented by the 16-bit computer will be explained, and the operation is performed with 16 bits as a processing unit. In
FIG. 16
, a reference numeral 1501 shows an integer Z, 1502 shows an integer I(I=2
160
+ff9d),
1503
shows higher 64 bit data Zh of the integer Z,
1504
shows lower 160 bit data Zl of the integer Z, and
1509
shows a remainder R. In
FIG. 16
, the integer Z and the remainder R are represented by hexadecimal numbers, and in the integer I, 2
160
is represented by decimal number, ff9d by hexadecimal number.
The highest 16 bits of I are
1
, and the remainder can be calculated by subtracting Zh
1503
multiplied by ff9d from Zl
1504
. Concretely, the following process is used for calculating the remainder.
First, the lowest 16 bit data aaaa of Zh
1503
is multiplied by ff9d to obtain 32 bit data aa
680042
(
1505
) (multiplication 1). Next, bbbb is multiplied by ff9d to obtain 32 bit data bb
7266
af (
1506
) (multiplication 2). Subsequently, cccc is multiplied by ff9d to obtain 32 bit data cc
7
ccd
1
c (
1507
) (multiplication 3).
Then, dddd is multiplied by ff9d to obtain 32 bit data dd
873389
(
1508
) (multiplication 4). Through the above 4 multiplications, a product of multiplication of Zh and ff9d is obtained.
Subsequently, this product is subtracted from Zl (
1504
). In the following, addition and subtraction include carry and borrow.
First,
0042
is subtracted from the lowest 16 bit data
0000
of Zl (
1504
) (addition/subtraction 1). Next, aa
68
is subtracted from
1111
(addition/subtraction 2), and further
66
af is subtracted (addition/subtraction 3). Subsequently, bb
72
is subtracted from
2222
(addition/subtraction 4), and further cdlc is subtracted (addition/subtraction 5). Then, cc
7
s is subtracted from
3333
(addition/subtraction 6), and further
3389
is subtracted (addition/subtraction 7). Finally, dd
87
is subtracted from
4444
(addition/subtraction 8).
As has been described, the remainder R
1509
of the integer Z divided by the integer I is calculated through
4
multiplications and
8
additions/subtractions.
In the above related arts, when the prime number P is 2
q
−C (C is a relatively small odd number), the remainder can be calculated without division, which allows the operation proceed quickly. However, even if the calculation excludes the division, the calculation includes the shift operation, which limits the operating speed of the calculation.
Further, as clearly described in the second related art, when the integer I is 2
q
−f (q=4, f=3 in the first related art, q=160, f=ff9d in the second related art), f (3 or ff9d) multiplication steps are required. And the multiplication result exceeds 16 bits of the basic operation unit, so that the number of accompanied additions or subtractions becomes large. Consequently, the code size becomes large, and when the number of processing steps is large, the operation may delay.
The present invention is provided to solve the above-mentioned problems, and aims to obtain an operation apparatus, operation method for calculating the remainder of the integer at a high speed using a computer and recording medium thereof.
DISCLOSURE OF THE INVENTION
An operation apparatus in relation to the present invention for calculating a remainder R of data Z having Bz bits divided by data I represented by a following equation:
I
=
∑
N
=
0
N
=
N
max
A
N
Q
MN
(M is a number of bits of a basic operational unit; N is a natural number being one of 0 through Nmax, A
0
is a value whose absolute value is smaller than a value represented by the basic operational unit of M bits; each of A
1
through A
Nmax−1
is +1, 0, or −1; A
Nmax
is +1, or −1; and Q is a natural number equal to or more than 2) the operation apparatus includes:
(1) a data Zl storing region for storing data Zl of lower M×Nmax bits of the data Z;
(2) a data Zh storing region for storing data Zh of higher (Bz−M×Nmax) bits of the data Z;
(3) a data A
N
storing region for storing the data A
N
; and
(4) an addition/subtraction unit for calculating the remainder R by determining an operation between addition and subtraction based on positive
egative of the data A
N
, and operating addition/subtraction of data stored in at least a part of the data Zl storing region and data stored in at least a part of the data Zh storing region.
Further, in the operation apparatus, the data Zl storing region stores the data Zl as data Zl(i) divided by the basic operational unit of M bits sequentially from a lowest side within a range of a natural number i (1>i>Nmax) in a data Zl(i) region;
A the data Zh storing region stores the data Zh as data Zh(j) divided by the basic operational unit of M bits sequentially from a lowest side within a range of a natural number j (a natural number of 1>j>(Bz/M)−Nmax with raising its decimals) in a data Zh(j) region; and
the addition/subtraction unit determines the operation between addition and subtraction using N having
Mitsubishi Denki & Kabushiki Kaisha
Ngo Chuong Dinh
LandOfFree
Method and apparatus for arithmetic operation and recording... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for arithmetic operation and recording..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for arithmetic operation and recording... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2992245