Fast remainder
|
05-14-2021, 06:15 PM
Post: #7
|
|||
|
|||
RE: Fast remainder
Added another version, similar to fmod optimized version, with cached intermediates.
Just like fmod version, code just return raw data, we have to work out the digits. > polydivisible 10 { 3 38 1 16 5 54 7 72 9 } → {3,8,1,6,5,4,7,2,9} > polydivisible 14 { 9 138 3 52 5 74 7 104 11 162 1 16 13 } → {9,12,3,10,5,4,7,6,11,8,1,2,13} Code: #include <stdio.h> For n=60, timing reduced to 10.5 sec Also, base covered more cases, 0 < n ≤ 256 (technically 0 < n ≤ 257, but odd n has no solution). Lemire's general rule work well here: If n = 256 = 2^8, n^3 = 2^24 → N = 24 F = N - log2(d) → max(N) = 32 - 8 = 24, confirmed OK. Code: recurse(a, n, 1, x); // arrays all 1-based There is a subtle issue here, which turns out harmless. First call to recurse(), k=1, x[0] is accessed. I was going to add x[0] = 0, before recurse(), but turns out not needed. x%1 = fastmod(x, d=1, c=0) = 0, does not matter what x is. All d that is pow-of-2 had this property, fastmod without error (see previous post). |
|||
« 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)