4
$\begingroup$

I've been reading around the area of complexity and arithmetic operations using logic gates; one thing that is confusing me is that \begin{equation} \Theta (n^{2}) \end{equation} is quoted as being the complexity for multiplication for iterative adition. But addition of a number requires \begin{equation} log_2(n) \end{equation} operations, 1 for each bit or 8 times that for each nand gate involved in doing this. So it strikes me as obvious that adding that number n times will have a complexity of \begin{equation} n \log_2(n) \end{equation} Which is definitely less than \begin{equation} \Theta (n^{2}) \end{equation} So where is this additional factor of \begin{equation} \frac{n}{\log_2(n)} \end{equation} coming from?

|cite|improve this question
$\endgroup$
  • 5
    $\begingroup$ Check which model of computation is assumed, and what $n$ denotes exactly. $\endgroup$ – Raphael♦ Feb 3 '16 at 12:01
  • $\begingroup$ @Raphael +1 Good advice. When working with numbers, this is very a common detail to get mixed up. $\endgroup$ – Lan Feb 3 '16 at 13:01
  • $\begingroup$ Nobody sane would calculate $a \times b$ by adding $a$ together $b$ times. There are far more efficient multiplication algorithms, some of which you should've learned in grade school. $\endgroup$ – Ilmari Karonen Feb 3 '16 at 15:26
  • $\begingroup$ I am aware that this is far from how multiplication is executed in modern computors. I was just confused at the compexity given for this method. I am curious though which methods should I have been taught for multiplication? I'm not sure I can recall any. I read your link and do recall learning long multiplication (not really something that needs teaching, very intuitive), but that isn't any more efficient for a computor. $\endgroup$ – Duke of Sam Feb 3 '16 at 15:53
  • $\begingroup$ Ah yes, I see how the "shift and add" method is alot faster than iterative adition. Not so easy to understand its implimentation at a bit level though. $\endgroup$ – Duke of Sam Feb 3 '16 at 15:58
8
$\begingroup$

Addition of a number of size $n$ takes time $O(n)$. Don't confuse a number and its encoding size, which is logarithmically smaller.

When multiplying an $n$-bit integer $a$ by an $n$-bit integer $b$ using the iterative addition algorithm, you are adding up to $n$ shifted copies of $a$. Each addition costs you $O(n)$ rather than $O(\log n)$. The numbers $a,b$ itself could be as large as $2^n$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thanks. So for n-bit times a the complexity is a*n? $\endgroup$ – Duke of Sam Feb 3 '16 at 14:23
  • $\begingroup$ Yes, that's right. $\endgroup$ – Yuval Filmus Feb 3 '16 at 14:24

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.