Fast remainder

[Albert Chan]

(05-10-2021 02:44 PM)Albert Chan Wrote:  Update2: unroll loop 1 time (but, 2 fastmod per loop), n=60 timing at 14.5 sec (1.5 sec saving)

My estimate is too conservative. Base is small, much less than 16 bits.
If base n ≤ 128, we may reduce 2 fastmod to 1, and still maintain correctness.

Or, keep the code as is, but pushed up base, n ≤ 1024.

Faster Remainder by Direct Computation: Applications to Compilers and Software Libraries

Conclusion part of Algorithm 1 Wrote:On this basis, Algorithm 2 gives the minimal number of fractional bits F. It is sufficient to pick F ≥ N + log2(d)

x % d = fastmod(x, d, c)                         // 0 < x < 2^N
c = ceil(2^F/d) = floor((2^F-1)/d)+1       // pre-computed

Our code is using 32-bits unsigned, F = 32

d = 1 to n-1 ⇒ d < n.
If n = 128 = 2^7, then log2(d) < 7

F ≥ N + log2(d)
max(N) = 32 - 7 = 25

If we combined 2 fastmod into 1, we have:

x = ((d + x[i-1])*n + x[i])*n < 2*n^3 = 2^(1 + 3*log2(n))

N ≤ 1+3*7 = 22 ≤ 25, thus we are safe.

---

Without combining 2 fastmod into 1, but pushed up base to maximum of 1024 = 2^10

max(N) = 32 - 10 = 22

x = (d + x[i-1])*n < 2*n^2 = 2^(1 + 2*log2(n))

N ≤ 1+2*10 = 21 ≤ 22, thus we are safe.