4 ms·
All modern computers are implemented with binary digital logic. If you build the hardware the obvious, computing mod 256 is just masking the lower 8 bits or not
by AlotOfReading 4y ago
All modern computers are implemented with binary digital logic. If you build the hardware the obvious, computing mod 256 is just masking the lower 8 bits or nothing at all if it's an 8 bit register. Computing mod arbitrary N is equivalent to doing integer division, which is an inherently complex operation that's typically anywhere from 10-100x slower. It also scales much worse for very large operands.
- vbezhenar 4y agoThere were computers with triary digital logic. Can we make a computers which would store 251 values per bit (using variable voltage, for example, or something like that)?
- AlotOfReading 4y agoThere's no inherent reason you couldn't, but it'd almost certainly be faster, cheaper, and vastly more reliable to do it with binary logic. In actual practice what we typically do is select primes that are "near" a power of two, called the Mersenne primes (which have the form 2^N - 1) and Pseudo-Mersenne primes (2^N - a). These have special properties that let us work with them more efficiently. Modern algorithms for these kinds of special cases are branchless, divisionless, and constant time, even if they're not quite as fast as operations in the binary fields.