Is there a fast divisibility check for a fixed divisor?

Is there a fast algorithm to check if $d \mid n$ is true for varying $n$, if divisor $d$ is fixed?

Variable $n$ is a $w$-bit binary integer, $d$ is an integer constant.

Solution 1:

Yes, there is an algorithm that only uses multiplication. This algorithm uses a lot of precomputation, but generates a simple expression that can be used to check for divisibility.

For example, if you have an 4 bit integer, and want to check if it's divisible by 3 it's enough to check (using 4-bit modular multiplication):

n * 11 <= 5

The example for $0 \leq n \leq 7$:

0 * 11 = 0  <= 5
1 * 11 = 11
2 * 11 = 6
3 * 11 = 1  <= 5
4 * 11 = 12
5 * 11 = 7
6 * 11 = 2  <= 5
7 * 11 = 13

I will first demonstrate and prove correct a technique for uneven $d$, and then for even $d$. I define $m = 2^w$.

Uneven $d$.

Find the modular multiplicative inverse $a$ of $d$ modulo $m$:

$$ad \equiv 1 \pmod m \tag{1}$$

This exists because $\gcd(d, m) = 1$ since $d$ is uneven. Also find $b$:

$$b = \left\lfloor {m-1\over d}\right\rfloor \tag{2}$$

Using (1) we get the following identity:

$$d(an \bmod m) = n \Leftrightarrow d \mid n \tag{3}$$

Now we create this equivalence, by multiplying both sides by $d$:

$$an \bmod m \leq b \Leftrightarrow d(an \bmod m) \leq bd \tag{4}$$

Because $bd \leq m - 1$ and (1):

$$d(an \bmod m) \leq m-1 \Leftrightarrow d(an \bmod m) = n \tag{5}$$

Combining (3), (4) and (5) gives us our fast check:

$$an \bmod m \leq b \Leftrightarrow d \mid n \tag{6}$$

This is fast because we turned a modulo $n$ into a modulo $m$. Arithmetic modulo $m$ is very cheap because it's a power of two, and on fixed-width integers (such as uint64_t in C++) it is free.

Even $d$.

Write $d$ as $2^j\cdot k$ with $k$ odd. Then we will check two conditions:

$$d \mid n \Leftrightarrow k \mid n \wedge 2^j \mid n$$

We check $k \mid n$ through the method for odd numbers above. We can check $2^j \mid n$ by using:

$$2^j \mid n \Leftrightarrow n2^{w-j} \equiv 0 \mod m$$

Since we're multiplying by a power of two we can use a bitshift to further speed things up.

Generating $a$, $b$, $j$.

I'm in a helpful mood, so here's a small Python3 function that given $d$ and $w$ prints the expressions you need to check to find if $d \mid n$. It assumes that << and * use $w$-bit arithmetic.

import math

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def fast_div(d, w):
    m = 2**w

    j = 0
    while d % 2 == 0:
        d //= 2
        j += 1

    if j > 0:
        print("n << {} == 0".format(w-j))
    if d > 1: 
        print("n * 0x{0:0{2}x} <= 0x{1:0{2}x}".format(egcd(d, m)[1] % m, m // d,
                                                      math.ceil(w/4)))

So for example fast_div(76, 64) prints:

n << 62 == 0
n * 0x86bca1af286bca1b <= 0x0d79435e50d79435