INNER CODE UNIT · Python
S
herumi/mcl · misc/mul-approx.py:24
S = 2**s
Q'=(x0 * p0) >> s
# (Q', R') = divmod(x0 * p0, S), x0 * p0 = Q' S + R', R' < S
(Q, R) = divmod(x, p), x = Q * p + R, R < p
# Theorem
0 <= Q - Q' <= 1
S p (Q - Q') = S (p Q) - p (S Q') = S(x - R) - p(x0 p0 - R')
= S(x0 * 2**(a-d) + x1 - R) - x0 p p0 + p R'
= 2**(2 d - e + a - d) x0 + S x1 - S R - x0 (2**(d+l-1) - p1)) + p R'
= 2**(d + l -1) x0 + S x1 - S R - x0 2**(d+l-1) + x0 p1 + p R'
= S x1 + p1 x0 + p R' - S R
Q - Q' = (x1/p) + (p1/p)(x0/S) + (R'/S) - (R/p)