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.
 A: 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.
