On this page

Module 8 · Math for Algorithms

Many algorithm problems turn out to be maths problems. "Count the arrangements, modulo " is combinatorics plus modular arithmetic. "Is this 19-digit number prime?" is number theory. "Multiply two polynomials of degree a million" is the fast Fourier transform. "Does this polygon contain that point?" is geometry with cross products. "Who wins this stone-taking game?" is the Sprague–Grundy theorem. In each case the code is short and the insight is mathematical. Without the maths you write a brute force that times out; with it you write ten lines that run in microseconds.

Module 8 teaches the maths that algorithms actually use, at the depth needed to implement it correctly: proofs where they show why the code works, worked numbers you can check by hand, and the overflow and precision traps that turn a correct formula into a wrong answer. It is not a maths course. Every lesson starts from a programming problem and ends with tested code in Python, Java, C++ and TypeScript.

The module is in the DSA: Zero to Mastery course. Previous module: Module 7 · String Algorithms. Next: Module 9 · Advanced Algorithms.

What this module covers

Nine lessons and a capstone, in four arcs.

Arc 1 — the integers. Number Theory I covers divisibility, primes, Euclid's GCD with its proof and Fibonacci worst case, extended Euclid and Bézout's identity, linear Diophantine equations, the sieve of Eratosthenes, the linear sieve with smallest prime factors, and factorization with divisor counts. Modular Arithmetic is clock arithmetic for programmers: how % treats negatives in each language, fast exponentiation, modular inverses, Euler's totient, the Chinese Remainder Theorem, why everyone uses and , safe 64-bit multiplication, factorial tables, and RSA end to end. Number Theory II goes further: Miller–Rabin and Pollard's rho for 64-bit numbers, primitive roots, discrete logarithms, multiplicative functions and Möbius inversion, and divisor blocks for sums of in .

