David Gregg

Integer division and remainder are relatively complicated, expensive operations. Most modern processors have at least one integer multiplier unit that has both low latency (typically between 3 and 5 cycles) and high throughput (typically the unit can complete a multiply operation every cycle). In contrast, most modern processors do not have a fast integer division … Read more

Almost all modern processors provide special-purpose instructions for integer multiplication. However, some applications require integer values that are larger than fit in a single machine word, such as 256 bit integers. We can multiply these big integer values using a sequence of smaller multiplies. For example, multiplying two 256-bit integer values might be completed with … Read more

In some applications, such as many cryptography algorithms, multiplication by a known integer constant is a common operation. It’s well known that integer multiplication with a constant can be computed with a sequence of shifts and adds. Most modern processors already have fast integer multiplication units, so in software it is usually faster to use … Read more

Matrix multiplication is one of the commonly-used computations across a wide range of applications. For example, most implementations of neural networks implement very large numbers of matrix multiplications. Almost all processor and GPU manufacturers provide libraries with carefully hand-tuned fast matrix multiplication routines. All the best-known algorithms matrix multiplication are out-of-place; that is, the result … Read more

Modular arithmetic is commonly used in cryptographic schemes such as elliptic curve cryptography. A modular number system can represent whole numbers in the range 0 up to some value p-1, where p is the modulus. Modular number systems wrap around. For example, if the modulus is 7, then (4 + 6) mod 7 = 10 … Read more

ABC is an open-source logic synthesis and optimization tool developed by Alan Mishchenko at the University of California at Berkeley. ABC specializes in optimizing digital logic circuits at the circuit level, and some commercial hardware synthesis tools incorporate ABC as part of their design flow to improve their circuit optimization. ABC is a large logic … Read more