Model a big number as a slice of 9-decimal-digit limbs so every operation is a carry, borrow, or shift you can assert against exactly - no bignum built-in, only fixed-width machine integers. Each lesson is one concrete spec with real values: a carry that grows the limb count, a subtraction that shrinks it or flips the sign, multiply by zero collapsing to canonical zero, Karatsuba agreeing with schoolbook on a multi-limb pair, a long-division remainder strictly smaller than the divisor, and a parse-and-render round-trip of a 20-digit number.
Over 32 lessons you build a working arbitrary-precision integer library from scratch - a BigInt type with arithmetic, parsing, and formatting - representing every number as a little-endian slice of fixed-base limbs plus a sign. You implement every operation yourself on that limb array; you never delegate to the host language's built-in big-integer type, and you use only fixed-width machine integers as limbs. That keeps the whole library exactly testable: every result is a precise decimal string you can assert against.
You choose base 1000000000 so that a group of exactly nine decimal digits is one limb, which makes parsing and rendering decimal trivial and exact from the very first chapter. From there you build magnitude comparison, schoolbook addition with carry and subtraction with borrow, signed add and subtract that dispatch on sign and magnitude, schoolbook long multiplication and then Karatsuba divide-and-conquer for large operands, single-limb short division and full schoolbook long division producing an exact quotient and remainder, and a final chapter of higher operations: bit shifts, square-and-multiply exponentiation, modular exponentiation, Euclid's GCD, and hexadecimal conversion. The capstone computes genuinely large exact results - 100 factorial and 2 to the 1000th power as full decimal strings, plus a modular-exponentiation result checked against a known value.
This is a teaching-grade bignum library built around the classical algorithms from Knuth's Seminumerical Algorithms: it is correct and exact but not tuned for speed the way GMP is - it uses base 1000000000 rather than a full machine-word base, Karatsuba but not the asymptotically faster Toom-Cook or FFT multiplication, and schoolbook long division rather than the fastest known divide-and-conquer division. It is the honest core that a production library like GMP extends with word-sized limbs, more multiplication algorithms, and heavy platform-specific tuning.
Every big number we build lives in one place - a little-endian array of limbs, each limb a digit in base 1000000000. Today you build that magnitude from an ordinary machine integer and read its limbs back out.
Represent a non-negative magnitude as base-1000000000 limbs and report how many limbs it holds.
A big integer is just a number written in a very large base. We pick base
1000000000 - ten to the ninth - because a group of exactly nine decimal
digits is then a single limb, which will make reading and writing decimal
trivial in a couple of lessons. A magnitude is a slice of these limbs stored
little-endian: limb 0 is the least significant, so 1000000005 becomes limb 0
= 5 and limb 1 = 1 (that is 1 * 1000000000 + 5).
Storing limbs in uint32 is deliberate: each limb is below 1000000000 < 2^32, so
it fits, and when we multiply two limbs later the product stays below 10^18,
which fits in a 64-bit intermediate. Everything the library does is built on this
one representation, so start by getting a magnitude into and out of it.
const Base = 1000000000 // 10^9: each limb holds nine decimal digitstype mag []uint32 // little-endian: index 0 is least significantfunc magFromUint(n uint64) mag {var m magfor n > 0 { m = append(m, uint32(n%Base)); n /= Base }return m}// NumLimbs is len(m); Limb(i) is m[i]
A genuinely working arbitrary-precision integer library - exact signed arithmetic (add, subtract, schoolbook and Karatsuba multiply, long division with quotient and remainder), decimal and hexadecimal parse and render, fast and modular exponentiation, GCD, and bit shifts, all on a base-1000000000 limb array with no language bignum built-in - but it stays deliberately simple under the hood: base 1000000000 rather than word-sized limbs, one-level Karatsuba (no Toom-Cook or FFT), schoolbook long division with binary-searched quotient digits rather than Knuth Algorithm D with normalization, int-sized exponents and shift counts, and no modular inverse or rational numbers.
Section 4.3 (Multiple-Precision Arithmetic) is the rigorous source for everything here - the classical add, subtract, and multiply, and Algorithm D, the schoolbook long-division method this project follows (here finding each quotient digit by binary search in place of Algorithm D normalization and estimate-and-correct).
The original 1962 divide-and-conquer idea: split each operand in half and multiply with three products instead of four, dropping the cost below n squared. The linked article walks the split, the three recursive products, and the recombination this project implements.
How a production big-integer library actually does it: limb representation, the thresholds between schoolbook, Karatsuba, Toom-Cook, and FFT multiplication, and divide-and-conquer division. Read it to see what the teaching-grade version here deliberately leaves on the table.
A free, modern, self-contained reference for arbitrary-precision arithmetic - representation, addition, the multiplication hierarchy, division, and exponentiation - filling the gap between Knuth and a real library. Chapter 1 maps almost one-to-one onto this project.
A compact from-scratch big-integer writeup that uses exactly the base 1000000000 little-endian-limb representation this project adopts, with the same decimal grouping for I/O - the practical companion to the classical texts.