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