5
$\begingroup$

My favourite algorithm textbook: The Algorithm Design Manual S. Skiena.pdf had this interesting problem:

1-28. [5] Write a function to perform integer division without using either the / or * operators. Find a fast way to do it.

What's the lower bound for asymptotic complexity of this problem? `

P.S: I know repeated subtraction with a will work. It has asymptotic linear complexity with b (case where a = 1). However, repeated subtraction has exponential complexity with $n$ where $n$ is the number of bits needed to represent the number. Specifically it is $\Theta(2^n)$. So it is definitely not fast.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ It'd be interesting to try implementing Goldschmidt's algorithm and seeing how that goes. $\endgroup$
    – Pseudonym
    Dec 24, 2016 at 2:40

1 Answer 1

Reset to default
7
$\begingroup$

Wikipedia has a nice page about the complexity of mathematical operations, and there is also a dedicated page about division. Asymptotically, division has the same complexity as multiplication. The fastest known algorithm, due to Harvey and van der Hoeven, runs in time $O(n\log n)$. However, this algorithm isn't practical (it is not fast in practice, since the integers aren't large enough). Wikipedia lists no known lower bounds, though some people believe that the complexity should be $\Omega(n\log n)$, and there are some bounds in weak models. See for example Lower Bounds for Multiplication via Network Coding by Afshani, Freksen, Kamma, and Larsen.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.