-4
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ What is the question here? $\endgroup$ – Wojowu 2 days ago
  • $\begingroup$ 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/… $\endgroup$ – Vincent Granville 2 days ago
  • 9
    $\begingroup$ 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. $\endgroup$ – Emil Jeřábek 2 days ago

Your Answer

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

Browse other questions tagged or ask your own question.