Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm reading a book on algorithms by Kurt Mehlhorn and Peter Sanders. On page 2, the following Theorem is stated:

The addition of two n-digit integers requires exactly n primitive operations. The result is an n+1-digit integer.

Is the result always n+1. What if you have 2 2-digit integers like 11 and 22 or others like that?

share|improve this question
    
At most $n+1$ digits (also, maybe the book considers $033$ as a $3$ digit number), and I don't think the last two tags are appropriate for this question –  Belgi Aug 5 '12 at 4:32
    
To use the decimal system as an example, consider the case when you're adding $\underbrace{99\dots99}_{n\text{ times}}$ to itself... –  J. M. Aug 5 '12 at 4:33

1 Answer 1

up vote 3 down vote accepted

It simply says that n+1 digits are sufficient to represent the sum. Keep in mind that you are reading a book on algorithms, the algorithm simply needs to be able to make an assumption that holds. If you were to check whether to use n or n+1 digits each time, you could save a few bits in some cases but the worst case space usage remains the same and you are increasing the time taken unecessarily. On that line, even when it refers to n-digit integers here, it does not necessarily mean that the leading digit in any of them is necessarily non-zero here.

In fact, the text here makes this same point right before starting the section on addition: "We can artificially turn any n-digit integer into an m-digit integer for any m≥n by adding additional leading zeros. Concretely, “425” and “000425” represent the same integer. We shall use a and b for the two operands of an addition or multiplication and assume throughout this section that a and b are n-digit integers. The assumption that both operands have the same length simplifies the presentation without changing the key message of the chapter. We shall come back to this remark at the end of the chapter.We refer to the digits of a as an−1 to a0, with an−1 being the most significant digit (also called leading digit) and a0 being the least significant digit, and write a = ($a_{n−1} . . . a_0$). The leading digit may be zero."

To see why n+1 digits are sufficient here, if you are working in base b, then any n-digit number is less than $b^n$, so the sum of two such numbers is less than $2b^n$, which is less than or equal to $b^{n+1}$ if b is at least 2. Being less than $b^{n+1}$ means that n+1 digits are sufficient to represent it.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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