Fast remainder
|
05-12-2021, 03:10 PM
Post: #4
|
|||
|
|||
RE: Fast remainder
(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. |
|||
« Next Oldest | Next Newest »
|
Messages In This Thread |
Fast remainder - Albert Chan - 05-09-2021, 08:48 PM
RE: Fast remainder - Albert Chan - 05-10-2021, 02:44 PM
RE: Fast remainder - Albert Chan - 05-12-2021, 12:05 AM
RE: Fast remainder - Albert Chan - 05-12-2021 03:10 PM
RE: Fast remainder - Albert Chan - 05-12-2021, 11:03 PM
RE: Fast remainder - Albert Chan - 05-12-2021, 04:12 PM
RE: Fast remainder - Albert Chan - 05-14-2021, 06:15 PM
|
User(s) browsing this thread: 2 Guest(s)