6. `base62_encode`/`base62_decode`, run

Description

The two previous lessons used base62_encode as a black box: you put a number in, a short code came out. This lesson opens the box. You'll implement base62_encode and its inverse base62_decode from scratch, understand why they work with the same divmod you learned in grade school, and —the heart of the lesson— run them to check three things we won't quote from memory: that base62_encode(1) gives '1' and base62_encode(1000000) gives '4c92', that the round-trip base62_decode(base62_encode(n)) == n is true for hundreds of thousands of values (that is, the conversion doesn't lose information), and that 62⁷ = 3,521,614,606,208 is plenty for Enlace's 6 billion links.

Base62 isn't magic or cryptography; it's base-conversion arithmetic, the same idea by which "255" in base 10 is written "FF" in base 16. Understanding it gives you two things: the ability to implement the project's code generator (lesson 8) with confidence, and the intuition for why 7 characters are the right number for Enlace —not 6 (which would fall short) nor 11 (which would be a waste)—.

Connection to the module: this is the third generation lesson (4 hash, 5 counter/random, 6 base62), and it's the one that gives the foundation of the other two: both the counter and the random need to convert numbers into short codes, and that conversion is base62. It's also where the module's numeric anchor (62⁷ vs 6 billion) is run in depth, closing the number lesson 1 presented. After this lesson, lesson 7 compares the three strategies with everything in hand, and lesson 8 puts them together into a generator that runs.

Changing base is regrouping

You have 1,000,000 chips and you want to write how many they are. In base 10 —the usual one— you group by ten: ten chips make a ten, ten tens a hundred, and so on. The number "1000000" means, literally, "one group of a million, zero of a hundred thousand, zero of ten thousand…": each position is worth ten times the one to its right. Base 10 uses ten symbols (0 to 9) because it groups by ten.

Base 62 does exactly the same, but it groups by 62. It uses 62 symbols —the digits 0-9, then the lowercase a-z, then the uppercase A-Z— and each position is worth 62 times the one to its right. Why 62? Because they're the characters you can put in a URL without complications: numbers and letters, no strange symbols, no accents, no spaces. And grouping by 62 instead of by 10 makes numbers write much shorter, because each character carries more information: a base62 character distinguishes between 62 things, while a base10 digit only between 10. That's why 1,000,000 (seven digits in base 10) fits in four base62 characters.

The conversion from base 10 to base 62 is the same algorithm you'd use to convert to binary or hexadecimal, and it rests on an operation you already know: divide and keep the remainder. To take a number to base B, you divide it by B repeatedly; the remainders that come out, read backwards, are the digits in base B. It sounds abstract; it becomes obvious as soon as you see it with numbers.

base62_encode: divide and keep the remainders

Here's the implementation, and below we take it apart step by step:

# base62.py — the alphabet and the two conversions.
ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
BASE = len(ALPHABET)   # 62


def base62_encode(n: int) -> str:
    """Converts a non-negative integer into its base62 string."""
    if n < 0:
        raise ValueError("n must be >= 0")
    if n == 0:
        return ALPHABET[0]           # 0 is a special case: gives "0"
    chars = []
    while n > 0:
        n, rem = divmod(n, BASE)      # quotient and remainder of dividing by 62
        chars.append(ALPHABET[rem])   # the remainder chooses the symbol
    return "".join(reversed(chars))   # the remainders come out backwards: they're reversed

Let's follow the algorithm with n = 1000000, by hand, to see there's no trick. On each pass of the loop, divmod(n, 62) returns the quotient (which becomes the new n) and the remainder (which chooses a character from the alphabet):

The remainders came out in the order 2, 9, c, 4. But notice a detail: the first remainder that comes out is that of the least significant digit (the one on the right), just as when you divide by hand and the first remainder is that of the units. That's why at the end you have to reverse them: reversed([2, 9, c, 4]) gives 4, c, 9, 2, and together they form '4c92'. That's the code for 1,000,000 in base 62. Four characters for what in base 10 were seven digits.

Two details of the code deserve a look. The n == 0 case is set apart because the while n > 0 loop would never execute for 0 and would return an empty string; by convention, 0 is encoded as the first symbol, '0'. And divmod(n, BASE) is a Python convenience that does the division and the remainder at once, returning (quotient, remainder) —it's exactly (n // 62, n % 62), but clearer and faster—.

base62_decode: the inverse operation

Encoding serves to manufacture the code from a number (the counter, or a random one). Decoding does the way back: from the string to the number. What's it needed for? To verify the conversion doesn't lose information (this lesson's round-trip), and in some designs to recover the internal number from the code. The inverse is just as simple: you go through the string from left to right, and for each character you multiply what you have by 62 and add the character's value.

def base62_decode(s: str) -> int:
    """Converts a base62 string back to its integer."""
    n = 0
    for ch in s:
        n = n * BASE + ALPHABET.index(ch)   # 'shift' one position and add
    return n

It's the same mechanism by which you read a normal number. When you see "492", your head does: start at 0; see 4, compute 0×10+4 = 4; see 9, compute 4×10+9 = 49; see 2, compute 49×10+2 = 492. base62_decode does the same, but multiplying by 62 instead of by 10. For '4c92': start at 0; 4 → 0×62+4 = 4; c → 4×62+12 = 260; 9 → 260×62+9 = 16,129; 2 → 16,129×62+2 = 1,000,000. It returns to the starting number. Encoding and decoding are perfectly reversible because they're the same correspondence read in two directions.

Worked example: I run everything and check the round-trip

Now let's run the two functions for real and verify the lesson's claims. This is the block that proves the implementation is correct, not just that it looks good:

# I run base62 and verify the module's three claims.
print("encode(0)       =", repr(base62_encode(0)))
print("encode(1)       =", repr(base62_encode(1)))
print("encode(61)      =", repr(base62_encode(61)))
print("encode(62)      =", repr(base62_encode(62)))
print("encode(1000000) =", repr(base62_encode(1000000)))
print("encode(62**7-1) =", repr(base62_encode(62**7 - 1)))
print()
print("decode('4c92')  =", base62_decode("4c92"))
print("decode(encode(1000000)) =", base62_decode(base62_encode(1000000)))
print()

# THE ROUND-TRIP: decode(encode(n)) == n for MANY n.
ok = all(base62_decode(base62_encode(n)) == n for n in range(0, 200_001))
print("round-trip decode(encode(n)) == n for n in [0, 200000]:", ok)
print()

# THE ANCHOR: 62^7 vs the 5-year demand.
supply = 62 ** 7
demand = 100_000_000 * 12 * 5
print("62**7 =", f"{supply:,}")
print("demand 5 years =", f"{demand:,}")
print("fraction used =", f"{demand / supply:.4%}")

What to expect. Running everything with Python 3.14.0 gives, exactly:

encode(0)       = '0'
encode(1)       = '1'
encode(61)      = 'Z'
encode(62)      = '10'
encode(1000000) = '4c92'
encode(62**7-1) = 'ZZZZZZZ'

decode('4c92')  = 1000000
decode(encode(1000000)) = 1000000

round-trip decode(encode(n)) == n for n in [0, 200000]: True

62**7 = 3,521,614,606,208
demand 5 years = 6,000,000,000
fraction used = 0.1704%

Let's go part by part, because each line confirms something. encode(1) = '1' and encode(61) = 'Z': the first 62 numbers (from 0 to 61) are encoded with a single character, running through the whole alphabet —0…9, a…z, A…Z—, and 61 is the last uppercase, Z. encode(62) = '10': on reaching 62 it "carries" to a second position, just as in base 10 when going from 9 to 10; '10' in base 62 means "one group of 62, zero loose ones" = 62. encode(1000000) = '4c92': exactly the number we derived by hand in the table above, now confirmed by the machine. And encode(62**7 - 1) = 'ZZZZZZZ': the largest number that fits in 7 characters is seven Zs in a row, the "999...9" of the 7-digit base62.

The line that matters most is the round-trip: True. It means that for all the 200,001 numbers from 0 to 200,000, encoding and then decoding returns the original number —not one is lost or corrupted—. That's the guarantee that base62 is a one-to-one correspondence: each number has exactly one code, and each code exactly one number. It's the property that makes the counter strategy safe: if base62_encode were ambiguous (two numbers with the same code), it would reintroduce collisions through the back door. It isn't, and you just verified it over 200,001 cases, instead of believing it.

And the anchor, at last run in depth: 62⁷ = 3,521,614,606,208, the 5-year demand is 6,000,000,000, and the fraction used is 0.1704%. Three and a half trillion possible codes, of which Enlace will use, in five years, less than two thousandths. That margin is what gives permission to the three strategies: the counter has numbers to spare, the random one almost never clashes (0.17%, lesson 5), and "7 characters" is roomy, not tight.

Why 7, and not 6 or 11

The lesson closes with the question the anchor answers: why 7 characters? The answer is that 7 is the smallest number of base62 characters whose space comfortably exceeds Enlace's demand —neither a waste nor a tight bet—. Let's see it by comparing how many codes each length gives against the 6 billion to cover:

# How many base62 characters are needed for 6 billion links?
demand = 6_000_000_000
for length in range(5, 9):
    space = 62 ** length
    verdict = "ENOUGH" if space >= demand else "falls short"
    print(f"{length} chars: 62^{length} = {space:>18,}  -> {verdict}")

What to expect. It gives:

5 chars: 62^5 =            916,132,832  -> falls short
6 chars: 62^6 =         56,800,235,584  -> ENOUGH
7 chars: 62^7 =      3,521,614,606,208  -> ENOUGH
8 chars: 62^8 =    218,340,105,584,896  -> ENOUGH

Look at the boundary. With 5 characters there are only ~916 million codes: it falls short for 6 billion, impossible. With 6 characters there are ~56,800 million: technically enough for 6 billion... but by a factor of only ~9.5×, that is, you'd use more than 10% of the space, and with the birthday problem (lesson 4) the random one would start to clash noticeably, and there'd be no room to grow. With 7 characters there are 3.52 trillion: a factor of ~587× over the demand, enormous margin for the random one to barely clash and for Enlace to grow without redesigning. With 8 characters there are 218 trillion: enough even more, but each link is one character longer without need —a shortener that lengthens its codes for free wastes exactly what it sells—.

There's the design choice, with numbers: 7 is the sweet spot. 6 would barely be enough and with no margin; 8 would give excess margin at the cost of brevity. 7 characters buy ~587 times the 5-year demand for the price of one character more than the tight minimum —an excellent trade—. When in an interview you're asked "why 7 characters?", this is the answer: it's not a magic number, it's the shortest one that gives comfortable margin over 100M/month × 12 × 5.

Common mistakes

Forgetting the n == 0 case. What happens: someone writes base62_encode with only the while n > 0 loop, without the special case, and when encoding 0 gets an empty string '' instead of '0'. If 0 is a possible counter value, that produces an empty code, which breaks everything that depends on a non-empty code. Why it happens: the loop never enters when n is already 0. How to detect it: test base62_encode(0) explicitly; if it returns '', you have the bug. How to fix it: handle 0 separately by returning ALPHABET[0], as in the lesson's implementation. It's the classic edge case that a one-line test catches and that in production appears as link number zero.

Changing the alphabet's order between encoding and decoding. What happens: someone defines the alphabet in one order when encoding (say uppercase first) and in another when decoding, or changes the order after having generated codes. The result: base62_decode(base62_encode(n)) stops giving n, and worse, the codes already stored in the database now decode to wrong numbers. Why it happens: the alphabet is the key of the correspondence; if the two directions don't use exactly the same one, they aren't inverses. How to detect it: the round-trip fails, or the old links stop resolving. How to fix it: define ALPHABET once, as a shared constant, and never reorder it once there are codes in production. The order is part of the data contract.

Forgetting to reverse the remainders. What happens: someone builds the string in the order the remainders come out (2, 9, c, 4) without reversing it, and encodes 1,000,000 as '29c4' instead of '4c92'. The function is consistent with itself only if decode also reads backwards, but if decode reads normally, the round-trip breaks; and the resulting code is "the number backwards", which is confusing and incompatible with any other standard base62 implementation. Why it happens: the remainders come out from the least significant digit to the most significant, the reverse of how a number is written. How to detect it: base62_encode(62) should give '10'; if it gives '01', you forgot to reverse. How to fix it: "".join(reversed(chars)), as in the implementation. The remainder of the first division is the last character of the code.

Exercises

Exercise 1 — Encode and decode by hand, then verify. Without running code, apply the base62_encode algorithm to n = 500 (divide by 62 repeatedly, note the remainders, reverse them). Write the code you obtain. Then decode it by hand with the base62_decode method to check you return to 500. Finally, verify with Python.

print(base62_encode(500))                 # '84'
print(base62_decode('84'))                # 500
print(base62_decode(base62_encode(500)))  # 500

Exercise 2 — How many characters for a shortener 10× bigger? A rival shortener creates 1 billion URLs per month (10× Enlace). With 5-year retention, compute its total demand and determine how many base62 characters it needs at minimum, comparing 62^length against the demand. Does 7 still suffice, or does it need 8?

demand = 1_000_000_000 * 12 * 5     # 60,000,000,000 (60 billion)
for length in range(6, 9):
    space = 62 ** length
    print(length, f"{space:,}", "ENOUGH" if space >= demand else "short")
# 6  56,800,235,584          short
# 7  3,521,614,606,208       ENOUGH
# 8  218,340,105,584,896     ENOUGH

Exercise 3 — The round-trip as a correctness test. Explain why the round-trip base62_decode(base62_encode(n)) == n for many n is a good proof that the implementation is correct, but not a complete proof. Give an example of a bug that the round-trip would catch and one that it wouldn't catch.

Summary and next step

You opened the black box. base62_encode is base conversion by divmod: you divide the number by 62 repeatedly, the remainders choose symbols from the 0-9a-zA-Z alphabet, and you reverse them. base62_decode is the inverse: you multiply by 62 and add, character by character. You ran it and verified the module's three claims: base62_encode(1) = '1', base62_encode(1000000) = '4c92', base62_encode(62⁷-1) = 'ZZZZZZZ'; the round-trip base62_decode(base62_encode(n)) == n is True for the 200,001 values from 0 to 200,000 (the conversion doesn't lose information, guarantee that the counter doesn't reintroduce collisions); and the anchor, run in depth: 62⁷ = 3,521,614,606,208, 5-year demand 6,000,000,000, fraction used 0.1704%. And you answered why 7 characters: it's the minimum that gives comfortable margin (587× the demand) —6 would barely be enough, 8 would waste brevity—.

Before moving on you should be able to: implement base62_encode/base62_decode from memory, with the n == 0 case and the remainder reversal; explain why the round-trip proves reversibility and why you also have to assert exact values; and justify with numbers why 7 characters (and not 6 or 8).

With the three strategies implemented and the base62 conversion mastered, you have everything to decide. Lesson 7 puts the three —hash, counter+base62, random+verification— in a table against Enlace's criteria (no collisions, not guessable, write-scalable, short code), shows how they combine in practice, and leads you to a reasoned decision you can defend —with the boundary toward module 5 (scaling the generator is sharding) marked.

Resources

• Python documentation — the divmod function — the engine of base62_encode: it returns quotient and remainder at once. Seeing its formal definition confirms that divmod(n, 62) is exactly (n // 62, n % 62).
• Python documentation — str methods (join, index) and reversed — the pieces with which the code's string is assembled and each character's value is looked up. ALPHABET.index(ch) is the inverse operation of ALPHABET[rem].
• Wikipedia — "Positional notation" and base conversion — the theory of why "each position is worth the base times the one to its right", common to base 10, base 16, and base 62. Understanding it makes base62 stop seeming a trick and look like the usual arithmetic.
• The System Design Primer — the shortener's code-generation section — a second voice on why base62 and why ~7 characters, with the same space-vs-demand reasoning you ran here.