Capstok — learn by doing

Why this matters

Every integer is the same mathematical object regardless of how we write it, but how we represent it determines the cost of every operation we perform. Computers use base 2 internally; we read base 10; cryptographers serialise large integers in base 16 or base 64; binary representations make multiplication by powers of 2 free; modular reduction by $2^k - 1$ is just digit summing in base $2^k$ . The point of this task is to internalise the division-algorithm view of base- $b$ representation: every integer $n \geq 0$ has a unique expansion $n = \sum d_i b^i$ with $0 \leq d_i < b$ , and that uniqueness is just the division algorithm applied recursively. Once you see that, you'll see why every fast modular-arithmetic algorithm — square-and-multiply for exponentiation, Montgomery reduction, Barrett reduction — is fundamentally about choosing the right base.

Demo

For any integer $n \geq 0$ and any base $b \geq 2$ , there is a unique sequence of digits $(d_k, d_{k-1}, \ldots, d_1, d_0)$ with , (unless ), and . The digits are computed by repeatedly dividing by and recording remainders — exactly the division algorithm, applied recursively.

n = \sum_{i=0}^{k} d_i \, b^i, \quad 0 \leq d_i < b, \quad d_k \neq 0 \text{ if } n > 0

Try it yourself

Convert 1729 to base 2, base 8, and base 16 by hand using repeated division. Verify each against to_base(1729, b) and against Python's bin/oct/hex.
Show numerically that for any $n$ , from_base(to_base(n, b), b) == n for several bases $b \in \{2, 3, 7, 16, 64\}$ . This is the round-trip that ratifies uniqueness.
Compute $123_{10}$ in base 4 by hand: , so digits are . Verify with .

References

to_base(123, 4)

// main.go
package main

import "fmt"

// toBase returns the digits of n in base b, most significant first.
func toBase(n, b int) []int {
	if n == 0 {
		return []int{0}
	}
	var digits []int
	for n > 0 {
		digits = append(digits, n%b)
		n /= b
	}
	// reverse
	for i, j := 0, len(digits)-1; i < j; i, j = i+1, j-1 {
		digits[i], digits[j] = digits[j], digits[i]
	}
	return digits
}

// fromBase reconstructs the integer from digits in base b.
func fromBase(digits []int, b int) int {
	n := 0
	for _, d := range digits {
		n = n*b + d
	}
	return n
}

func main() {
	fmt.Println(toBase(255, 2))            // [1 1 1 1 1 1 1 1]
	fmt.Println(toBase(255, 16))           // [15 15]  -> ff
	fmt.Println(toBase(2024, 7))           // [5 6 6 1 1] -> 5*7^4 + 6*7^3 + 6*7^2 + 1*7 + 1
	fmt.Println(fromBase([]int{5, 6, 6, 1, 1}, 7)) // 2024

	// Go fmt verbs for common bases
	fmt.Printf("%b %x %o\n", 255, 255, 255) // 11111111 ff 377
	fmt.Println(255)                         // decimal
}

Run: go run main.go

One Number, Many Ways to Write It (Bases)

Why this matters

Demo

Try it yourself

References