Thread: Base Conversion Algorithm

Hello,

I am currently reading about base conversion algorithm. The one thing that the author of my textbook has failed to mention is, why does the remainders represent the digits of the number being converted. So, I thought I'd appeal to your minds.

Thank you for your time.

Does it have do with the fact that we are taking the ratio of a given number to the desired base; that is, we have some natural number $\displaystyle n$ that we want to convert to base $\displaystyle b$, and so we divide it by the natural number $\displaystyle b$, which is our desired base. I know a ratio is a comparison between two numbers.

I can take a shot at answering if you define precisely what "the digits of the number" are. That is, what is, by definition, the kth digit of n counting from the right?

Hmm...Are you asking me this because you aren't sure what I am asking, or because you are trying to check my understanding? Because, frankly, I am not sure how I would define that.

I attached a file that provides an excerpt from my textbook.

Originally Posted by Bashyboy

Hmm...Are you asking me this because you aren't sure what I am asking, or because you are trying to check my understanding? Because, frankly, I am not sure how I would define that.

One possible reason the textbook fails to give the reason for the correctness of this algorithm is that the authors thought it would be above the average reader's level. So I wanted to see if you can at least pose the problem rigorously, which is both a necessary and a significant step towards the solution.

OK, one way to define the kth digit (k = 1, 2, ...) of n base b counting from the right is (n / b^k-1) % b. Here (x / y) is the result of integer division and (x % y) is the remainder when x is divided by y (borrowing the notation from the C programming language). Indeed, (n / b^k-1) is n without the rightmost k - 1 digits, and % b returns the last digit of the result. For example, the 3rd (from the right) digit of 1354 is (1354 / 100) % 10 = 13 % 10 = 3.

The algorithm repeatedly divides n by b and takes the remainder of the result. According to the algorithm, the kth digit of n is $\displaystyle \underbrace{[(\dots((n/b)/b)/\dots)/b]}_{k-1\text{ divisions}}\mathbin{\%}b$.

Now, $\displaystyle (\dots((n/b)/b)/\dots)/b=n/b^{k-1}$. This can be shown as follows. We have $\displaystyle x/y=\left\lfloor\frac{x}{y}\right\rfloor$ where $\displaystyle \lfloor\cdot\rfloor$ is the floor function, $\displaystyle x/y$ is integer division and $\displaystyle \frac{x}{y}$ is regular division. And Wikipedia claims that $\displaystyle \left\lfloor \frac{\lfloor x/m\rfloor}{n} \right\rfloor = \left\lfloor \frac{x}{mn} \right\rfloor$ for positive integers m, n and arbitrary real number x, i.e., (x / m) / n = (x / mn).

Thus, the kth digit of n returned by the algorithm is (n / b^k-1) % b, which is exactly the definition.

Thinking again about this, it's not unreasonable to adopt the definition that the digits of n base b are the ones returned by this algorithm; then there is nothing to prove! Of course, if the definition is different from the ones above, then the proof has to change accordingly.

For example, to find the "digits" of 74 in base 3, divide 3 into 74- the quotient is 24 with remainder 2: 74= 24(3)+ 2. Then divide 24 by 3- the quotient is 8 with remainder 0: 24= 8(3)+ 0 so 74= (8(3)+ 0)(3)+ 2= 8(3^2)+ 0(3)+ 2. Then divide 8 by 3- the quotient is 2 with remainder 2: 8= 2(3)+ 2 so 74= (2(3)+ 2)(3^2)+ 0(3)+ 2= 2(3^3)+ 2(3^2)+ 0(3^1)+ 2(3^0).

Now do you see why those remainders are precisely the "digits" in that base?

Originally Posted by emakarov

One possible reason the textbook fails to give the reason for the correctness of this algorithm is that the authors thought it would be above the average reader's level. So I wanted to see if you can at least pose the problem rigorously, which is both a necessary and a significant step towards the solution.

