For completeness, the alternative (and conceptually simpler to me) approach is to “just” compute the full-width multiplication result and check that for overflow before returning the truncated result. That sounds expensive as well, but if you only want the overflow check, it turns out you can skip a lot of the work.
I’m not sure if it’s faster than the “divide result by one factor” approach. It’s probably more Z-machine instructions, but division is generally much more expensive than multiplication, including on retro hardware, so it may still come out ahead.
Once I started writing this post I got nerd-sniped into actually finishing the derivation, so it’s gotten rather long.
The Z-machine doesn’t have 16x16 → 32 bit multiplication, but we can build it from what does exist. This is simplified by Dialog only using the non-negative 14-bit integers, so we can conveniently ignore the complications of negative numbers and even side-step the mismatch with the Z-machine’s signed arithmetic. The standard way to build a full-width multiply of word-sized inputs L, R is to split them into halves and do long multiplication in base (word size / 2).
For Dialog that means we can compute ($LHS times $RHS into $Result) as base-128 long multiplication. For non-negative n < 16383, let n₀ be the least significant seven bits and n₁ the most significant bits, thus n = n₁ * 128 + n₀. (This requires bit shifts, but luckily Dialog targets Z-machine v5 or v8 which have some shift opcodes.) Then we could compute L * R as follows:
L * R
= (L₁ * 128 + L₀) * (R₁ * 128 + L₀)
= (L₁ * R₁ * 128²) + (L₁ * R₀ * 128) + (L₀ * R₁ * 128) + (L₀ * R₀)
Ignoring the factors of 128 (bit shifts), each of the products of parts of L and R can be computed with Z machine mul instructions, so this reduces the multi-precision arithmetic to add-with-carry (also not natively supported, but easy to emulate with normal add and overflow checks). If we needed the full-width multiplication result, that’s basically as good as it gets. But we can simplify it since we’re only interested in whether the product overflows (if it doesn’t, the Z-machine mul instruction gives the right result):
- If first term
L₁ * R₁ * 128² is non-zero, the product definitely overflows because 128² > 16383. So we don’t need to compute this term, only check if L₁ and R₁ are non-zero.
- If both L₁ and R₁ are non-zero, we have overflow.
- Conversely, if L₁ = R₁ = 0, then there is no chance of overflow, as the result is at most 127² < 16383. (Special-casing this isn’t strictly required, but makes the rest of the derivation a little simpler.)
- That leaves the case where either L₁ or R₁, but not both, is zero. I’ll only discuss the L₁ = 0 case, the case R₁ = 0 is symmetric.
- The first and second terms (involving L₁) are zero, thus L * R = (L₀ * R₁ * 128) + (L₀ * R₀).
- Since the high bits of L are zero, we don’t need to explicitly isolate the low bits of L, i.e., we have L = L₀ and can write L * R = (L * R₁ * 128) + (L * R₀).
- Overflow will mostly be due to the first term (L * R₁ * 128) being too large, as the contribution of (L * R₀) is much smaller. We’ll ignore (L * R₀) for now and get back to it later.
- In general (L * R₁ * 128) won’t fit in 16 bits, but we don’t need to compute it to detect overflow. L * R will overflow if L * R₁ > 16383 / 128. Since that right-hand side isn’t an integer, it’s more obvious to write this as L * R₁ >= (16383 + 1) / 128 = 128.
- To correct for the contribution of (L * R₀) and make the check precise, we actually check if (L * R₁) + ((L * R₀) / 128) >= 128. Since the fractional part of (L * R₀) / 128 never changes the comparison result, we only need floor((L * R₁) / 128), which is just a multiply and bit shift ((L * R₁) >> 7).
So in summary, we only need two additional mul instructions (over the one used to compute the actual result), and a few shifts/adds/compares. Here’s a Rust program implementing this and checking that it actually works correctly:
fn dialog_mult_overflow(lhs: i16, rhs: i16) -> bool {
let l1 = lhs >> 7;
if l1 == 0 {
// optional: short-circuit if rhs small enough (r1 == 0)
let l0 = lhs;
let r0 = rhs & 0x7f;
l0 * r1 + ((l0 * r0) >> 7) >= 128
} else {
let r1 = rhs >> 7;
if r1 != 0 {
// both >= 128, so product must overflow
return true;
}
let l0 = lhs & 0x7f;
let r0 = rhs;
(l1 * r0) + ((l0 * r0) >> 7) >= 128
}
}
fn main() {
for lhs in 0..=16383 {
for rhs in 0..=16383 {
let real_result = i64::from(lhs) * i64::from(rhs);
let ovf_real = real_result > 16383;
let ovf_diag = dialog_mult_overflow(lhs, rhs);
assert_eq!(ovf_real, ovf_diag, "{lhs} * {rhs} = {real_result}");
}
}
}