CODEWITHSUNDEEP
cmath
Steven
Steven

Reputation: 871

Why this algorithm to determine is divisible or not work?

static inline bool is_divisible(uint32_t n, uint64_t M) {
    return n * M <= M - 1;
}

static uint64_t M3 = UINT64_C(0xFFFFFFFFFFFFFFFF) / 3 + 1;
....
uint8_t div3 = is_divisible(17, M3);

As mention in title, this function can determine whether n is divisible by 3. The only thing I figure out is that M is same as ceil((1<<64)/d) which d is 3.

Are there anyone call explain why is_divisible work? thanks!

Upvotes: 0

Views: 68

Answers (1)

Eric Postpischil
Eric Postpischil

Reputation: 222923

Divide n by 3 to find quotient q and remainder r, allowing us represent n as n = 3q + r, where 0 ≤ r < 3.

Intuitively, multiple 3q + r by (264−1)/3 + 1 causes the q portion to vanish because it wraps modulo 264, leaving the remainder portion to be in one of three segments of [0, 264) depending on the value of r. The comparison with M3 determines whether it is in the first segment, meaning r is zero. A proof follows.

Note that M3 is (264−1)/3 + 1.

Then n•M3 = (3q + r)•((264−1)/3 + 1) = q•(264−1)+3q+r•((264−1)/3 + 1) = q•264+2q+r•((264−1)/3 + 1).

When this is evaluated with uint64_t arithmetic, the q•264 term vanishes due to wrapping modulo 264, so the computed result is 2q+r•((264−1)/3 + 1).

Suppose n is a multiple of 3. Then r = 0. Since n is a uint32_t value, q < 232, so 2q+r•((264−1)/3 + 1) = 2q < 233 < M3.

Suppose n is not a multiple of 3. Then r = 1 or r = 2. If r = 1, r•((264−1)/3 + 1) = (264−1)/3 + 1 > M3−1. And, of course, if r = 2, r•((264−1)/3 + 1) is even greater and also exceeds M3−1. However, we need to be concerned about wrapping in uint64_t arithmetic. Again, since q < 232, we have, for r = 2, 2q+r•((264−1)/3 + 1) < 2•232 + 2•((264−1)/3 + 1) = 233 + 2/3•264 − 2/3 + 2 = 264 − 1/3•264 + 233 + 4/3, which is clearly less than 264, so no wrapping occurs.

Upvotes: 1

Related Questions