OK, one way to define the kth digit (k = 1, 2, ...) of n base b counting from the right is (n / b^k-1) % b. Here (x / y) is the result of integer division and (x % y) is the remainder when x is divided by y (borrowing the notation from the C programming language). Indeed, (n / b^k-1) is n without the rightmost k - 1 digits, and % b returns the last digit of the result. For example, the 3rd (from the right) digit of 1354 is (1354 / 100) % 10 = 13 % 10 = 3.

The algorithm repeatedly divides n by b and takes the remainder of the result. According to the algorithm, the kth digit of n is $\displaystyle \underbrace{[(\dots((n/b)/b)/\dots)/b]}_{k-1\text{ divisions}}\mathbin{\%}b$.

Now, $\displaystyle (\dots((n/b)/b)/\dots)/b=n/b^{k-1}$. This can be shown as follows. We have $\displaystyle x/y=\left\lfloor\frac{x}{y}\right\rfloor$ where $\displaystyle \lfloor\cdot\rfloor$ is the floor function, $\displaystyle x/y$ is integer division and $\displaystyle \frac{x}{y}$ is regular division. And Wikipedia claims that $\displaystyle \left\lfloor \frac{\lfloor x/m\rfloor}{n} \right\rfloor = \left\lfloor \frac{x}{mn} \right\rfloor$ for positive integers m, n and arbitrary real number x, i.e., (x / m) / n = (x / mn).

Thus, the kth digit of n returned by the algorithm is (n / b^k-1) % b, which is exactly the definition.

Thinking again about this, it's not unreasonable to adopt the definition that the digits of n base b are the ones returned by this algorithm; then there is nothing to prove! Of course, if the definition is different from the ones above, then the proof has to change accordingly.

Oh, so there really isn't any special reason that the remainder's are the digits of the "new" number; it's simply the way mathematicians defined it to be, is that correct?

No, that's not at all what emakarov said! The crucial part of what he said relys on the "floor function" do you know what that is?

Originally Posted by Bashyboy

Oh, so there really isn't any special reason that the remainder's are the digits of the "new" number; it's simply the way mathematicians defined it to be, is that correct?

I would not say mathematicians defined it this way. This is just one definition, probably not the most natural. The most natural definition may be as follows.

d_k, ..., d₀ is a base b expansion of n if 0 ≤ d_i < b for 0 ≤ i ≤ k, d_k ≠ 0 and d_kb^k + ... + d₀ = n. (*)

It may not be immediately obvious that such expansion is unique, so this has to be proved. It is also not obvious that the algorithm returns such expansion, and post #6 is a nice explanation of this. It is also possible to prove the equivalence of (*) and the definition from post #5 or the one based on the algorithm (end of post #5). Then the proof of equivalence plus the reasoning in post #5 would be an explanation why the algorithm returns the expansion in the sense of (*).

To sum up, any precise argument why the algorithm is correct needs some definition of a base b expansion, and the argument would depend on such definition. We are used to decimal numbers and often think about natural numbers as strings of decimal digits: e.g., it is immediate to select the kth digit of a given number. However, this is not the input of the algorithm. The input can be thought of as an element of an abstract datatype, and the only things we may do with objects of this type are arithmetic operations and comparison. In particular, there is no predefined operation to produce the kth digit of base b expansion. Therefore, the specification of the algorithm, i.e., the property which the algorithm's output must satisfy, has to be given in terms of those arithmetic operations. In other words, we need to define base b expansion of n in terms of addition, multiplication, power, etc., and only then we can give reasons why the algorithm produces such an expansion.

Yes, I do know what the floor function is. What made me think that it was a definition was when he said, "Thinking again about this, it's not unreasonable to adopt the definition that the digits of n base b are the ones returned by this algorithm; then there is nothing to prove!" So, I thought that everything that preceded this statement was the rationale for defining it. But you, HallsofIvy, are saying it is a proof?