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](https://math.stackexchange.com/questions/3834120/on-the-computational-complexity-of-reciprocal) 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.



What is the big-O time complexity of computing $1/N$ to $\log_{2}(N)$ bits of precision?
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](https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm).


As described by [Brent](https://scholar.google.com/scholar?cluster=5103058551561005766&hl=en&as_sdt=2005&sciodt=0,5),
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.


