Carrying the One in Base 232: Why Mercury Addition Works
Mercury does not abandon grade-school arithmetic. It changes the size of the digit.
That one idea explains a surprising amount of the Mercury arbitrary-precision engine. When we work in decimal, each digit holds a value from 0 to 9. When a column grows too large, we keep the part that belongs in the current column and carry the rest into the next one.
Mercury does exactly the same thing. The only difference is that Mercury’s “digits” are not decimal digits. They are 32-bit unsigned integer limbs.
In other words, Mercury works in base 232.
Every Base Has Columns
In base 10, the largest single digit is 9. If we add:
9 + 9 + 1 = 19the current column keeps the 9, and the next column receives a carry of 1.
In base 16, the largest single digit is F, which is decimal 15. If we add:
F + F + 1 = 1Fthe current column keeps F, and the next column receives a carry of 1.
Mercury uses the same rule, just with much larger digits:
0xFFFFFFFF + 0xFFFFFFFF + 1 = 0x1FFFFFFFFThe current 32-bit limb keeps:
0xFFFFFFFFand the next limb receives:
1That is all a carry is.
Why the Carry Can Only Be 0 or 1
This is not a special trick of binary computers. It is a property of positional number systems.
In any base B, a single digit can only range from:
0 to B - 1When adding two digits plus an incoming carry, the largest possible value is:
(B - 1) + (B - 1) + 1 = 2B - 1That means the result may cross into the next column, but it can only cross once. The outgoing carry can only be 0 or 1.
For Mercury, the base is:
B = 2^32So the largest possible single-limb addition is:
(2^32 - 1) + (2^32 - 1) + 1 = 2^33 - 1That result needs only 33 bits. A 64-bit register has more than enough room to hold it safely.
The Mercury Addition Loop
This is why Mercury can use a 64-bit register to add two 32-bit limbs:
ulong reg = 0;
for (; i <= bh && i <= h; i++) {
reg += ((slong) a[2+i-al] + (slong) b[2+i-bl]);
scratch[i - l] = (uint) reg;
reg >>= 32;
}The low 32 bits become the output limb:
scratch[i - l] = (uint) reg;Then Mercury shifts the register right by 32 bits:
reg >>= 32;That removes the limb we already stored and leaves only the carry for the next position.
If there was no overflow, the carry is 0. If the limb overflowed, the carry is 1.
That is the whole secret: Mercury uses the processor’s native 64-bit arithmetic as a temporary workspace for base-232 digit arithmetic.
Borrowing Is the Same Story in Reverse
Subtraction follows the same positional logic, but instead of carrying forward a positive overflow, it carries forward a borrow.
Consider the smallest possible underflow in one limb:
0x00000000 - 0x00000001The current limb does not have enough value to complete the subtraction. So it borrows one unit from the next limb. But one unit in the next limb is worth exactly 232 in the current limb.
So the calculation becomes:
0x100000000 - 0x00000001 = 0xFFFFFFFFThe current limb receives:
0xFFFFFFFFand the next limb receives a borrow of:
-1The Mercury Subtraction Loop
That is why Mercury’s subtraction loop uses a signed 64-bit register:
slong reg = 0;
for (; i <= bh && i <= h; i++) {
reg += ((slong) a[2+i-al] - (slong) b[2+i-bl]);
if (reg < 0) {
reg += 0x100000000LL;
scratch[i - l] = (uint) reg;
reg = -1;
} else {
scratch[i - l] = (uint) reg;
reg = 0;
}
}The signed register makes the borrow visible immediately. If reg drops below zero, Mercury knows the current limb had to borrow from the next place.
To repair the current limb, Mercury adds back:
0x100000000which is exactly 232. Then it stores the repaired 32-bit limb and carries -1 forward into the next position.
This is not a shortcut around subtraction. It is subtraction in positional notation, written directly in the machine’s natural word size.
The Limb Train
A helpful way to picture this is as a train of limbs. Each car holds one base-232 digit:
[00000001] [FFFFFFFF] [FFFFFFFF]
+ [00000001]
-------------------------------------
[00000002] [00000000] [00000000]The rightmost limb overflows first. It rolls from FFFFFFFF to 00000000 and sends a carry to the next limb. That limb also rolls over and sends a carry onward. Finally, the left limb receives the carry and increases from 00000001 to 00000002.
This is the same thing that happens in decimal when:
1999 + 1 = 2000Mercury simply does it in a base where each digit contains 32 bits of information.
Bounded Overflow
This gives Mercury a very useful design property: bounded overflow.
For addition, the bounds are simple:
32-bit limb + 32-bit limb + carry = at most 33 bitsFor multiplication, the next tier, the bounds are larger:
32-bit limb * 32-bit limb = at most 64 bitsThat is why base 232 is such a natural foundation for this engine. Addition has room to carry. Multiplication has room to stage a limb product. The machine’s native 64-bit arithmetic becomes the safe workbench for 32-bit arbitrary-precision digits.
Why This Matters
The Additive Tier may look simple, but it establishes the discipline that the rest of Mercury builds on.
A large number is not magic. It is a sequence of bounded digits.
A carry is not magic. It is the part of a column that no longer fits.
A borrow is not magic. It is one unit from the next column, reinterpreted in the current column’s base.
Once those ideas are clear, the rest of arbitrary-precision arithmetic becomes much less mysterious. Multiplication is not a different universe. It is the next tier: many limb products, many carries, and the same positional logic scaled upward.
Mercury does not abandon grade-school arithmetic. It changes the size of the digit.
Up Next
The Additive Tier gives us a stable, linear foundation. Next time, we will step up to the Multiplicative Tier, where we move into geometric scaling and explore how decimal long division perfectly explains Mercury’s nibble-sized pre-multiplication table.
Also, how does multiplying two 32bit values produce precisely 64bits?