Fast remainder
|
05-12-2021, 12:05 AM
Post: #3
|
|||
|
|||
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)The reason for the update is to compare effect of replacing 2 16-bits fastmod with 1 32-bits mod First experiment, for the inner loop: < d = fastmod((d + x[i-1])*n, k, c); < d = fastmod((d + x[i])*n, k, c); > d = (d + x[i-1])*n; > d = (d + x[i])*n % k For n=60, timings at 19.5 sec. (slower, by 5 sec) This confirmed Lemire's chart. fastmod is about 3 times as fast (blue vs red) --- We could pre-compute multiply constants and shifts, to speed-up quotient (x%k = x-q*k) Unfortunately, code is more involved ... I use libdivide.h, for fast divide. (It is just a header file, very easy to use; for C++, it is even easier) libdivide version is good. n=60 timings at 14.8 sec (slower, by only 0.3 sec) For this tiny cost, we have both quotient and remainder ! And, it cover more bases, 2n^3 ≤ 2^32 → Base n ≤ 1290 Code: #include <stdio.h> Perhaps of interest: How do compilers optimize divisions? http://homepage.divms.uiowa.edu/~jones/bcd/ |
|||
« 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)