INNER CODE UNIT · Python
l
herumi/mcl · misc/mul-approx.py:6
l = p.bit_length(), then 2**(l-1) <= p < 2**l
a = x.bit_length(), then 2**(a-1) <= x < 2**a
assume d < l <= a <= l + d - 3
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