Back to results
US 11,379,230 B2Granted
Modulus calculation that leverages computer architecture and/or operand clustering
AssigneeLG Electronics Inc.
InventorsDayin Gou, Harsh Kupwade-Patil
Life of this patent
Estimating the term…
Abstract
Modulus operation is performed by a system in an efficient manner taking into account the system's processor and memory architecture. Other features are also provided.
Claims23
A method comprising:
- performing a first modulus operation by a system having a processor whose instruction set includes an instruction subset having one or more addition instructions and one or more multiplication instructions, wherein each instruction in the subset accepts an operand of a first size greater than one bit;
- wherein the first modulus operation has a dividend x and a divisor y;
- wherein performing the first modulus operation comprises:
- (1) obtaining, by the system, first components xi of the dividend x, each first component xi representing a sequence of consecutive bits of the dividend, each first component xi occupying, in a computer storage in the system, a number of bits which is divisible by the first size, the dividend being equal to a sum of first monomials such that each first monomial is a product of a corresponding first component and a corresponding power M1i of a value M1=2α1 where α1 is an integer greater than one and is divisible by the first size, wherein in at least one corresponding power M1i , an exponent i is positive;
- (2) for a set of one or more first monomials whose exponents are positive, obtaining by the processor, for each first monomial M1i in the set, a modulus (M1i % y);
- (3) for each first monomial, multiplying, by the processor, a corresponding first multiplicand by a corresponding second multiplicand to obtain a corresponding product, wherein:
- the corresponding first multiplicand is either the corresponding first component xi or the modulus (xi % y);
- the corresponding second multiplicand is either the corresponding power M1i or the modulus (M1i % y);
- wherein for at least one first monomial, the corresponding second multiplicand is the modulus (M1i % y);
- (4) obtaining, by the processor, a sum of the corresponding products;
- and
- (5) calculating the modulus (x % y) by the processor by using the sum of the corresponding products as a dividend instead of x.
9 more elements
A method comprising:
- performing a first modulus operation by a system having a processor whose instruction set includes an instruction subset having one or more addition instructions and one or more multiplication instructions, wherein each instruction in the subset accepts an operand of a first size greater than one bit;
- wherein performing the first modulus operation comprises:
- obtaining, by the processor, a dividend x for the first modulus operation, and a divisor y for the first modulus operation, each of the dividend x and the divisor y being represented in a memory by a number of bits divisible by the first size;
- determining, by the processor, a value xtmp equal to one of:
- xh*(M % y)+xl
- xh*(M % y)+(xl % y)
- where:
- xl is m least significant bits of x, where m is greater than the first size and is divisible by the first size,
- M=2m,
- xh is all the bits of m other than xl;
- calculating the modulus by the processor from the value xtmp, the modulus being calculated as a value xtmp % y.
8 more elements
A method comprising:
- performing a modulus operation by a system having a processor whose instruction set includes an instruction subset having one or more addition instructions and one or more multiplication instructions, wherein each instruction in the subset accepts an operand of a first size greater than one bit;
- wherein performing the modulus operation comprises:
- obtaining a dividend in a computer storage;
- obtaining a divisor in the computer storage;
- performing a process that obtains, from the dividend, a unit consisting of a plurality of consecutive bits of a first value congruent to the dividend modulo the divisor, the unit not including a number w of least significant bits of the first value, wherein w is divisible by the first size, and w is greater than a size of the divisor but the unit is otherwise independent of the size of the divisor in that the process provides the same unit for any divisor of a size less than w;
- determining, by the processor, a weight value for the unit, the weight value being congruent to 2w modulo the divisor and having a size smaller than w+1;
- and
- combining, by the processor, the weight value with the unit to determine a remainder of division of the dividend by the divisor.
5 more elements
A method for performing modulus operations for dividends x by a processor, the method comprising:
- storing, in a computer memory, a remainder (xB % y) for each of one or more values xB, wherein y is a divisor for each said modulus operation;
- receiving dividends x by the processor;
- for each dividend x, performing the corresponding one of said modulus operations, wherein performing each corresponding modulus operation comprises:
- calculating, by the processor, a difference between the dividend x and a corresponding one of said one or more values xB;
- and
- calculating, by the processor, a result of the corresponding modulus operation from the corresponding remainder (xB % y) and said difference.
3 more elements
Dependencies are inferred from the claim text.