Number algorithms

Introduction

Three short algorithms about whole numbers, each far faster than the obvious method. They are used everywhere from fractions to cryptography, and in almost every programming contest.

Number problems often have an obvious slow method and a beautiful fast one. These three are some of the oldest algorithms there are, and they are still used in cryptography today.

How it works

Euclid's GCD

#include <stdio.h>

int gcd(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int main(void) {
    int a = 84, b = 36;
    int g = gcd(a, b);
    printf("gcd(%d, %d) = %d\n", a, b, g);
    printf("lcm(%d, %d) = %d\n", a, b, a / g * b);
    return 0;
}

The greatest common divisor of a and b does not change when you replace a by a % b: anything that divides both a and b also divides the remainder. So gcd(a, b) = gcd(b, a % b), until b is 0. The numbers shrink at least by half every two steps: O(log min(a, b)), a few dozen steps even for huge numbers.

The least common multiple follows: lcm(a, b) = a / gcd(a, b) * b. Dividing first keeps the numbers small.

The sieve of Eratosthenes

#include <stdio.h>
#define N 30

int main(void) {
    int composite[N + 1] = {0};   // 0 = maybe prime
    for (int p = 2; p * p <= N; p++)
        if (!composite[p])
            for (int m = p * p; m <= N; m += p) composite[m] = 1;
    for (int i = 2; i <= N; i++)
        if (!composite[i]) printf("%d ", i);
    printf("\n");
    return 0;
}

To find every prime up to n, testing each number separately is slow. The sieve starts with every number marked "maybe prime"; for each prime p it crosses out the multiples of p, starting at p * p (smaller multiples were already crossed out by smaller primes). It is O(n log log n), almost linear.

Syntax

while (b != 0) { int r = a % b; a = b; b = r; }   // Euclid

while (b > 0) {                                   // repeated squaring
    if (b % 2 == 1) result = result * a % m;
    a = a * a % m;
    b /= 2;
}

Example

#include <stdio.h>

long long power_mod(long long a, long long b, long long m) {
    long long result = 1;
    a %= m;
    while (b > 0) {
        if (b % 2 == 1) result = result * a % m;   // this bit of b is 1
        a = a * a % m;
        b /= 2;
    }
    return result;
}

int main(void) {
    printf("3^13 mod 1000 = %lld\n", power_mod(3, 13, 1000));
    printf("2^1000000 mod 1000000007 = %lld\n", power_mod(2, 1000000, 1000000007));
    return 0;
}

a^b by multiplying a b times is O(b): hopeless for b = 10¹⁸. Repeated squaring uses the binary digits of b: square a at each step, and multiply it into the result when the current bit of b is 1. That is O(log b) multiplications.

Contests ask for answers modulo a prime such as 1,000,000,007, because the real answers are too big for any integer type. Taking % m after every multiplication keeps every number below m², which fits in a long long.

Line by line

1. power_mod starts result at 1 and first reduces a modulo m.
2. The loop reads the binary digits of b, starting with the lowest.
3. If the current digit is 1, this power of a is multiplied into result.
4. a = a * a % m moves from a to a², then a⁴, and so on.
5. b /= 2 moves to the next binary digit, so the loop runs about log₂ b times.
6. main first prints a small case that can be checked by hand, then one far too large to compute directly.

Expected result

3^13 mod 1000 = 323
2^1000000 mod 1000000007 = 235042059

In the real world

RSA and the Diffie–Hellman key exchange, which help secure connections on the web, depend on modular exponentiation with enormous numbers. The GCD is what simplifies fractions, and it appears inside those same cryptographic methods.

Common mistakes

• Computing a * b / gcd when a * b can overflow: divide first.
• Multiplying two values near m in an int, which overflows: use long long.
• Starting the sieve's loop for each prime at 2 × p, which works but wastes time.

Best practices

• Reduce modulo m after every multiplication.
• Check the largest possible intermediate value before choosing a type.
• Test with b = 0 and with m = 1.

Summary

Euclid's algorithm finds the GCD by repeated remainders, the sieve finds all primes up to n by crossing out multiples, and repeated squaring computes huge powers in O(log b) multiplications.

Mark lesson complete