# What is the big-O time complexity of computing $1/N$ to $\log_{2}(N)$ bits of precision?

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.

• 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 – DUO Labs Sep 21 '20 at 23:42
• @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. – mlchristians Sep 21 '20 at 23:52
• 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. – DUO Labs Sep 22 '20 at 2:17
• The number of digits in the period of $1/N$ can be as big as $N-1$. – Gerry Myerson Sep 22 '20 at 2:30
• @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! – Gerry Myerson Sep 22 '20 at 12:20

## 1 Answer

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.