(42, all flavours) Integer Division - how?

[Albert Chan]

(12-21-2020 07:51 AM)Werner Wrote:  Hi Albert,
can that then not be simplified to verifying whether

a = (1-q)*h (mod 3)

and if not equal q := q-1

Yes ! For halfway case, s = ±1. If s≠1 then s=-1
I "divided" both side by h, only to show mod 3 test cannot have h with factor of 3.

With assumed s=1, we can also do mod 9 test.
mod 9 test allowed b having 1 factor of 3, instead of none at all.

a = q*b + s*h
a-h ≡ q*b (mod 9), if s=1

We start with sum-of-digits, to expand for non-integer inputs. (e.g. 1.2e-9 → 1+2 → 3)
Redoing previous post examples, but scale up both a, b by 3

lua> a, b = 2300*3, 40*3
lua> q = rint(a/b)
lua> a, b, q, a%b
6900      120      58      60

This is halfway case, with b%9 = 3 ≠ 0. We do mod 9 test.

a-h ≡ (6+9) - 6 ≡ 6 - 6 ≡ 0
q*b ≡ (5+8)*3 ≡ 4*3 ≡ 12 ≡ 3
→ s≠1, return q-1 = 57

lua> a, q = -a, -q -- 2nd example
lua> a, b, q, a%b
-6900      120      -58      60

a-h ≡ -(6+9) - 6 ≡ -6 - 6 ≡ -12 ≡ 6
q*b ≡ -(5+8)*3 ≡ -4*3 ≡ -12 ≡ 6
→ s=1, return q = -58

---

Even if initial q was wrongly rounded, we still get the right correction.

1st example, but q wrongly rounded 57.5 to 57:
q*b ≡ (5+7)*3 ≡ 3*3 ≡ 0      → = a-h (mod 9), return q = 57

2nd example, but q wrongly rounded to -57.5 to -57:
q*b = -(5+7)*3 ≡ 3*3 ≡ 0     → ≠ a-h (mod 9), return q-1 = -58