INNER CODE UNIT · Python
e
herumi/mcl · misc/mul-approx.py:10
e = a - l + 1, then e <= d - 2
assume max(e) = 9
# Preparation
(p0, p1) = divmod(2**(d+l-1), p)
# 2**(d+l-1) = p0 * p + p1, p1 < p
# Quotient
input : x < 2**(l+e-1)
a = x.bit_length()
(x0, x1) = divmod(x, 2**(a-d))
# x = x0 * 2**(a-d) + x1, x1 < 2**(a-d)
s = 2 * d - e
S = 2**s
Q'=(x0 * p0) >> s
# (Q', R') = divmod(x0 * p0, S), x0 * p0 = Q' S + R', R' < S