# computational complexity – Fast 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 3:

``````222730506728397170591387079211836683557072632289734369842905278066498119541270318525897952142956554114412930297037751282
``````

The result is this:

``````74243502242799056863795693070612227852360000000000000000000000000000000000000000000000000000000000000000000000000000000
``````

Obviously it is totally wrong, despite using the BigNum library in Perl. 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?

I came up with the following rudimentary algorithm, but I am wondering if there is a faster solution.

Algorithm

Let $$x$$ be the number to be divided by $$3$$. Pre-compute $$3^k$$ and $$2cdot 3^k$$ for $$k=0,cdots,n$$ with $$n=lfloorlog_3 xrfloor$$. In other words, $$n$$ is the largest integer such that $$3^nleq 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$$
• $$nleftarrow n+1$$

The loop consists of:

• $$y=z-d_n 3^n$$
• If $$2cdot 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$$
• $$nleftarrow 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 $$2cdot 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}$$.