Results 1 to 10 of 10
Like Tree4Thanks
  • 1 Post By emakarov
  • 2 Post By HallsofIvy
  • 1 Post By emakarov

Math Help - Base Conversion Algorithm

  1. #1
    Member
    Joined
    May 2011
    Posts
    179
    Thanks
    6

    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.
    Last edited by Bashyboy; March 19th 2013 at 07:40 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    May 2011
    Posts
    179
    Thanks
    6

    Re: Base Conversion Algorithm

    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 n that we want to convert to base b, and so we divide it by the natural number b, which is our desired base. I know a ratio is a comparison between two numbers.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Base Conversion Algorithm

    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    May 2011
    Posts
    179
    Thanks
    6

    Re: Base Conversion Algorithm

    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.
    Attached Thumbnails Attached Thumbnails Base Conversion Algorithm-capture.jpg  
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Base Conversion Algorithm

    Quote Originally Posted by Bashyboy View Post
    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 / bk-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 / bk-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 \underbrace{[(\dots((n/b)/b)/\dots)/b]}_{k-1\text{ divisions}}\mathbin{\%}b.

    Now, (\dots((n/b)/b)/\dots)/b=n/b^{k-1}. This can be shown as follows. We have x/y=\left\lfloor\frac{x}{y}\right\rfloor where \lfloor\cdot\rfloor is the floor function, x/y is integer division and \frac{x}{y} is regular division. And Wikipedia claims that \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 / bk-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.
    Thanks from Bashyboy
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,454
    Thanks
    1868

    Re: Base Conversion Algorithm

    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?
    Thanks from emakarov and Bashyboy
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    May 2011
    Posts
    179
    Thanks
    6

    Re: Base Conversion Algorithm

    Quote Originally Posted by emakarov View Post
    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 / bk-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 / bk-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 \underbrace{[(\dots((n/b)/b)/\dots)/b]}_{k-1\text{ divisions}}\mathbin{\%}b.

    Now, (\dots((n/b)/b)/\dots)/b=n/b^{k-1}. This can be shown as follows. We have x/y=\left\lfloor\frac{x}{y}\right\rfloor where \lfloor\cdot\rfloor is the floor function, x/y is integer division and \frac{x}{y} is regular division. And Wikipedia claims that \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 / bk-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?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Apr 2005
    Posts
    16,454
    Thanks
    1868

    Re: Base Conversion Algorithm

    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?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: Base Conversion Algorithm

    Quote Originally Posted by Bashyboy View Post
    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.

    dk, ..., d0 is a base b expansion of n if 0 ≤ di < b for 0 ≤ i ≤ k, dk ≠ 0 and dkbk + ... + d0 = 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.
    Last edited by emakarov; March 20th 2013 at 07:00 AM.
    Thanks from Bashyboy
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member
    Joined
    May 2011
    Posts
    179
    Thanks
    6

    Re: Base Conversion Algorithm

    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?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Base Conversion - Negative Base
    Posted in the Number Theory Forum
    Replies: 7
    Last Post: August 3rd 2010, 06:13 AM
  2. Replies: 4
    Last Post: May 26th 2010, 02:36 PM
  3. Replies: 0
    Last Post: January 27th 2010, 10:25 AM
  4. Number Base Conversion
    Posted in the Math Software Forum
    Replies: 2
    Last Post: September 14th 2009, 09:19 AM
  5. Inequalities and log base 2 search algorithm problem
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: August 29th 2007, 02:20 PM

Search Tags


/mathhelpforum @mathhelpforum