Lines Matching +full:2 +full:d
8 * Suppose we have n = q * d, all integers. We know n and d, and want q = n / d.
11 * floor(ceil(2^k / d) * n / 2^k) = floor((2^k + r) / d * n / 2^k), where
12 * r = (-2^k) mod d.
15 * ... = floor(2^k / d * n / 2^k + r / d * n / 2^k)
16 * = floor(n / d + (r / d) * (n / 2^k)).
18 * The fractional part of n / d is 0 (because of the assumption that d divides n
20 * ... = n / d + floor((r / d) * (n / 2^k))
23 * (r / d) * (n / 2^k) < 1.
25 * r is a remainder mod d, so r < d and r / d < 1 always. We can make
26 * n / 2 ^ k < 1 by setting k = 32. This gets us a value of magic that works.
30 div_init(div_info_t *div_info, size_t d) { in div_init() argument
32 assert(d != 0); in div_init()
35 * (we would want magic = 2^32 exactly). This would mess with code gen in div_init()
38 assert(d != 1); in div_init()
41 uint32_t magic = (uint32_t)(two_to_k / d); in div_init()
44 * We want magic = ceil(2^k / d), but C gives us floor. We have to in div_init()
45 * increment it unless the result was exact (i.e. unless d is a power of in div_init()
48 if (two_to_k % d != 0) { in div_init()
53 div_info->d = d; in div_init()