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:


The result is this:


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.


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} <
    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

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}$.