Integrated circuit, computer system, and related methods for three-dimensional (3D) graphics and modular operations

1 . An integrated circuit, comprising:

a cache;

one or more registers;

one or more digital circuits; and

a control unit (CU) configured to control execution of operations for computing modular coordinates for an integer relative to a modulus, the operations comprising:

fetching, from the cache, one or more folding constants, wherein the one or more folding constants are precomputed using the modulus;

fetching, from the cache, a reciprocal constant, wherein the reciprocal constant is precomputed using the modulus;

loading the integer, the modulus, the one or more folding constants and the reciprocal constant into a set of first registers;

decomposing, using one or more hardwired operations, the integer into binary chunks;

computing, using the one or more digital circuits, an intermediate folded value, wherein the intermediate folded value is a sum of products of each folding constant and its corresponding binary chunk;

normalizing, using the one or more digital circuits, the intermediate folded value by using a bounded number of subtraction operations to obtain a normalized residue;

computing, using the one or more digital circuits, a spin estimate, wherein the spin estimate comprises one or more high bits of a product of the integer and the reciprocal constant;

obtaining, using the one or more digital circuits, a corrected spin from the spin estimate; and

outputting, to a set of second registers, the normalized residue and the corrected spin as a coordinate pair.

2 . The integrated circuit of claim 1 , wherein the modulus is a product of one or more small prime integers and is approximate to a power of two.

3 . The integrated circuit of claim 1 , wherein the one or more folding constants are equal to one or more remainders of a base corresponding to a size of the binary chunks, taken to an integer power corresponding to a number of binary chunks, modulo the modulus.

4 . The integrated circuit of claim 1 , wherein the reciprocal constant is equal to a floor of a quotient of two to a power of a bit-width of the integer divided by the modulus.

5 . The integrated circuit of claim 1 , wherein computing, using the one or more digital circuits, the intermediate folded value, further comprises:

computing in parallel, using one or more digital circuits, a product of each folding constant and its corresponding binary chunk.

6 . The integrated circuit of claim 1 , wherein the operations for computing modular coordinates for the integer relative to the modulus further comprise a streaming update logic for consecutive integers operating on stored residue and spin state, the streaming update logic comprising:

advancing, using the one or more digital circuits, a register storing the integer to a subsequent integer value;

incrementing, using the one or more digital circuits, the normalized residue by one;

determining, using the one or more digital circuits, if the normalized residue is greater than or equal to the modulus; and

when the normalized residue is greater than or equal to the modulus:

wrapping, using the one or more digital circuits, the normalized residue by subtracting the modulus; and

incrementing, using the one or more digital circuits, the corrected spin by one.

7 . The integrated circuit of claim 1 , wherein obtaining, using the one or more digital circuits, the corrected spin from the spin estimate, further comprises:

determining, using the one or more digital circuits, whether a check value derived from the integer, the modulus, and the spin estimate indicates that the spin estimate underestimates a floor of a quotient of the integer divided by the modulus;

when the spin estimate underestimates the floor of a quotient of the integer divided by the modulus, incrementing, using the one or more digital circuits, the spin estimate a bounded number of times to obtain the corrected spin;

determining, using the one or more digital circuits, whether the check value derived from the integer, the modulus, and the spin estimate indicates that the spin estimate overestimates a floor of a quotient of the integer divided by the modulus; and

when the spin estimate overestimates the floor of a quotient of the integer divided by the modulus, decrementing, using the one or more digital circuits, the spin estimate a bounded number of times to obtain the corrected spin.

8 . The integrated circuit of claim 1 , further comprising:

an arithmetic logic unit (ALU), wherein the ALU includes the one or more digital circuits.

9 . A computing system for processing three-dimensional (3D) graphics comprising:

a processor;

a graphics processing unit (GPU); and

one or more memories, having stored thereon computer-executable instructions for computing modular coordinates for a set of integers representing vertices of a triangle in a three-dimensional (3D) graphical space, relative to a modulus, that when executed, cause the computing system to:

