patternMinor
Complexity of division
Viewed 0 times
divisioncomplexitystackoverflow
Problem
The article Computational complexity of mathematical operations mentions that the complexity of division in $O(M(n))$, and that "$M(n)$ below stands in for the complexity of the chosen multiplication algorithm".
But I'm not sure how to read that $M(n)$ embedded in $O(M(n))$: does it mean that the division has the same complexity as multiplication?
If I use, say, Karatsuba multiplication algorithm, will the division also take $O(n^{1.585})$
But I'm not sure how to read that $M(n)$ embedded in $O(M(n))$: does it mean that the division has the same complexity as multiplication?
If I use, say, Karatsuba multiplication algorithm, will the division also take $O(n^{1.585})$
Solution
The paper
Torbjörn Granlund and Peter L. Montgomery; "Division by Invariant Integers using Multiplication", Proceedings of the ACM SIGPLAN '94 conference on Programming Language Design and Implementation (PLDI):61-72, 1994.
gives the method used, in practice, to calculate (exact) integer division by producing an appropriate reciprocal (accurate to $n$ bits) of the divisor and also a shift amount. The division is then done by multiplying the dividend by the reciprocal and shifting.
The reciprocal can be found by Newton's method or Goldschmidt's method, as @Yuval stated in the comments. Those methods produce the reciprocal accurate to $n$ bits in $O(\log n)$ iterations. Each iteration requires a constant number of multiplications, and once you have the reciprocal you need one more multiplication to multiply the reciprocal by the dividend.
As pointed out by @gnasher729 in the comments, however, you don't need to do each iteration with full precision. Newton's iteration doubles the number of useful digits each iteration. So you can use, for example, 32 bit multiplies in the firsts iteration, 64 bit multiplies in the second, etc. Since that's a geometric sum it sums to a constant and you get $O(M(n))$.
Torbjörn Granlund and Peter L. Montgomery; "Division by Invariant Integers using Multiplication", Proceedings of the ACM SIGPLAN '94 conference on Programming Language Design and Implementation (PLDI):61-72, 1994.
gives the method used, in practice, to calculate (exact) integer division by producing an appropriate reciprocal (accurate to $n$ bits) of the divisor and also a shift amount. The division is then done by multiplying the dividend by the reciprocal and shifting.
The reciprocal can be found by Newton's method or Goldschmidt's method, as @Yuval stated in the comments. Those methods produce the reciprocal accurate to $n$ bits in $O(\log n)$ iterations. Each iteration requires a constant number of multiplications, and once you have the reciprocal you need one more multiplication to multiply the reciprocal by the dividend.
As pointed out by @gnasher729 in the comments, however, you don't need to do each iteration with full precision. Newton's iteration doubles the number of useful digits each iteration. So you can use, for example, 32 bit multiplies in the firsts iteration, 64 bit multiplies in the second, etc. Since that's a geometric sum it sums to a constant and you get $O(M(n))$.
Context
StackExchange Computer Science Q#57455, answer score: 5
Revisions (0)
No revisions yet.