1
$\begingroup$

I have been reading [1] recently. On page xxi, the authors wrote: "For example, multiplying 577 by 423 using repeated addition requires 422 additions, whereas doing it with the grade-school algorithm takes 3 multiplications of a number by a single digit and 3 additions."

The above statement is wrong. There are only 2 additions because 1731+11540+230800=244071 (see page xx) only requires 2 additions. Am I right?

Reference

[1] S. Arora and B. Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

$$ 2961 + 29610 + 211500 = 244071. $$

There are only 2 additions still. You are right again!

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you for your answer. $\endgroup$
    – Wei-Cheng Liu
    Commented Apr 16, 2022 at 8:59
  • 1
    $\begingroup$ @Wei-ChengLiu You are welcome. $\endgroup$
    – John L.
    Commented Apr 16, 2022 at 8:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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