The math behind converting from any base to any base without going through base 10?

Question Detail: 

I've been looking into the math behind converting from any base to any base. This is more about confirming my results than anything. I found what seems to be my answer on mathforum.org but I'm still not sure if I have it right. I have the converting from a larger base to a smaller base down okay because it is simply take first digit multiply by base you want add next digit repeat. My problem comes when converting from a smaller base to a larger base. When doing this they talk about how you need to convert the larger base you want into the smaller base you have. An example would be going from base 4 to base 6 you need to convert the number 6 into base 4 getting 12. You then just do the same thing as you did when you were converting from large to small. The difficulty I have with this is it seems you need to know what one number is in the other base. So I would of needed to know what 6 is in base 4. This creates a big problem in my mind because then I would need a table. Does anyone know a way of doing this in a better fashion.

I thought a base conversion would help but I can't find any that work. And from the site I found it seems to allow you to convert from base to base without going through base 10 but you first need to know how to convert the first number from base to base. That makes it kinda pointless.

Commenters are saying I need to be able to convert a letter into a number. If so I already know that. That isn't my problem however. My problem is in order to convert a big base to a small base I need to first convert the base number I have into the base number I want. In doing this I defeat the purpose because if I have the ability to convert these bases to other bases I've already solved my problem.

Edit: I have figured out how to convert from bases less than or equal to 10 into other bases less than or equal to 10. I can also go from a base greater than 10 to any base that is 10 or less. The problem starts when converting from a base greater than 10 to another base greater than 10. Or going from a base smaller than 10 to a base greater than 10. I don't need code I just need the basic math behind it that can be applied to code.

Asked By : Griffin

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10318

Answered By : Andrej Bauer

This seems a very basic question to me, so excuse me if I lecture you a bit. The most important point for you to learn here is that a number is not its digit representation. A number is an abstract mathematical object, whereas its digit representation is a concrete thing, namely a sequence of symbols on a paper (or a sequence of bits in compute memory, or a sequence of sounds which you make when you communicate a number). What is confusing you is the fact that you never see a number but always its digit representation. So you end up thinking that the number is the representation.

Therefore, the correct question to ask is not "how to I convert from one base to another" but rather "how do I find out which number is represented by a given string of digits" and "how do I find the digit representation of a given number".

So let us produce two functions in Python, one for converting a digit representation to a number, and another for doing the opposite. Note: when we run the function Python will of course display the number it got in base 10. But this does not mean that the computer is keeping numbers in base 10 (it isn't). It is irrelevant how the computer represents the numbers.

def toDigits(n, b):     """Convert a positive number n to its digit representation in base b."""     digits = []     while n > 0:         digits.insert(0, n % b)         n  = n // b     return digits  def fromDigits(digits, b):     """Compute the number given by digits in base b."""     n = 0     for d in digits:         n = b * n + d     return n 

Let us test these:

>>> toDigits(42, 2) [1, 0, 1, 0, 1, 0] >>> toDigits(42, 3) [1, 1, 2, 0] >>> fromDigits([1,1,2,0],3) 42 

Armed with conversion functions, your problem is solved easily:

def convertBase(digits, b, c):     """Convert the digits representation of a number from base b to base c."""     return toDigits(fromDigits(digits, b), c) 

A test:

>>> convertBase([1,1,2,0], 3, 2)  [1, 0, 1, 0, 1, 0] 

Note: we did not pass through base 10 representation! We converted the base $b$ representation to the number, and then the number to base $c$. The number was not in any representation. (Actually it was, the computer had to represent it somehow, and it did represent it using electrical signals and funky stuff that happens in chips, but certainly those were not 0's and 1's.)