retrieve, from the one or more memories, one or more folding constants, wherein the one or more folding constants are precomputed using the modulus;

retrieve, from the one or more memories, a reciprocal constant, wherein the reciprocal constant is precomputed using the modulus;

decompose, via the processor, each integer vertex into binary chunks;

compute, via the processor, an intermediate folded value for each integer vertex, wherein the intermediate folded value is a sum of products of each folding constant and its corresponding binary chunk;

normalize, via the processor, the intermediate folded value for each integer vertex by using a bounded number of subtraction operations to obtain a normalized residue;

compute, via the processor, a spin estimate for each integer vertex, wherein the spin estimate comprises one or more high bits of a product of an integer vertex and the reciprocal constant;

obtain, via the processor, a corrected spin from the spin estimate; and

output, via the processor, to the GPU, for each integer vertex the normalized residue and the corrected spin as coordinate pairs.

10 . The computing system of claim 9 , wherein the modulus is a product of one or more small prime integers and is approximate to a power of two.

11 . The computing system of claim 9 , wherein the one or more folding constants are equal to one or more remainders of a base corresponding to a size of the binary chunks, taken to an integer power corresponding to a number of binary chunks, modulo the modulus.

12 . The computing system of claim 9 , wherein the reciprocal constant is equal to a floor of a quotient of two to a power of a bit-width of the integer vertex divided by the modulus.

13 . The computing system of claim 9 , the computer-executable instructions for computing modular coordinates for the set of integers representing vertices of a triangle in 3D graphical space, relative to the modulus further comprising:

advancing, via the processor, an integer value stored in memory to a subsequent integer value;

incrementing, via the processor, the normalized residue by one;

determining, via the processor, if the normalized residue is greater than or equal to the modulus; and

when the normalized residue is greater than or equal to the modulus:

wrapping, via the processor, the normalized residue by subtracting the modulus; and

incrementing, via the processor, the corrected spin by one.

14 . The computing system of claim 9 , obtaining, via the processor, a corrected spin from the spin estimate, further comprises:

determining, via the processor, whether a check value derived from the integer vertex, the modulus, and the spin estimate indicates that the spin estimate underestimates a floor of a quotient of the integer vertex divided by the modulus;

when the spin estimate underestimates the floor of a quotient of the integer vertex divided by the modulus, incrementing, via the processor, the spin estimate a bounded number of times to obtain the corrected spin;

determining, via the processor, whether a check value derived from the integer vertex, the modulus, and the spin estimate indicates that the spin estimate overestimates a floor of a quotient of the integer vertex divided by the modulus; and

when the spin estimate overestimates the floor of a quotient of the integer vertex divided by the modulus, decrementing, via the processor, the spin estimate a bounded number of times to obtain the corrected spin.

15 . The computing system of claim 14 , wherein the GPU uses the coordinate pairs to perform a graphical processing operation, wherein the graphical processing operation includes (i) screen wrapping, (ii) texture tiling, (iii) pattern animation, (iv) pixel dithering, or (v) processing a polygonal mesh.

16 . The computing system of claim 15 , wherein the graphical processing operation is performed to project a three-dimensional object onto a two-dimensional display.

17 . The computing system of claim 9 , wherein

k

i

=

2

B

i

⁢

mod

⁢

W

where k i are the one or more folding constants, B i are starting bit positions for the ith binary chunk, and W is the modulus.

18 . The computing system of claim 17 , wherein

r

raw

=

∑

i

=

0

n

-

1

a

i

⁢

k

i

where r raw is the intermediate folded value prior to normalization, n corresponds to a number of binary chunks derived from a bit-width of an integer and a chosen chunk size and a i are one or more binary chunks.

19 . The computing system of claim 9 , wherein

μ

=

⌊

2

b

W

⌋

where μ is the reciprocal constant, b is a selected bit-width, and W is the modulus.

20 . The computing system of claim 9 , wherein

s

est

=

HIGH

(

N

*

μ

)

where s est is the spin estimate, N is an integer, μ is the reciprocal constant, and HIGH is a high-bit extraction operator that returns upper bits of a double-width product.