[Feature Request] Overflow and Saturating Arithmetic

Mojo Language Design
1

Multi-precision integer arithmetic (BigInt, cryptographic field arithmetic) cannot be implemented efficiently without carry/borrow propagation and double-word multiplication primitives. Without them, compilers are forced to synthesize 64-bit multi-precision arithmetic using 32-bit limbs to capture overflows manually, throwing away roughly half the hardware throughput.

Here is the completed API proposal incorporating multiplication and carrying/borrowing primitives:

# --- Checked / Raising Variants ---
def __add__(lhs: Int, rhs: Int) raises OverflowError -> Int
def __sub__(lhs: Int, rhs: Int) raises OverflowError -> Int
def __mul__(lhs: Int, rhs: Int) raises OverflowError -> Int

# --- Saturating Variants ---
def sat_add(lhs: Int, rhs: Int) -> Int
def sat_sub(lhs: Int, rhs: Int) -> Int
def sat_mul(lhs: Int, rhs: Int) -> Int

# --- Carrying / Borrowing Primitives (ADC / SBB) ---
def carrying_add(lhs: Int, rhs: Int, carry: Bool) -> (Int, Bool)
def borrowing_sub(lhs: Int, rhs: Int, borrow: Bool) -> (Int, Bool)

# --- Multiplication & Wide Accumulation ---
def overflowing_mul(lhs: Int, rhs: Int) -> (Int, Bool)
def mul_hi(lhs: Int, rhs: Int) -> Int
def widening_mul(lhs: Int, rhs: Int) -> (Int, Int)            # (low, high)
def carrying_mul_add(
    lhs: Int,
    rhs: Int,
    carry: Int,
    high_carry: Int = 0
) -> (Int, Int)                                               # (low, high)

Core Mechanics & Hardware Lowering

1. Carrying Addition & Subtraction (carrying_add, borrowing_sub)

  • Hardware lowering: Direct mapping to ADC / SBB (x86-64) or ADCS / SBCS (AArch64).
  • Chaining: Essential for ripple-carry loops in multi-word additions:
var carry: Bool = False
for i in range(limb_count):
    (result[i], carry) = carrying_add(a[i], b[i], carry)
  • Typed Throws Variant: If OverflowError carries payload (e.g., struct OverflowError: var partial: Int), raising variants avoid tuple unpacking overhead in checked execution paths. However, carrying loops generally run faster using explicit (Int, Bool) returns to prevent unwinding frame overhead across hot loops.

2. Full-Width & High Multiplication (widening_mul, mul_hi)

  • Standard single-word Int * Int discards the top word. Multi-precision multiplication requires full N \times N \to 2N bit products.

  • widening_mul(lhs, rhs) computes (lhs \times rhs) returning (low, high).

  • Lowers to MULX (x86 BMI2) or UMULH + standard MUL (AArch64).

  • mul_hi(lhs, rhs) extracts only the upper word without computing or returning the low bits if they are unneeded.

3. The BigInt Multiplier Primitive (carrying_mul_add)

  • The fundamental inner loop of Comba/Schoolbook multi-limb multiplication computes:
\text{product} = (\text{lhs} \times \text{rhs}) + \text{carry}_1 + \text{carry}_2
  • Because (2^{64} - 1) \times (2^{64} - 1) + (2^{64} - 1) + (2^{64} - 1) = 2^{128} - 1, the result of multiplying two words and adding two full-width carry words is guaranteed to fit within two 64-bit words with zero overflow.
  • Providing carrying_mul_add enables a 1:1 mapping to AMD64 MULX / ADCX / ADOX dual-carry instructions without register spilling.

Scalar vs. SIMD Codegen Notes

Feature Scalar Int (Word Size) SIMD Vector (SIMD[type, size])
Flags Register Natural access to carry/overflow flags (CF, OF). Vectors have no flags register. Emulating carry requires explicit masks and shift logic.
Carrying Ops Fast sequential chaining (ADC loop). Inefficient for ripple-carry. Multi-word vector BigInt typically uses redundant representations (e.g., 52-bit limbs in 64-bit lanes via AVX-512 IFMA).
Overflow Reporting Raising/typed throws work cleanly. Mask-based reporting (returning vector comparison masks) is preferred over branching/raising.
2

This of course does not work for Int, thus it would either have to be on a checked arithmethic struct or the operator form would have to be converted into a named form

3

The ABI is the same, though LLVM could have some trouble optimizing the branched code and it’s better to resolve this earlier in the optimiziation pipeline.

4

Thanks for taking the time to write this up!

Given the current state of Mojo’s error handling, I think the dunder methods may need to stay as wrapping, in order to avoid Mojo being nearly unusable.

Mostly as personal style thing, I’d prefer sat → saturating, since LSP actions (once the LSP is fixed) make being a bit more verbose when writing to make reading easier cheap.

Otherwise I think this looks reasonable.