Post Reply 
(42, all flavours) Integer Division - how?
12-25-2020, 01:07 PM
Post: #59
RE: (42, all flavours) Integer Division - how?
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 Smile

\(\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
Find all posts by this user
Quote this message in a reply
Post Reply 


Messages In This Thread
RE: (42, all flavours) Integer Division - how? - Albert Chan - 12-25-2020 01:07 PM



User(s) browsing this thread: 1 Guest(s)