(42, all flavours) Integer Division - how?

[Albert Chan]

(12-11-2020 10:48 AM)Werner Wrote:  (2e23+3e12) DIV 4e11 = 5e11+7 (5e11+8) (round-to-even, and a particularly difficult one to get right)

Round-to-even behavior actually make halfway case easy to get floor-divide.

a, b = 2e23 + 3e12, 4e11
a ≡ 0 + 2e11 ≡ b/2, (mod b), indeed a halfway case.
Problem is reduced to finding s = sign of remainder(a,b)

Let q = rounded-to-nearest of a/b, which we know is correct
Let h = halfway = b/2

a = q*b + s*(b/2) = (2*q+s)*h

While 3|h, reduce both a, h by 3. This made mod 3 test (below), work all the time.
Without this step, we get into modulo fractions equivalent of divide-by-zero. (*)

a ≡ (2*q + s)*h ≡ (s - q)*h (mod 3)
s ≡ a/h + q (mod 3)

Mod 3 is same as Mod 9, then Mod 3. Just add the digits, ignoring powers-of-tens.
For above example, h = 2e11 ≡ 2 ≡ -1 (mod 3), not divisible by 3. So, we proceed:

a = 2e23 + 3e12 ≡ 2+3 ≡ -1 (mod 3)
q = 5e11+8 ≡ 5 + 8 ≡ 13 ≡ 1 (mod 3)

→ s ≡ -1/-1 + 1 ≡ 2 ≡ -1 (mod 3)
→ floor-divide(a/b) = q - (s<0) = q - 1 = 5e11 + 7


(*) modulo arithmetics with fractions actually meant multiply by its inverse.
x ≡ a/b (mod m)      ⇔      x ≡ a*b^-1 (mod m)      ⇔      b*x ≡ a (mod m)

Example: 5/4 ≡ -1/1 ≡ -1 (mod 3)
By keeping the mod 3 range of -1,0,1, mod 3 fractions is same as normal fractions.