Recursive number theory

Overview

Two recurrences that shrink their input dramatically rather than by one. Euclid's algorithm replaces gcd(a,b) with gcd(b, a mod b), and because the modulus collapses the numbers quickly it finishes in O(log min(a,b)) steps. Fast exponentiation halves the exponent at every step, turning base^exp from exp multiplications into about log2(exp) of them. Both are naturally recursive because each step restates the same problem on smaller arguments, and both are worth knowing as the standard examples of logarithmic recursion.

Why it matters

Fast exponentiation is the workhorse of public-key cryptography — RSA and Diffie-Hellman compute huge modular powers, and doing that naively would take longer than the age of the universe. Euclid's algorithm underlies fraction reduction, modular inverses, and much of number theory. The shared lesson is that a recursive step which divides rather than decrements is what turns linear into logarithmic.

Core concepts

Euclid's identity. gcd(a, b) = gcd(b, a mod b), with gcd(a, 0) = a as the base case. Each step replaces the pair with a strictly smaller one, and the modulus shrinks fast — consecutive Fibonacci numbers are the worst case and still only give logarithmic depth.

Why the base case is b == 0. When the remainder reaches zero, the other argument is the divisor of both — the answer.

Argument order sorts itself. gcd(12, 18) immediately becomes gcd(18, 12) after one step, so you do not need to order the arguments beforehand.

Fast power by halving. base^exp = (base^(exp/2))^2, multiplied by one extra base when exp is odd. Compute the half once into a variable and square it; writing fast_pow(b, e/2) * fast_pow(b, e/2) calls it twice and destroys the benefit, degrading to linear.

Base case exp == 0 returns 1. Anything to the zero power is 1, and that seeds the whole unwinding.

Overflow. Powers grow explosively — the modular variant ((a * b) % m at every step) is what makes this usable in practice, and even then intermediate products need a wide enough type.

Syntax notes

/* Euclid: gcd(a,0) = a */
int gcd(int a, int b) {
    return (b == 0) ? a : gcd(b, a % b);
}

/* halve the exponent - compute the half ONCE */
long long fast_pow(int base, int exp) {
    if (exp == 0) return 1;
    long long h = fast_pow(base, exp / 2);      /* one call, not two */
    return (exp % 2) ? h * h * base : h * h;
}

/* modular variant - what cryptography actually uses */
long long pow_mod(long long b, long long e, long long m) {
    if (e == 0) return 1 % m;
    long long h = pow_mod(b, e / 2, m);
    long long r = (h * h) % m;
    return (e & 1) ? (r * b) % m : r;
}

Key points:

• Storing the recursive result in h is what makes this O(log exp); calling twice makes it O(exp).
• a % b in C truncates toward zero, so negative inputs need abs if you want the usual non-negative gcd.
• pow_mod keeps every intermediate below m^2 — choose a type wide enough for that product.

Lesson

Two recurrences shrink fast: Euclid's GCD (gcd(a,b)=gcd(b, a mod b)) collapses in O(log) steps, and fast exponentiation halves the exponent each call (base^exp via squaring) for O(log exp) multiplications.

Code examples

#include <stdio.h>
static int gcd(int a,int b){ return b==0 ? a : gcd(b, a%b); }
static long long fast_pow(int base,int exp){ if(exp==0) return 1; long long h=fast_pow(base,exp/2); return exp%2 ? h*h*base : h*h; }
int main(void){
    printf("gcd(48, 36) = %d\n", gcd(48,36));
    printf("2^20 (by squaring) = %lld\n", fast_pow(2,20));
    return 0;
}

Line by line

Common mistakes

Recomputing the recursive half twice in fast_pow; wrong base case.

Debugging tips

Compiler errors and warnings:

• warning: integer overflow in expression when powers exceed the type — widen or take a modulus.
• No warning for the double-recursive-call mistake; it is a performance bug, not a compile error.

Runtime symptoms:

• fast_pow is as slow as the naive loop. You wrote fast_pow(b, e/2) * fast_pow(b, e/2). Compute it once into a variable.
• gcd never terminates. The arguments are swapped so the modulus is never taken, or b is negative and % yields a negative remainder that never reaches 0. Take absolute values at the boundary.
• gcd(0, 0) returns 0. Mathematically it is undefined; decide and document your convention.
• Wrong results for large exponents. Overflow — use the modular version or a wider type.
• pow_mod returns a negative number. An intermediate product overflowed before the %; use a wide type or __int128 where available.

Technique: print the argument pair at each level of gcd. You should see the numbers collapse within a handful of steps — if they crawl down by 1, the recursion is wrong.

Memory safety

• Depth is logarithmic, so stack use is negligible — a genuine advantage of these two over linear recursion. fast_pow(2, 1000000) is only about 20 frames deep.
• Signed overflow is undefined behaviour, and powers overflow almost immediately. Use long long, or better, the modular form for anything cryptographic.
• Intermediate products in pow_mod. h * h can reach nearly m^2; if m approaches 2^32 then a 64-bit product is not enough. Use __int128 or a mulmod routine.
• Negative and zero inputs. a % b with a negative a gives a negative remainder in C, which breaks Euclid's termination assumption. Normalise with absolute values, and decide what gcd(0,0) means.
• Not constant-time. These implementations branch on the exponent's bits, which leaks timing information. Real cryptographic code uses constant-time ladders — do not use this version to guard secrets.

Real-world uses

Concrete uses: RSA and Diffie-Hellman are modular exponentiation at their core. Euclid's algorithm reduces fractions, computes modular inverses (via the extended version), and appears in scheduling problems involving cycle lengths. Both are standard components of any big-integer or number-theory library.

Professional best practices:

Beginner:

• Store the halved result in a variable — this is the whole optimisation.
• Normalise negative inputs to gcd before recursing.

Intermediate:

• Use the modular form by default for large exponents; plain fast_pow overflows almost immediately.
• Be aware that these branch on secret data; use vetted constant-time implementations for cryptography rather than rolling your own.
• The iterative (bit-scanning) version of fast power is equally simple and avoids recursion entirely.

Practice tasks

1. (Beginner) Euclid's gcd. Implement int gcd(int a, int b) and normalise negative inputs. Example: gcd(48,18) -> 6; gcd(-48,18) -> 6. Concepts: modulus base case.

2. (Beginner) Fast power. Implement long long fast_pow(int base, int exp) computing the half once. Example: fast_pow(2,10) -> 1024. Concepts: halving recursion.

3. (Intermediate) Count the multiplications. Instrument both the naive and fast versions with a counter and compare for exp = 1000. Concepts: linear vs logarithmic.

4. (Intermediate) Modular exponentiation. Implement pow_mod(b, e, m) reducing at every step. Example: pow_mod(2, 100, 1000000007). Concepts: overflow control, the cryptographic form.

Summary

Both recurrences shrink their input by division rather than decrement, which is what makes them logarithmic. Euclid replaces gcd(a,b) with gcd(b, a mod b) and stops when the remainder is zero; fast exponentiation halves the exponent, squaring the result and multiplying in one extra factor when the exponent is odd. The critical implementation detail is computing the halved call once into a variable — calling it twice silently degrades the algorithm to linear. Normalise negative inputs for gcd, and use the modular form for powers, since these values overflow almost immediately.

Practice with these exercises

• Recursive GCD (Euclid)
• Fast exponentiation