Arc 2 — counting and chance. Combinatorics covers binomial coefficients modulo a prime (and Lucas' theorem when ), stars and bars, inclusion–exclusion, Catalan and Stirling numbers, and Burnside's lemma for counting up to symmetry. It builds on the recurrences in Counting DP. Probability & Expected Value covers linearity of expectation (the most useful trick in the module), indicator variables, expected values modulo a prime, geometric waiting times and coupon collecting, tail bounds (Markov, Chebyshev, Chernoff), the birthday paradox and balls into bins. It is the algorithmic side of Probability for Engineers.

Arc 3 — algebra and signals. Linear Algebra covers Gaussian elimination over the reals, modulo a prime and over XOR (GF(2)), determinants, rank, the XOR basis, and the matrix view of Matrix Exponentiation. FFT & NTT multiplies polynomials and big integers in with complex roots of unity (FFT) or modular ones (NTT), and shows where convolution hides in string matching and counting problems.

Arc 4 — space and play. Computational Geometry builds everything from the cross product: orientation, segment intersection, polygon area (the shoelace formula), point-in-polygon, convex hull, and the sweep line, with integer arithmetic wherever possible to dodge floating-point error. Game Theory covers impartial games, Nim and the Sprague–Grundy theorem, and links back to Game DP for games that are not impartial.

Capstone. Capstone combines several of the module's tools into one tested and benchmarked project; its page gives the full brief.

Already on Archon. Two existing pages sit next to this module: Probability for Engineers (distributions, Bayes, the birthday paradox, applied to systems) and System Design Math (back-of-envelope estimation, powers of two, latency numbers, QPS and storage maths). Read them whenever a lesson here mentions them.

How the topics connect

flowchart TD
    NT1["Number Theory I: GCD, primes, sieves"] --> MOD["Modular Arithmetic: powmod, inverses, CRT"]
    MOD --> NT2["Number Theory II: Miller-Rabin, Pollard rho, discrete log"]
    MOD --> COMB["Combinatorics: binomials mod p, inclusion-exclusion"]
    COMB --> PROB["Probability & Expected Value"]
    MOD --> LA["Linear Algebra: Gaussian elimination, XOR basis"]
    MOD --> FFT["FFT & NTT: fast polynomial multiplication"]
    DC["Module 5 · Divide & Conquer"] --> FFT
    LA --> FFT
    GEO["Computational Geometry: cross products, hulls"]
    GT["Game Theory: Nim, Sprague-Grundy"]
    BIT["Module 5 · Bit Manipulation"] --> GT
    PROB --> CAP["Capstone"]
    FFT --> CAP
    NT2 --> CAP
    GEO --> CAP
    GT --> CAP
    CAP --> M9["Module 9 · Advanced Algorithms"]

Arrows mean "read this first". Geometry and game theory depend only on earlier modules, so you can read them at any point; the number-theory chain should be read in order.

Which math tool? A trigger table

When a problem has one of these shapes, this is the lesson to open first.

If the problem says or has…Reach for…Lesson
"simplify the fraction", "when do the cycles line up", "smallest number divisible by all"GCD, LCMNumber Theory I
"integers with ", jugs measuring an amountExtended Euclid, BézoutNumber Theory I
"all primes up to ", "smallest prime factor", "number of divisors"Sieves, factorizationNumber Theory I
"answer modulo ", with huge , division under a modulusModular arithmetic, fast power, inversesModular Arithmetic
"", cycles with offsetsChinese Remainder TheoremModular Arithmetic
"is this 64-bit number prime?", "factor a number up to "Miller–Rabin, Pollard's rhoNumber Theory II
"", "count coprime pairs", sums of Discrete log, Möbius, divisor blocksNumber Theory II
"how many ways", "choose of ", "paths on a grid", "distribute identical balls"Binomials, stars and barsCombinatorics
"count those satisfying none of the conditions"Inclusion–exclusionCombinatorics
"up to rotation / reflection"Burnside's lemmaCombinatorics
"expected number of", "probability that", "output "Linearity of expectation, indicatorsProbability & Expected Value
A system of linear equations, "XOR of a subset equals", rank, determinantGaussian elimination, XOR basisLinear Algebra
"-th term of a linear recurrence", up to Matrix exponentiationMatrix Exponentiation
"multiply two polynomials / big numbers", "all pairwise sums", modulus 998244353FFT, NTT, convolutionFFT & NTT
Points, segments, polygons, "left turn", "area", "enclosing fence"Cross product, convex hullComputational Geometry
Two players, alternate moves, "who wins with optimal play", several independent pilesNim, Grundy numbersGame Theory
Two players maximising a score differenceMinimax DPGame DP
"estimate", "how many servers", "how much storage"Back-of-envelope arithmeticSystem Design Math

Two habits make this table work. First, compute small cases by brute force and look at the numbers — a sequence like 1, 2, 5, 14, 42 is Catalan, and searching the OEIS for your first few terms is a legitimate technique. Second, decide the number type before you write the formula: will the true answer fit in 64 bits, does the problem want it modulo a prime, or do you need exact big integers or floating point? The next section is about that decision.

Overflow and precision primer

Mathematical formulas are exact; machine numbers are not. Most wrong answers in maths-heavy problems are not wrong formulas but wrong number types. This primer is the reference the lessons point back to.

Integer limits you should know by heart

TypeRangeApproximatelyWhat fits
signed 32-bit (int) to One residue mod , and the sum of two
unsigned 32-bit to
signed 64-bit (long, long long, i64) to Product of two residues mod ; ; Fibonacci
unsigned 64-bit to Wraps modulo by definition, handy for hashing
__int128 (GCC/Clang)Product of two 64-bit values
IEEE double, exact integersJavaScript's only number type

Three numbers to remember: is the first factorial that overflows signed 64-bit; is the first Fibonacci number that does; and fits in signed 64-bit but not in a double's exact range.

How each language misbehaves

C++JavaPythonJavaScript / TypeScript
Signed overflowUndefined behaviour — the optimiser may assume it never happens and delete your checkWraps silently (two's complement)Never: int is arbitrary precisionNot an integer type: precision loss above , silently
Wider integer__int128 (GCC/Clang only, no cout support), or a big-integer library (Boost.Multiprecision, GMP)BigInteger in java.mathBuilt inBigInt (123n): arbitrary precision, cannot mix with number in arithmetic, no Math.* functions, slower
Detect overflow__builtin_mul_overflow(a, b, &r); -fsanitize=undefined in testsMath.addExact, Math.multiplyExact throw ArithmeticException—Number.isSafeInteger(x) after the fact
High half of a 64×64 product(unsigned __int128)a * b >> 64Math.multiplyHigh (Java 9+)—BigInt
Bitwise operators64-bit on 64-bit types64-bit on longArbitrary widthConvert to 32-bit signed: `2**32
% with negativesSign of the dividendSign of the dividend (Math.floorMod for non-negative)Sign of the divisorSign of the dividend
Gotchaint * int overflows before assignment to long long: write 1LL * a * bint * int likewise; Integer caching makes == on boxed values unreliableint→str of more than 4,300 digits raises ValueError since Python 3.11 (sys.set_int_max_str_digits)Number.MAX_SAFE_INTEGER + 2 === Number.MAX_SAFE_INTEGER + 1 is true

The Modular Arithmetic lesson has the full table for % and the safe-multiplication options (128-bit products, double-and-add, Montgomery, Barrett).

Choosing the number type

  1. Estimate the largest intermediate value, not just the answer. fits whenever the answer does, but does not. A sum of products of two values up to is up to .
  2. If the problem asks for an answer modulo a prime, reduce after every operation and keep everything in 64-bit (or in number with the split multiplication trick, or BigInt, in JavaScript).
  3. If the exact value can exceed 64 bits but only a little (products of two 64-bit numbers), use __int128 in C++ or Math.multiplyHigh/BigInteger in Java.
  4. If the exact value is genuinely huge (big factorials, exact rationals), use big integers and accept the slowdown — or change the algorithm to avoid them (compare logarithms, compare fractions by cross-multiplying in 128 bits).
  5. Use floating point only for genuinely real-valued answers (probabilities, geometry with real coordinates), and never for exact counting.

Floating-point precision in one minute

An IEEE 754 double has a 53-bit significand: about 15–16 significant decimal digits, and machine epsilon . So:

  • 0.1 + 0.2 == 0.3 is false in every language listed here (0.30000000000000004).
  • Never compare doubles with ==. Compare with a tolerance suited to the magnitudes: abs(a - b) <= eps * max(1, abs(a), abs(b)), with eps around for typical contest geometry.
  • Subtracting nearly equal numbers loses digits (catastrophic cancellation); prefer formulas that avoid it, and sum many small values with Kahan summation or by sorting first.
  • In geometry with integer coordinates, stay in integers: cross products, the shoelace formula (twice the area is an integer) and orientation tests are exact in 64-bit as long as coordinates are below about (products then stay under ). Computational Geometry is built on this rule.
  • long double is 80-bit extended precision (64-bit significand) with GCC on x86, but the same as double with MSVC and 128-bit quad on some ARM platforms — do not rely on it for portability.
  • Math.floor(Math.sqrt(n)) can be off by one for large ; use an integer square root (math.isqrt in Python) or correct the float result, as the Number Theory I code does.

A quick self-check in four languages

Each program checks the facts above on the language it runs in.

import math
import sys

assert 2**63 - 1 == 9_223_372_036_854_775_807          # just a number in Python: no overflow
assert math.factorial(20) < 2**63 - 1 < math.factorial(21)
assert float(2**53) == float(2**53 + 1)                   # doubles lose exactness past 2^53
assert 0.1 + 0.2 != 0.3 and math.isclose(0.1 + 0.2, 0.3)
assert -7 % 3 == 2                                        # sign of the divisor
assert math.isqrt(10**30 - 1) == 10**15 - 1               # exact integer square root
limit = getattr(sys, "get_int_max_str_digits", lambda: 0)()   # Python 3.11+: 4300 by default
if 0 < limit < 5000:
    try:
        str(10**5000)                                       # 5001 digits
        raise AssertionError("expected ValueError")
    except ValueError:
        pass
print("python primer checks passed")
import java.math.BigInteger;

public class Primer {
    public static void main(String[] args) {
        if (Long.MAX_VALUE != 9_223_372_036_854_775_807L) throw new AssertionError();
        if (Long.MAX_VALUE + 1 != Long.MIN_VALUE) throw new AssertionError("wraps");
        boolean threw = false;
        try { Math.multiplyExact(3_037_000_500L, 3_037_000_500L); } catch (ArithmeticException e) { threw = true; }
        if (!threw) throw new AssertionError("multiplyExact should throw");
        long f = 1;
        for (int i = 2; i <= 20; i++) f = Math.multiplyExact(f, i);   // 20! fits
        if (f != 2_432_902_008_176_640_000L) throw new AssertionError("20!");
        BigInteger f21 = BigInteger.valueOf(f).multiply(BigInteger.valueOf(21));
        if (f21.bitLength() <= 63) throw new AssertionError("21! should not fit");
        int a = 1_000_000_007 - 1;
        if ((long) a * a == (long) (a * a)) throw new AssertionError("int*int overflows first");
        if (-7 % 3 != -1 || Math.floorMod(-7, 3) != 2) throw new AssertionError("%");
        if (0.1 + 0.2 == 0.3) throw new AssertionError("float");
        System.out.println("java primer checks passed");
    }
}
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdint>
#include <iostream>

int main() {
    static_assert(LLONG_MAX == 9223372036854775807LL, "64-bit long long");
    long long r;
    assert(__builtin_mul_overflow(3037000500LL, 3037000500LL, &r));   // detects overflow
    long long f = 1;
    for (int i = 2; i <= 20; ++i) f *= i;                             // 20! fits
    assert(f == 2432902008176640000LL);
    assert(__builtin_mul_overflow(f, 21LL, &r));                      // 21! does not
    unsigned __int128 big = (unsigned __int128)UINT64_MAX * UINT64_MAX;
    assert((uint64_t)(big >> 64) == UINT64_MAX - 1);                  // high half of the product
    int a = 1000000006;
    assert(1LL * a * a == 1000000012000000036LL);                     // widen BEFORE multiplying
    assert(-7 % 3 == -1 && ((-7 % 3) + 3) % 3 == 2);
    assert(0.1 + 0.2 != 0.3 && std::fabs(0.1 + 0.2 - 0.3) < 1e-12);
    std::cout << "c++ primer checks passed\n";
}
function check(cond: boolean, msg: string): void {
  if (!cond) throw new Error("FAILED: " + msg);
}

check(Number.MAX_SAFE_INTEGER === 2 ** 53 - 1, "max safe");
check(Number.MAX_SAFE_INTEGER + 2 === Number.MAX_SAFE_INTEGER + 1, "precision loss above 2^53");
check(!Number.isSafeInteger(1_000_000_006 * 1_000_000_006), "product of residues is not safe");
check(1_000_000_006n * 1_000_000_006n === 1_000_000_012_000_000_036n, "BigInt is exact");
check((2 ** 32 | 0) === 0 && (2 ** 31 | 0) === -(2 ** 31), "bitwise ops are 32-bit");
check(-7 % 3 === -1, "sign of the dividend");
check(0.1 + 0.2 !== 0.3 && Math.abs(0.1 + 0.2 - 0.3) < 1e-12, "float tolerance");
let f = 1n;
for (let i = 2n; i <= 21n; i++) f *= i;
check(f > 2n ** 63n - 1n, "21! exceeds int64");
console.log("ts primer checks passed");

Why in this order

The order follows dependencies.

  1. Number Theory I first, because the integers are the most exact objects a computer handles, and GCD and extended Euclid are used by almost everything later: modular inverses, CRT, rational arithmetic, Diophantine equations. The sieve's analysis also introduces the style of argument that reappears in complexity proofs.
  2. Modular Arithmetic second, because it needs extended Euclid for inverses and factorization for the totient, and because every later lesson computes "modulo a prime": binomials, expected values, Gaussian elimination, NTT.
  3. Number Theory II third: Miller–Rabin, Pollard's rho and discrete logarithms are fast exponentiation and CRT applied cleverly, and they need both previous lessons.
  4. Combinatorics next, because counting formulas need factorial tables modulo a prime (Modular Arithmetic) and Lucas' theorem (CRT-style reasoning). It continues where Counting DP stopped: closed forms instead of recurrences.
  5. Probability & Expected Value after counting, because a probability is often "favourable count / total count", and because "output the expectation modulo " needs modular inverses.
  6. Linear Algebra before FFT, because Gaussian elimination modulo a prime reuses inverses, and because the FFT is easiest to understand as evaluating a polynomial at special points — a matrix–vector product with a very structured matrix.
  7. FFT & NTT after Modular Arithmetic, Linear Algebra and Divide & Conquer: the NTT needs roots of unity modulo , and the FFT's is a divide-and-conquer recurrence.
  8. Computational Geometry is independent of arcs 1–3 but needs the precision primer above; it comes late because its hardest bugs are numeric.
  9. Game Theory last: Nim's solution is an XOR (Bit Manipulation) and its proof is an induction over game states like Game DP.
  10. The capstone combines lessons from several arcs.

Prerequisites

From Module 0: Complexity Analysis and Recursion & Induction — most proofs in this module are inductions. From Module 5: Bit Manipulation (binary exponentiation walks the bits of the exponent; Nim is XOR) and Divide & Conquer (Karatsuba is the warm-up for FFT). From Module 6: Counting DP, Matrix Exponentiation, Probability DP and Game DP, each of which this module revisits with closed forms. From Module 7: String Hashing, which is modular arithmetic on strings.

School algebra is enough: we define every term (prime, congruence, inverse, determinant, root of unity) at first use. As in every module, each canonical implementation is given in Python, Java, C++ and TypeScript and checks itself with assertions.

Lessons

#LessonAfter it you will be able to…Minutes
1Number Theory I: Divisibility, Primes, GCD & SievesProve and implement Euclid and extended Euclid, solve , sieve primes and smallest prime factors, factorize and count divisors70
2Modular ArithmeticCompute powers, inverses, totients and CRT solutions without overflow in four languages, and explain RSA75
3Number Theory IITest and factor 64-bit numbers, find primitive roots and discrete logs, use Möbius inversion75
4CombinatoricsCount with binomials, stars and bars, inclusion–exclusion and Burnside, modulo a prime70
5Probability & Expected ValueUse linearity of expectation and indicators, and output expectations modulo a prime60
6Linear AlgebraSolve linear systems over reals, and GF(2), compute rank and determinants, build an XOR basis65
7FFT & NTTMultiply polynomials and big integers in and spot convolutions in disguise80
8Computational GeometryUse cross products for orientation, intersection, area and point-in-polygon, and build a convex hull robustly75
9Game TheorySolve Nim and compute Grundy numbers for sums of impartial games50
—CapstoneCombine the module's tools in one tested, benchmarked project180–240

Lesson time totals about 620 minutes, roughly 10 hours, plus 3 to 4 hours for the capstone and about as much again for the practice ladders. Two to three weeks at an hour a day is realistic; the number-theory chain alone is a good first week.

How to study this module

Recompute every worked example. Each lesson traces its algorithms on small numbers: Euclid on , extended Euclid on , by square-and-multiply, Sunzi's remainder puzzle. Do them with pencil and paper before reading the table. Number theory is unforgiving of "roughly right".

Write the brute force and compare. A maths shortcut is a claim that two computations agree. Check it: compare gcd with a loop over divisors, the sieve with trial division, CRT with a search over , a counting formula with enumeration for . Every implementation in this module does exactly this in its tests, following Testing & Debugging Algorithms.

Pick the number type first. Before coding a formula, write down the largest intermediate value and choose the type from the primer above. Most "my formula is right but the judge says wrong answer" bugs are overflow or precision.

Learn the proofs that explain the code. You do not need to memorise proofs, but a few are the code: why , why the sieve can start at , why is an inverse, why a CRT system with non-coprime moduli can be inconsistent. If you can say those in a sentence, you will not mis-implement them.

Climb the ladders. Each lesson ends with 10–15 problems from easy to hard. Do the first half after reading; return to the rest after the next lesson, since many hard number-theory problems combine two lessons.

Start with Number Theory I, then follow the table in order. Previous module: String Algorithms. Next module: Advanced Algorithms. Course map: DSA: Zero to Mastery.