11
$\begingroup$

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.

$\endgroup$
19
$\begingroup$

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
$\endgroup$
  • 1
    $\begingroup$ It seems like this is way more complicated than just computing $n\mod d$ and checking to see if it is zero. Is this actually computationally faster than the "naive" method? $\endgroup$ – TravisJ Apr 25 '15 at 15:13
  • $\begingroup$ @TravisJ Yes, integer division/modulo ranges from expensive to very expensive on CPUs. If I'm not mistaken two comparisons, one multiplication and one bitshift is faster than integer modulo on virtually every CPU in existence. This also extends to operations on very large integers. $\endgroup$ – orlp Apr 25 '15 at 15:17
  • 2
    $\begingroup$ I realize that, but your code is full of modular division (in the recursive egcd function and in a while-loop) as well as integer division and multiplication. Why not just do egcd(d, n)? If the result is d then $d\mid n$. $\endgroup$ – TravisJ Apr 25 '15 at 15:25
  • 3
    $\begingroup$ @TravisJ The code I listed is code to generate constants a and b. This is precomputation, and doesn't end up in the final code. The expressions all the way at the bottom of my answer is an example of the generated code for $76 \mid n$ for 64-bit integer $n$. $\endgroup$ – orlp Apr 25 '15 at 15:26
  • 2
    $\begingroup$ Ok, now I understand. This is only fast when your plan is to recycle the code over and over for a fixed d. The cost of pre-computation is amortized over many many runs of the (afterward) fast divisibility check. This is sort of similar to computing a "divisibility rule" (expensive up-front cost) then applying the rule later. $\endgroup$ – TravisJ Apr 25 '15 at 15:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.