Блог пользователя Bellala

What is the time complexity of calculating the inverse of n recursively？
Автор Bellala, история, 3 года назад, По-английски

I've always believed that getting the inverse of some integer n this way takes O(log(p)) time:

long long inv(long long n, long long p) {
	if (n == 1) return 1;
	return inv(p%n, p) * (p - p/n) % p;
}

But recently someone told me that it might be O(sqrt(p)).

So what is the correct time complexity?

  • Проголосовать: нравится
  • +17
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

It's the same as calculating gcd.

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +19 Проголосовать: не нравится

    I don't see, why does this hold. gcd swaps arguments, while in this function p is just parameter, it doesn't change during the recursion.

    → Ответить
    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      True, I'm not familiar with this code. I only know how to do this with the extended euclidean algorithm.

      → Ответить
»
3 года назад, # |
← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

Apparently this algorithm is attributed to Gauss. You can make it guaranteed $$$O(\log n)$$$ by noticing that $$$p = nq + r = n(q+1) - (n-r)$$$ and $$$\min(r, n - r) \le \frac n2$$$.

But no one usually analyses your simpler one-liner version.

→ Ответить
»
3 года назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

Its time complexity seems to be an open problem.

A common mistake is to consider it to be $$$O(\log(P))$$$ without thinking twice like above.

A problem discussed in this link is actually your problem.

And it gives an upper bound of $$$O(n^{1/3})$$$ and a lower bound of $$$\Omega(\dfrac{\log n}{\log\log n})$$$.

However it's not difficult to optimize it to $$$O(\log(n))$$$ as mmaxio shown above.

→ Ответить