David Gregg

A sparse matrix is a two-dimensional array where most of the elements are zero. If a very large sparse matrix is stored in normal array format, a huge amount of memory will be needed to store values that are almost all zero. Instead, large sparse matrices are normally stored in a compacted form, where only … 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

A sorting network is a notional model of a hardware circuit that can sort a fixed number of inputs. Sorting networks are made up of hardware comparator units connected together by a fixed network of wires so that the outputs of one comparator can become an input to another. Sorting networks can be implemented in … Read more

Multipliers can be relatively large pieces of hardware. We can multiply two n-bit integers with a simple long multiplication algorithm using a sequence of n n-bit additions. If we want to do the multiplication in a single cycle, we will need O(n^2) gates to do all the n-bit multiplications in one cycle. There are faster … Read more

Quicksort is one of the best-known algorithms in computer science. The algorithm selects one value from the array, which it calls the pivot. The array is then divided into two segments: values that are less than or equal to the pivot, and values that are greater than or equal to the pivot. If we partition … 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

Current processors typically support at least two variations of floating point arithmetic. Single precision (or binary32) numbers consist of 32 bits, including a sign bit, 8 exponent bits, and 23 bits to represent the most significant digits of the number. Double precision (or binary64) numbers provide 11 exponent bits, and 52 bits for the significant … Read more