3
$\begingroup$

I am considering large integer values of $N$ (100 or more digits in base-$10$).

In my algorithm, I need to be able to compute the reciprocal of $N$ with enough precision that the repetend will have been produced exactly. (I estimate this to be to $\lfloor \log N \rfloor$ digits or $\lfloor \log_{2} N \rfloor$ bits)

If I employ ordinary long division, how may I estimate the big-$\mathcal{O}$ time complexity of calculating $\frac{1}{N}$ with the desired level of precision?

I posted question(s) to this effect over on the Mathematics Stack Exchange, but have yet to garner an answer. I know that the complexity of the division of two $n$-digit numbers is $n^{2}$ using ordinary division, but that says nothing about the degree of precision required for non-terminating decimal expansions.

Thank you for your help.

Improve this question
$\endgroup$
10
  • $\begingroup$ Off the bat, I'm thinking about Newton's root-finding search on $f(x)=Nx-1$, it converges very quickly, though the exact complexity might be difficult. en.wikipedia.org/wiki/Root-finding_algorithms $\endgroup$ – DUO Labs Sep 21 '20 at 23:42
  • $\begingroup$ @DUO Yes. I think we can obtain as much precision as we want with Newton's Method. And if I remember correctly, that approach has Quadratic time complexity. And if I could be certain that that were also the case here, I would be happy. I'm just thinking that with the size of $N$ and the required precision, it could be worse than the complexity that Wikipedia, for example, gives for Newton's Method. $\endgroup$ – mlchristians Sep 21 '20 at 23:52
  • $\begingroup$ Actually, because the function is linear, it is guaranteed consistent performance (no extrema to get stuck in), as long as you start from pre-defined initial value, like $x_0=1$ or $x_0=0$. Also, you should be more concerned about space-- what are you doing with $N$ with "hundreds of digits", as you say? In addition, this is more suited for the Computer Science Stack Exchange. $\endgroup$ – DUO Labs Sep 22 '20 at 2:17
  • 3
    $\begingroup$ The number of digits in the period of $1/N$ can be as big as $N-1$. $\endgroup$ – Gerry Myerson Sep 22 '20 at 2:30
  • 1
    $\begingroup$ @user no, for the simple reason that there are no primes for which $4$ is a primitive root. Even if you throw out such trivial counterexamples, there is no $n$ for which it is proved that there are infinitely many primes for which $n$ is a primitive root. But it is very strongly believed that every $n$ which isn't disqualified for trivial reasons is a primitive root for infinitely many primes, and it is known that there are at most three exceptions. Look it up! $\endgroup$ – Gerry Myerson Sep 22 '20 at 12:20
5
$\begingroup$

Denote by $M_b$ the complexity of multiplying two $b$-digit integers $z = xy$. One easily sees that this is essentially obtained by convolving the $b$-dimensional vectors of digits $x*y$. The school algorithm is a "slow convolution" algorithm that takes $O(b^2)$, but fast convolution algorithms give rise to $M_b = O(b\log b)$ or $M_b = O(b\log^2 b)$ algorithms, see e.g. the Schönhage–Strassen algorithm.

As described by Brent, whatever the complexity of your multiplication algorithm, the Newton iteration for the reciprocal also takes $M_b$ pairwise operations on digits, provided that the number $b_k$ of digits at the $k$th Newton iteration grows in the right way (i.e. geometrically). In the first few Newton iterations, the accuracy is poor so you use few bits of accuracy. As you converge to $1/x$, you use more and more bits of accuracy.

As pointed out elsewhere, the period of $1/N$ could be as large as $N$ so you're looking at $O(N\log N)$ or $O(N\log^2 N)$ running time and $O(N)$ space.

Edit: in your title, you also ask about computing $1/N$ to $O(\log(N))$ bits of accuracy, which is possibly not enough to reveal the repeating pattern of $1/N$. As per above, computing $1/N$ with $O(\log(N))$ bits of accuracy, can be achieved in just a hair more than $O(\log(N))$ digitwise operations.

Improve this answer
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.