# How to perform a very fast integer division by 3 or 5?

There was a question about this topic posted on StackExchange 12 years ago, see here. Basically, it says that there is nothing better than the 3000 years-old technique, and the suggestion in modern times is to "let the compiler do its job".

Well, here is what mine is doing. Divide the following integer by $$7$$:

222730506728397170591387079211836683557072632289734369842905278066498119541270318525897952142956554114412930297037751282


Then multiply the result by $$7$$. The result is this:

222730506728397170591387079211836683557072632289734369842905278066498119541270318525897952142956554114412930297037751276


The last two digits are wrong, despite using the BigInt library in Perl, no matter how I set precision and accuracy. I know you can compute the multiplication $$3x$$ very fast: $$3x = 2x + x = (x$$ << $$1) + x$$ using the bit shifting operator. But what about the division?

Question: I came up with the following rudimentary algorithms A, B, C below, but I am wondering if there is a faster solution. I want to divide a positive integer $$x$$ by $$3$$, knowing that $$\bmod(x,3)=0$$. I want the exact solution no matter how many digits $$x$$ has.

Also, how to choose $$p_1,\cdots,p_r$$ and $$r$$ in Algorithm B below?

Algorithm A: Digits in base 3

Let $$x$$ be the number to be divided by $$3$$. Pre-compute $$3^k$$ and $$2\cdot 3^k$$ for $$k=0,\cdots,n$$ with $$n=\lfloor\log_3 x\rfloor$$. In other words, $$n$$ is the largest integer such that $$3^n\leq x$$. Very useful step, since I have a bunch of large integers (all equal to zero modulo $$3$$) that I need to divide by $$3$$ and by any power of $$3$$ that is also a divisor. Here I assume $$x$$ is the largest of the integers that I am dealing with. Then the initialization step consists of:

• $$z \leftarrow x$$
• $$d_{n+1} \leftarrow 0$$
• $$n\leftarrow n+1$$

The loop consists of:

• $$y=z-d_n 3^n$$
• If $$2\cdot 3^{n-1} < y$$ then $$d_{n-1}=2$$ else if $$3^{n-1} < y$$ then $$d_{n-1}=1$$ else $$d_{n-1}=0$$.
• $$z \leftarrow y$$
• $$n\leftarrow n-1$$

Repeat the loop until $$n=0$$.

The sequence $$d_1,\cdots,d_n$$ is the digits of $$x/3$$ in base $$3$$. If $$3$$ divides $$x$$ then $$d_0=0$$. Thus $$\frac{x}{3}=\sum_{k=1}^nd_{k}3^{k-1}.$$

Note that $$2\cdot 3^{k} = 3^{k}$$ << $$1$$ (faster than the multiplication by $$2$$). In the final sum, use pre-computed values for $$d_k 3^{k-1}$$. The complexity is $$O(n)$$. No multiplication is required. It may be just as efficient as long division.

Algorithm B: Chinese remainder theorem

Consider $$r$$ positive integers $$p_1,\cdots,p_r$$, and let $$y=x/3$$. We have $$x = -p_k y +(3 + p_k)y, \mbox{ for } k=1,\cdots,r.$$ Instead of solving this, let $$z_k= \bmod(x,p_k)$$ and take the $$p_k$$ modulo on both sides. Then the congruential system to solve is

$$\bmod(3y,p_k) = z_k, \mbox{ for } k=1,\cdots,r.$$

Here the unknown is $$y$$, and both $$r$$ and $$p_1,\cdots,p_r$$ are chosen so as to obtain a unique solution $$y\leq x/3$$, as fast as possible.

Algorithm C: Modular multiplicative inverse

This is the same as Algorithm B, but with $$r=1$$. In this case, $$p_1$$ must be pretty large to have a unique solution $$y\leq x/3$$. If $$p_1$$ is a power of $$2$$, then the computations can be performed very fast. And $$3y$$ is the modular inverse of $$p_1$$ modulo $$z_1$$.

• What is the question here? – Wojowu 2 days ago
• How to perform an integer division by $3$ very fast, faster than my basic algorithm. I have a large list of big numbers, very dense in large prime numbers especially if you remove all factors that are a power of $2, 3$ or $5$. See mathoverflow.net/questions/374083/… and math.stackexchange.com/questions/3864776/… – Vincent Granville 2 days ago
• It is well known that integer division by any fixed constant can be done by a finite-state transducer, thus in online linear time and constant space. – Emil Jeřábek 2 days ago