Let $N$ be a positive integer.
I would like to determine $\mathcal{O}(\frac{1}{N})$.
Let $n$ denote the number of bits in $(N)_{2}$, the binary representation of $N$.
If ordinary long division is used, am I correct in assuming that the calculation of the reciprocal of $N$ will be $\mathcal{O}(n)$? My reasoning is this—
In the case of dividing the integer $a$ by the integer $b$, the Big-O time complexity associated the decimal expansion of the fraction $\frac{a}{b}$ is (I am presuming), $len(a) \cdot len(b)$, where $len$ is the number of bits in the binary form of the integers $a$ and $b$, respectively. Hence, for $\left(\frac{1}{N}\right)_{2} = \frac{1}{n}$, $\mathcal{O}(1/N) = len1 \cdot lenN$ = $n$.
Is this reasoning correct?
Incidentally, the $N$s I have in mind are very, very large. I expect that this does not matter in terms of obtaining a big-$\mathcal{O}$ estimate, but please advise me if it does.
Many thanks.
Best Answer
Assuming "if ordinary long division is used," computing $1/N$ in binary representation far enough "to produce the exact repetend" will take up to $\mathcal O(nN)$ bit operations.
Consider the complexity of a single step of the usual long division algorithm, carried out we presume in binary arithmetic. We will subtract one $n$-bit operand from another, which means $n$ subtract-with-borrow operations.
We then need to bound the length of the repetend -- the repeating sequence of the binary representation of the reciprocal $1/N$ -- because that relates the number of subtraction steps required by the long division. We cannot be sure a priori how many such steps are necessary, and one might argue that in the steps where the trial dividend bit is zero, no actual subtraction is necessary. On the other hand we are looking for an upper bound, and furthermore checking whether zero or one is right trial dividend bit is a comparison of two $n$-bit quantities, so one may need to carry out the subtraction in order to know whether or not it is needed.
Interestingly the length $k$ of the repeating sequence is the multiplicative order of $2$ modulo the largest odd divisor of $N$. One would generally have removed any even factor of $N$ to begin with (the trailing zeros of its binary representation, so a known quantity) and thus reducing to the case $N$ itself is odd. We will assume so for the rest of the discussion.
This is often discussed in the context of a repeating decimal expansion here on Math.SE. See for example this previous Question and Ross Millikan's Answer, tying the length of the repeating decimal part $k$ to the minimal positive integer such that $10^k \equiv 1 \bmod N$.
As a practical matter, although one can separately determine that length in advance, one can simply carry out the long division until a remainder of one is obtained. That's where our division $1/N$ started, so if we reach that point again, all the steps will repeat afterwards.
Now how big can $k$ be? As the multiplicative order of $2$ in $\mathbb Z/N\mathbb Z$ divides Euler's totient function $\varphi(N)$, that gives us an upper bound. In fact Artin's conjecture on primitive roots implies that for infinitely many prime values of $N$, this multiplicative order $k$ will be $N-1$. (Recall the well-known decimal case of $1/7$ having a repetend length six... because $10^6 \equiv 1 \bmod 7$.) For more information see the Wikipedia article Full repetend prime.