Math Utilities
Quick reference
| GCD (Euclidean, mod version) | O(log(min(a,b))) |
| Primality check (trial division) | O(√n) |
| Modular exponentiation (fast power) | O(log n) |
| Bit operations (AND/OR/XOR/shift) | O(1) |
GCD (greatest common divisor) has a useful geometric picture. Imagine a rectangle, for example 18×12. You want to tile it exactly with the largest possible square, with no gaps and no overhang. The side length of that largest square is GCD(18, 12) = 6. You can find it this way: cut off the largest square that you can from the rectangle, and repeat on what is left. This is the same process as the Euclidean algorithm, but drawn instead of computed.
Modulo (%) is clock arithmetic. A 12-hour clock does not count 13, 14, 15. It goes back to 1, 2, 3. `13 % 12` is 1 for this reason. Modulo gives you the remainder after you wrap around each multiple of the divisor. It is the tool for anything cyclical: an index into a fixed-size buffer, a check for even or odd, and a way to spread values evenly across buckets.
A prime number cannot be tiled evenly by any square smaller than itself (except a 1×1 square). It has no whole-number factors except 1 and itself. Primes are the atoms of the integers. Each whole number greater than 1 is either prime or built from a multiplication of primes.
Below all of it, a computer has only two symbols: 0 and 1, called bits. Every number, character, and instruction is a pattern of bits. Operations such as AND, OR, XOR, and shift work directly on these patterns. They look low-level, but they are often the fastest tool, because they map directly onto what the hardware already does.
Core routines
// Euclidean GCD. The subtraction idea first, then the efficient form:
// GCD(a, b) == GCD(a - b, b) when a > b. If you subtract the smaller value from the
// larger value many times, you reach the same answer as the tiling picture above.
// The efficient version replaces many subtractions with one mod:
function gcd(a, b):
while b != 0:
a, b = b, a % b // a % b does many subtractions in one step
return aisPrime — trial division, O(√n)
function isPrime(n):
if n < 2:
return false
for i in range(2, int(sqrt(n)) + 1): // Factors always come in pairs that are
if n % i == 0: // on both sides of sqrt(n). So a check past
return false // sqrt(n) can never find a new factor.
return truemodPow — fast modular exponentiation via repeated squaring, O(log n)
function modPow(base, exp, mod):
result = 1
base = base % mod
while exp > 0:
if exp % 2 == 1: // odd exponent: fold in the current base
result = (result * base) % mod
exp = exp // 2 // halve the exponent...
base = (base * base) % mod // ...and square the base to match
return resultbit operations — AND / OR / XOR / shift, each O(1)
a & b // AND: 1 only where BOTH bits are 1 — used to mask or check specific bits
a | b // OR: 1 where EITHER bit is 1 — used to set specific bits
a ^ b // XOR: 1 where the bits DIFFER — a value XORed with itself is 0
a << k // left shift: multiply by 2^k
a >> k // right shift: divide by 2^k (integer division)
n & (n - 1) // Clears the lowest set bit. n-1 changes every trailing 0 to 1 and the
// lowest 1 to 0. So an AND with n turns that lowest 1 off.
x ^ x == 0 // Any value XORed with itself cancels to 0. This is the trick behind the
// "find the one unpaired value" problems.Fixed-width integer operations (bit operations, basic arithmetic) are O(1), because a CPU register holds a bounded number of bits. The hardware does the work in one step, for any value of the number. Everything below this assumption becomes more expensive as the numbers become larger.
| Operation | Time | Space | Why |
|---|---|---|---|
| GCD (Euclidean, mod version) | O(log(min(a,b))) | O(1) | Each step replaces (a, b) with (b, a % b). The smaller value reduces by at least half every two steps. So it takes a logarithmic number of steps to reach 0. |
| Primality check (trial division) | O(√n) | O(1) | You only need to test candidate factors up to √n. Any factor past that point would already appear with a smaller factor. |
| Modular exponentiation (fast power) | O(log n) | O(1) | If you square the base and halve the exponent at each step, you reach the answer in log₂(n) multiplications. The naive method multiplies the base by itself n times, which is O(n). |
| Bit operations (AND/OR/XOR/shift) | O(1) | O(1) | A fixed-width integer (32 or 64 bits) fits in one CPU register. The operation touches all bits at the same time in hardware, for any value of the number. |
GCD of 0 and negatives
By convention, GCD(0, 0) is 0 (no positive common divisor exists). GCD(a, 0) = |a|. For negative inputs, GCD uses the absolute value, so GCD(-12, 18) = GCD(12, 18) = 6, because divisibility does not depend on sign. But a naive mod-based implementation can return a negative result if you do not fix the signs first.
0, 1, and negatives are never prime
A prime number needs exactly two different positive divisors: 1 and itself. 0 has an infinite number of divisors. 1 has only one divisor (itself). Negative numbers are not part of the standard definition. All three are "not prime" by definition, not by a calculation. A common bug is a trial-division loop that never runs for n < 2 and returns true with no check.
Modulo of negative numbers is not universal
The `%` in Python always returns a result with the same sign as the divisor (true mathematical mod), so `-7 % 3` is `2`. The `%` in C, Java, and JavaScript follows the sign of the dividend instead (a truncating remainder), so `-7 % 3` is `-1` in those languages. If you port modulo-based logic (for example circular buffer indexing) between languages without attention to this, you make a common silent bug.
Integer overflow and sign bits in shifting
If you left-shift a signed integer far enough, you can push a 1 into the sign bit. This changes a positive number to a negative number in languages with fixed-width signed integers. Also, a shift of a fixed-width type by more bits than it has is undefined or implementation-specific in several languages. Bit tricks that work in a language with arbitrary-precision integers (like Python) can break with no error when you port them to a fixed-width language.
Sign in to mark problems done — progress syncs across devices.