# US 10,768,898 B2 · Efficient modulo calculation

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 10,768,898 B2
- Document ID: US10768898B2
- Status: Granted
- Kind: B2
- Application number: 16/712,048
- Filed: 2019-12-12
- Published: 2020-04-16
- Granted: 2020-09-08
- Earliest claimed: 2015-05-27
- Assignees: Imagination Technologies Limited
- Applicants: Imagination Technologies Limited
- Inventors: Simon Fenney
- Web page: https://patentgrep.com/patent/US10768898B2

## CPC

- G06F 7/729: {using representation by a residue number system}
- G06F 5/01: for shifting, e.g. justifying, scaling, normalising {(digital stores in which the information is moved stepwise, e.g. shift-registers G11C19/00; digital stores in which the information circulates G11C21/00)}
- G06F 7/483: Computations with numbers represented by a non-linear combination of denominational numbers, e.g. rational numbers, logarithmic number system or floating-point numbers {(G06F7/4806, G06F7/4824, G06F7/49, G06F7/491, G06F7/544 take precedence)}
- G06F 7/72: using residue arithmetic
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Hardware logic is arranged to efficiently perform modulo calculation with respect to a constant value b. The hardware logic comprises a series of addition units (each comprising a plurality of binary adders). A first stage addition unit in the series groups bits from an input number into a number of strings, multiplies each string by a corresponding coefficient using adders and left-shifting and adds the resulting strings together to generate an intermediate value which, in most examples, has a smaller range of possible values than the input number. The series of addition units also includes a second stage addition unit and/or a final stage addition unit. A second stage addition unit uses similar methods to generate an updated intermediate value in a pre-defined terminating range. A final stage addition unit generates a final result from the final intermediate result output by an immediately previous addition unit in the series.

## Claims

### Claim 1

An apparatus comprising hardware logic arranged to perform modulo calculation with respect to a constant value b, the hardware logic comprising a unit arranged to:
receive an input n-bit value;
generate at least one string from one or more bits of the value and a corresponding coefficient, wherein the corresponding coefficient comprises a selected one of 2i mod b and (2i mod b)−b having a smaller absolute magnitude and where i is a bit index of a least significant input bit in the string;
add together the at least one string and one or more further strings to generate an output value; and
output the output value.

### Claim 2 (depends on 1)

The apparatus according to claim 1, wherein the unit is arranged to generate at least one string from one or more bits of the value and a corresponding coefficient by grouping the bits of the value received by the unit into a plurality of strings to minimize a range of possible values of the output value.

### Claim 3 (depends on 1)

The apparatus according to claim 1, wherein at least one of the strings generated in the unit is generated from a plurality of contiguous bits from the value received by the unit.

### Claim 4 (depends on 1)

The apparatus according to claim 1, wherein at least one of the strings generated in the unit is generated from a plurality of non-contiguous bits from the value received by the unit.

### Claim 5 (depends on 1)

The apparatus according to claim 1, wherein at least one of the strings generated in the unit is generated from one or more bits of the value and at least one a repeated bit.

### Claim 6 (depends on 1)

The apparatus according to claim 1, wherein at least one of the strings generated in the unit is generated from bits arranged in a different order to the input value.

### Claim 7 (depends on 1)

The apparatus according to claim 1, wherein at least one bit of the value received by the unit is used to generate two or more different strings in the unit.

### Claim 8 (depends on 1)

The apparatus according to claim 1, wherein the unit is arranged to generate at least one string from one or more bits of the value and a corresponding coefficient by
pre-combining two or more bits of the value received by the unit using a logic element and generating the string from at least the pre-combined bits and the corresponding coefficient.

### Claim 9 (depends on 1)

The apparatus according to claim 1, wherein the corresponding coefficient for a bit of the input value is one of:
i. a positive coefficient value in [0, . . . ,b−1] which is congruent to 2i mod b;
ii. a coefficient equal to (2i mod b) or ((2i mod b)−b) which has a smaller absolute magnitude and where i is a bit index for the bit;
iii. whichever of (2i mod b) or ((2i mod b)−b) has a larger absolute magnitude provided it can be formed from fewer powers of two via addition or subtraction than the smaller magnitude value from (ii) or is less in magnitude than b and is a 2× multiple of another bit's coefficient;
iv. a coefficient according to (ii) or (iii), wherein the coefficient is selected by evaluating a plurality of combinations of coefficient choices for each bit using a cost metric;
v. a coefficient selected according to any of (i)-(iv) which is a signed power of two and has an absolute magnitude which does not exceed K*b where K is a natural number; and
vi. a coefficient selected according to any combination of (i)-(v) to minimise the cost metric.

### Claim 10 (depends on 7)

The apparatus according to claim 7, wherein the cost metric comprises at least one of:
a) a number of bits required to represent any value in the range [Minx, Maxx];
b) a result of evaluating (Maxx−Minx);
c) a result of evaluating max(−Minx, Maxx); and
d) a sum over all bits of a cost parameter associated with each coefficient, the cost parameter comprising a size of a smallest set of powers of two such that there exists an expression involving sums and differences of that set which equates to the coefficient.

### Claim 11 (depends on 1)

The apparatus according to claim 1, wherein the apparatus is a processor.

### Claim 12 (depends on 1)

The apparatus according to claim 1 wherein the hardware logic comprises a single unit only.

### Claim 13 (depends on 1)

The apparatus according to claim 1, wherein the input n-bit value is a value output by an immediately previous unit.

### Claim 14 (depends on 1)

The apparatus according to claim 1, wherein the output value is in a pre-determined terminating range.

### Claim 15 (depends on 1)

The apparatus according to claim 1, wherein the pre-defined terminating range is one of [−b, b−1], [−b, b], [0, 2b−1] or [−b, 2b−1].

### Claim 16

A non-transitory computer readable storage medium having stored thereon computer readable instructions that, when processed at a computer system for generating a manifestation of an integrated circuit, cause the computer system to generate a manifestation of an integrated circuit arranged to perform modulo calculation, the integrated circuit comprising a unit arranged to:
receive an input n-bit value;
generate at least one string from one or more bits of the value and a corresponding coefficient, wherein the corresponding coefficient comprises a selected one of 2i mod b and (2i mod b)−b having a smaller absolute magnitude and where i is a bit index of a least significant input bit in the string;
add together the at least one string and one or more further strings to generate an output value; and
output the output value.

### Claim 17

A method of manufacturing, using an integrated circuit manufacturing system, an integrated circuit comprising hardware logic arranged to perform modulo calculation with respect to a constant value b, the hardware logic comprising a unit arranged to
receive an input n-bit value;
generate at least one string from one or more bits of the value and a corresponding coefficient, wherein the corresponding coefficient comprises a selected one of 2i mod b and (2i mod b)−b having a smaller absolute magnitude and where i is a bit index of a least significant input bit in the string;
add together the at least one string and one or more further strings to generate an output value; and
output the output value.