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.

5more comments