(42, all flavours) Integer Division - how?

[Albert Chan]

Previously, we had tried mod 3, mod 9, mod 10 to get halfway floor-divide quotient.

a = (2*q+1) * h, where h = b/2, q is floor-divide quotient of a/b

Mod 2 seems impossible. With (2*q+1) odd, a, h have same parity.

Say, b = 2^k * b', where b' is odd. Reduced both side by 2^(k-1), and take mod 4, we have

a' ≡ (2*q+1) * h' (mod 4)

With a', h' both odd, a' ≡ ± 1 (mod 4), and so is h'

If a' ≡ +h' (mod 4), then 2*q+1 ≡ 1 (mod 4)      → q ≡ 0 (mod 2)
If a' ≡ -h' (mod 4), then 2*q+1 ≡ -1 (mod 4)      → q ≡ 1 (mod 2)

So, we can use mod 2 to get floor-divided quotient after all

\(\qquad\qquad\large q ≡ {a'-h' \over 2} ≡ {a-h \over 2^k} \normalsize \pmod 2 \)

Redo previous post example, using mod 2:

>>> from gmpy2 import *
>>> a, b = 6900, 120 # a/b = 57.5, a halfway case
>>> k = bit_scan1(b) # k = 3, see Find First Set
>>> q, h = 58, 60
>>> q - ((q&1) ^ (bit_test(a,k) ^ bit_test(h,k)))
57