dkh.fastdiv source code

1 module dkh.fastdiv;
2 
3 import dkh.foundation, dkh.int128;
4 
5 /**
6 Barrett reductionを使用し、高速除算を行う。
7 ulongをこれで置き換えれば大体うまく動く。
8  */
9 struct FastDivULong {
10     const ulong value, m;
11     const int lg;
12     this(ulong value) {
13         import core.bitop : bsr;
14         this.value = value;
15         assert(value);
16         if (value <= 1) return;
17         int _lg = value.bsr;
18         if (1UL<<_lg != value) _lg++;
19         lg = _lg;
20         m = div128([0UL, (2UL<<(lg-1))-value], value)+1;
21     }
22     ulong opBinaryRight(string op:"/")(ulong x) const {
23         if (value == 1) return x;
24         ulong r;
25         r = mul128(m, x)[1];
26         r = (r + ((x-r)>>1)) >> (lg-1);
27         return r;
28     }
29     ulong opBinaryRight(string op:"%")(ulong x) const {
30         return x - (x/this)*value;
31     }
32 }
33 
34 ///
35 unittest {
36     assert(11 / FastDivULong(3) == 3);
37     assert(11 % FastDivULong(3) == 2);
38 }
39 
40 unittest {
41     ulong[] up;
42     ulong[] down;
43     up ~= 0;
44     foreach (ulong i; 1..1000) {
45         up ~= i;
46         up ~= -i;
47     }
48     foreach (ulong i; 1..1000) {
49         down ~= i;
50         down ~= -i;
51     }
52     foreach (ulong i; down) {
53         auto b = FastDivULong(i);
54         foreach (ulong j; up) {
55             assert(j/b == j/i);
56             assert(j%b == j%i);
57         }
58     }
59 }