49
$\begingroup$

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.

$\endgroup$
5
  • 2
    $\begingroup$ Is this question on topic for this forum? $\endgroup$ Mar 6, 2013 at 14:31
  • 2
    $\begingroup$ The procedure is trivial as long as you can do addition and multiplication in the target base. If you can't, I don't think it's possible. $\endgroup$ Mar 6, 2013 at 15:23
  • 12
    $\begingroup$ Griffin should first be told what many students need to hear: numbers exist without being represented in a base. Then the answer is clear: we need to algorithms, one for convering a representation of a number in a given base to the number (that is, something which takes a string and returns an int), and an algorithm which takes a number and returns its representation in a given base. $\endgroup$ Mar 6, 2013 at 15:23
  • 2
    $\begingroup$ @AndrejBauer The question is about CS: even if it isn't worded that way, this is a question about an algorithm to convert between number representations. [Unrelated note: I deleted a bunch of confusing comments. Griffin: please edit your question to update it. Others: please take it to chat.] $\endgroup$ Mar 6, 2013 at 17:48
  • 1
    $\begingroup$ @Griffin it's been a long time since your original question. I hope you've found your answer. If so maybe it could be a great idea to update and accept an answer or post yours. In the meantime I've found a couple of very nice ideas (talking about implementation in C++) in Google's Code Jam Archives. Some solutions for this problem are very creative code.google.com/codejam/contest/32003/dashboard $\endgroup$ May 15, 2015 at 13:05

8 Answers 8

69
$\begingroup$

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 question to ask is not "how do 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". Once we have the answers, it will be easy to answer the original question, too.

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 print on the screen 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.)

$\endgroup$
17
  • 6
    $\begingroup$ This doesn't convince me 100%. In fact, you did convert the number to some representation (although you can claim not to know what it is) because computers are not platonic mathematicians and your algorithm cannot convert an arbitrary sequence of digits in base $b_1$ to base $b_2$; it can only convert sequences representable by the concrete machine. Python is charmingly flexible; C would not have been so forgiving. It is a perfectly valid to ask how to convert arbitrary strings from $b_1$ to $b_2$; however, this is only possible in linear time except with certain base combinations (eg. 2<->16) $\endgroup$
    – rici
    Mar 7, 2013 at 21:29
  • 3
    $\begingroup$ This does pass the number through base 10 representation, as the fromDigits returns the number in base 10. $\endgroup$
    – apnorton
    Mar 8, 2013 at 2:12
  • 16
    $\begingroup$ @anorton: No, most definitely it does not. Python prints the number on screen in base 10 digit representation, but the number itself is not stored that way. What I am trying to get accross is that it is irrelevant how the numbers are implemented inside Python. It does not matter. The only thing that matters is that they behave like numbers. $\endgroup$ Mar 8, 2013 at 2:47
  • 2
    $\begingroup$ Hmmm... I guess I concede--I see your point now (the sentence "prints the number on screen..." was what I needed to read to see what you were saying.) Thanks for your patience with an obstinate person... :) $\endgroup$
    – apnorton
    Mar 8, 2013 at 2:55
  • 3
    $\begingroup$ Finally a general solution for any base and not limited to particular use cases, bases less than 36, or instances where you can come up with enough unique symbols. $\endgroup$
    – J.Money
    Dec 22, 2015 at 13:26
28
$\begingroup$

I think the best way to understand this is in discussion with an alien (at least as an analogy).

Definition $x$ is a number in base $b$ means that $x$ is a string of digits $<b$.

Examples The string of digits 10010011011 is a number in base 2, the string 68416841531 is a number in base 10, BADCAFE is a number in base 16.

Now Suppose I grew up on the planet QUUX where everyone is taught to work in $q$ for their whole lives, and I meet you who is used to base $b$. So you show me a number, and what do I do? I need a way to interpret it:

Definition I can interpret a number in base $b$ (Note: $b$ is a number in base $q$) by the following formula

$$\begin{array}{rcl} [\![\epsilon]\!] &=& 0 \\ [\![\bar s d]\!] &=& [\![\bar s]\!] \times b + d \end{array}$$

where $\epsilon$ denotes the empty string, and $\bar s d$ denotes a string ending in the digit $d$. See my proof that addition adds for an introduction to this notation.

So what's happened here? You've given me a number in base $b$ and I've interpreted it into base $q$ without any weird philosophy about what numbers truly are.

Key The key to this is that the $\times$ and $+$ I have are functions that operate on base $q$ numbers. These are simple algorithms defined recursively on base $q$ numbers (strings of digits).


This may seem a bit abstract since I've been using variables rather than actual numbers throughout. So let's suppose you are a base 13 creature (using symbols $0123456789XYZ$) and I am used to base 7 (which is much more sensible) using symbols $\alpha \beta \gamma \delta \rho \zeta \xi$.

So I've seen your alphabet and tabulated it thus:

$$\begin{array}{|c|c||c|c||c|c|} \hline 0 & \alpha & 1 & \beta & 2 & \gamma \\ 3 & \delta & 4 & \rho & 5 & \zeta \\ 6 & \xi & 7 & \beta\alpha & 8 & \beta\beta \\ 9 & \beta\gamma & X & \beta\delta & Y & \beta\rho \\ & & Z & \beta\zeta & & \\ \hline \end{array}$$

So I know that you work in base $\beta\xi$, and I know what base 7 number any digit you write corresponds to.

Now if we were discussing physics and you were telling me about fundamental constants (say) $60Z8$ so I need to interpret this:

$$\begin{array}{rcl} [\![60Z8]\!] &=& \xi (\beta\xi)^3 + \alpha (\beta\xi)^2 + \beta \zeta (\beta\xi) + \beta\beta \\ \end{array}$$

So I start by multiplying out $\beta \zeta \times \beta\xi$ but this is grade school stuff for me, I recall:

Quux multiplication table

$$\begin{array}{|c|cccccc|} \hline \\ \times & \beta & \gamma & \delta & \rho & \zeta & \xi \\ \hline \beta & \beta & \gamma & \delta & \rho & \zeta & \xi \\ \gamma & \gamma & \rho & \xi & \beta\beta & \beta\delta & \beta\zeta \\ \delta & \delta & \xi & \beta\gamma & \beta\zeta & \gamma\beta & \gamma\rho \\ \rho & \rho & \beta\beta & \beta\zeta & \gamma\gamma & \gamma\xi & \delta\delta \\ \zeta & \zeta & \beta\delta & \gamma\beta & \gamma\xi & \delta\rho & \rho\gamma \\ \xi & \xi & \beta\zeta & \gamma\rho & \delta\delta & \rho\gamma & \zeta\beta \\ \beta\alpha & \beta\alpha & \gamma\alpha & \delta\alpha & \rho\alpha & \zeta\alpha & \xi\alpha \\ \hline \end{array}$$

so to find $\beta \zeta \times \beta\xi$ I do:

$$\begin{array}{ccc} & \beta & \zeta \\ \times & \beta & \xi \\ \hline & \xi & \gamma \\ & \rho & \\ \beta & \zeta & \\ \hline \delta & \beta & \gamma \\ \gamma & & \\ \end{array}$$

so I've got this far

$$\begin{array}{rcl} [\![60Z8]\!] &=& \xi (\beta\xi)^3 + \alpha (\beta\xi)^2 + \beta \zeta (\beta\xi) + \beta\beta \\ &=& \xi (\beta\xi)^3 + \alpha (\beta\xi)^2 + \delta \beta \gamma + \beta\beta \\ \end{array}$$

Now I need to perform the addition using the algorithm which was mentioned before:

$$\begin{array}{ccc} \delta & \beta & \gamma \\ & \beta & \beta \\ \hline \delta & \gamma & \delta \\ \end{array}$$

so

$$\begin{array}{rcl} [\![60Z8]\!] &=& \xi (\beta\xi)^3 + \alpha (\beta\xi)^2 + \beta \zeta (\beta\xi) + \beta\beta \\ &=& \xi (\beta\xi)^3 + \alpha (\beta\xi)^2 + \delta \beta \gamma + \beta\beta \\ &=& \xi (\beta\xi)^3 + \alpha (\beta\xi)^2 + \delta \gamma \delta \\ \end{array}$$

and continuing this way I get $$[\![60Z8]\!] = \zeta\delta\xi\gamma\rho.$$


In summary: If I have my own conception of number in terms of base $q$ strings of digits, then I have way to interpret your numbers from base $b$ into my own system, based on the fundamental arithmetic operations - which operate natively in base $q$.

$\endgroup$
12
  • 4
    $\begingroup$ Well that was a good deal of squiggly lines. How would I get the computer to do that though? $\endgroup$
    – Griffin
    Mar 12, 2013 at 21:17
  • 1
    $\begingroup$ @Griffin, I think you are asking that (strange) question prematurely. You pick a programming language and type out the algorithm for addition and multiplication on base q numbers (represented as lists of digits), then define a function to interpret base b digits into base q numbers and interpret base b numbers into base q numbers. I've explained all this. $\endgroup$
    – user7081
    Mar 12, 2013 at 21:29
  • $\begingroup$ Thing is I know the concept your trying to portray. My problem is my computer can't use your squiggly lines. $\endgroup$
    – Griffin
    Mar 12, 2013 at 21:32
  • 1
    $\begingroup$ I know what you explained but putting it into practice is far harder. You see defining those digits isn't as easy. $\endgroup$
    – Griffin
    Mar 12, 2013 at 21:33
  • 1
    $\begingroup$ Also why did you drop the alpha digit in the most significant position? Since 6 = &xi;, Wouldn't 7 = &alpha;&alpha;? $\endgroup$ Sep 30, 2014 at 13:56
12
$\begingroup$

This is a refactoring (Python 3) of Andrej's code. While in Andrej's code numbers are represented through a list of digits (scalars), in the following code numbers are represented through a list of arbitrary symbols taken from a custom string:

def v2r(n, base): # value to representation
    """Convert a positive number to its digit representation in a custom base."""
    if n == 0: return base[0]
    b = len(base)
    digits = ''
    while n > 0:
        digits = base[n % b] + digits
        n  = n // b
    return digits

def r2v(digits, base): # representation to value
    """Compute the number represented by string 'digits' in a custom base."""
    b = len(base)
    n = 0
    for d in digits:
        n = b * n + base[:b].index(d)
    return n
    
def b2b(digits, base1, base2):
    """Convert the digits representation of a number from base1 to base2."""
    return v2r(r2v(digits, base1), base2)

To perform a conversion from value to representation in a custom base:

>>> v2r(64,'01')
'1000000'
>>> v2r(64,'XY')
'YXXXXXX'
>>> v2r(12340,'ZABCDEFGHI') # decimal base with custom symbols
'ABCDZ'

To perform a conversion from representation (in a custom base) to value:

>>> r2v('100','01')
4
>>> r2v('100','0123456789') # standard decimal base
100
>>> r2v('100','01_whatevr') # decimal base with custom symbols
100
>>> r2v('100','0123456789ABCDEF') # standard hexadecimal base
256
>>> r2v('100','01_whatevr-jklmn') # hexadecimal base with custom symbols
256

To perform a base conversion from one custome base to another:

>>> b2b('1120','012','01')
'101010'
>>> b2b('100','01','0123456789')
'4'
>>> b2b('100','0123456789ABCDEF','01')
'100000000'
$\endgroup$
4
  • 4
    $\begingroup$ Welcome to the site and thanks for your contribution. However, producing well-optimized source code isn't what this site is really about. Andrej's code makes the concepts clear, which is what is needed for his answer, but improving the code beyond that is a matter of programming, rather than computer science. $\endgroup$ Nov 8, 2016 at 17:23
  • 2
    $\begingroup$ @DavidRicherby I partly agree, but this contribution was too long for a comment and its best place to be is somewhere near Andrej's answer, that's why I posted it here. Anyway if you think it's better I could convert it to a comment with a link to the code, but wouldn't it be an excess of purism? $\endgroup$
    – mmj
    Nov 8, 2016 at 17:33
  • 3
    $\begingroup$ Despite @David's "site-purist" objections, I found your answer a useful because it emphasizes the fact that that the bases involved can be thought of in more abstract terms as "alphabets" of arbitrary symbols of varying lengths — and not restricted to the usual range of 2-36 characters. You could in fact consider streams of bytes as the "digits" of base 256 integer values. $\endgroup$
    – martineau
    Jul 7, 2020 at 18:13
  • 2
    $\begingroup$ I was staring at the exact problem this solves today (an integer-keyed sharding context) and making zero progress because I couldn't reason about the problem space intuitively. For some reason being able to stare at a minimal working example of a solution helps me immensely in these kinds of situations, and this was incredibly helpful. $\endgroup$
    – i336_
    Jul 28, 2021 at 4:46
5
$\begingroup$

Fundamental operation of base convertion is the toDigits() operation of @AndrejBauer answer. However, to make it there is no need to create a number in the internal representation of the numbers, which is basically a conversion from and to base 2 representation. You can make the needed operations in the original base representation.

So the first step is to do repetitive modulo division operation

def convertBase(n,original_base,destination_base):
    digits = []    
    while not is_zero(n):
        digits.insert(0,modulo_div(n,original_base,destination_base))
    return digits

As the internal representation is digits, one has to make a specilaised function for testing zero

def is_zero(n):
    for d in n:
        if d != 0:
            return False
    return True

Eventually one has to make the modulo_div operation which is actually the standard division by destination base as we learnt at school.

def modulo_div(n,original_base,destination_base):
    carry = 0
    for i in range(len(n)):
        d = n[i]
        d+=original_base*carry 
        carry = d%destination_base 
        d=(d//destination_base)
        n[i] = d
        #print(i,d,carry)
    return carry

just a test check to verify the code is correct:

print(convertBase([1,1,2,0], 3, 2))
#[1, 0, 1, 0, 1, 0]

print(convertBase([1, 0, 1, 0, 1, 0], 2, 3))
#[1, 1, 2, 0]
$\endgroup$
6
  • 1
    $\begingroup$ Thanks for posting but please note that we're not a coding site, so a big block of code isn't appropriate as an answer here. Especially when the question explicitly says, "I don't need code I just need the basic math behind it." $\endgroup$ Dec 27, 2017 at 18:43
  • 1
    $\begingroup$ @DavidRicherby I tried to add text. $\endgroup$ Dec 27, 2017 at 18:59
  • $\begingroup$ Thanks. And I see there's a heck of a lot of code on this page, despite what I said! $\endgroup$ Dec 27, 2017 at 19:51
  • 1
    $\begingroup$ @David: FWIW, I think this answers the OP's question best as it shows how to convert between the two bases without first converting the representation of the original to some intermediate form, and then converting that to the destination base. $\endgroup$
    – martineau
    Jul 7, 2020 at 18:01
  • $\begingroup$ Nice try but d is still in base 10, so you are in effect extracting some smaller portion of n converting it to base 10, then converting that to the desired base and collecting those into the final result. $\endgroup$
    – Gregor y
    Sep 18, 2020 at 6:27
1
$\begingroup$

You can convert from base n to base 10 without any conversion to some intermediate base.

To convert from base n to base 9, for example, you take the algorithm for conversion to base 10, and replace “10” with “9”. Same for any other base.

$\endgroup$
0
$\begingroup$

I know an easy way to do base conversion that doesn't require a computer program. It's by defining a way to convert from any base to base 2 and vice versa and then coverting from one base to another base by first converting from the first base to base 2 then converting from base 2 to the other base. 2 is so easy to multiply or divide by in any base.

To convert from any base to base 2, all you have to do is recognize that for any number, if you take its base 2 notation and start from 0 and then for each digit in order from left to right double if that digit is zero and double than add 1 if that digit is 1, you get to that number itself. Now given that number in any base, you can divide by 2 in that base to get a quotient and remainder. If the remainder is 1, the last binary digit is 1 and if the remainder is 0, the last binary digit is 0. Divide by 2 again. If the remainder is 1, the second last digit is 1 and if the remainder is 0, the second last digit is 0 and so on until you get a quotient of 0.

To convert from base 2 to any base, all you have to do is in that base, start from 0, then for each binary digit going from left to right, double in that base if that digit is 0 and double then add 1 in that base if that digit is 1.

$\endgroup$
1
  • 1
    $\begingroup$ 2 is so easy to multiply or divide by in any base. I don't see that for odd bases that are more than one from any power of two (11 and 13, to start with). $\endgroup$
    – greybeard
    Aug 16, 2018 at 11:48
0
$\begingroup$

There is one not-so-useful special case:
Pairs of bases where each is a power of their GCD.

You can just consider symbol groups "the size of their LCM" and use a lookup table - recoding more than handling numbers.

$\endgroup$
2
  • $\begingroup$ Ex. octal ↔ hexagesimal. $\endgroup$
    – greybeard
    Aug 23, 2022 at 15:39
  • $\begingroup$ I don't see how this answers the question. The question asks how to convert "from any base to any base". $\endgroup$
    – D.W.
    Nov 8, 2022 at 21:56
0
$\begingroup$
    // Let's look at the number 11201 in base 3
    // which we will represent as (11201),3
    // 
    // (11201),3 = ( ),7
    //
    // 3^4 3^3 3^2 3^1 3^0
    //   1   1   2   0   1
    //
    // The "amount" of number we have in any given base
    // can be computed as per the following algorithm:
    //
    // begin_psuedocode
    // ans = 0;
    // ans = ( 1 * 3^4 ) + ans;
    // ans = ( 1 * 3^3 ) + ans;
    // ans = ( 2 * 3^2 ) + ans;
    // ans = ( 0 * 3^1 ) + ans;
    // ans = ( 1 * 3^0 ) + ans;
    // end_psuedocode
    //
    // or, otherwise stated:
    //
    // begin_pseudocode
    // ans = 1;
    // ans = ( ans * 3 ) + 1;
    // ans = ( ans * 3 ) + 2;
    // ans = ( ans * 3 ) + 0;
    // ans = ( ans * 3) + 1
    // end_pseudocode
    //
    // first step in converting to new base, is to
    // represent input number in input base, for this example, base 3
    // ((((1*10 + 1)10 + 2)10 + 0)10 + 1)
    //
    // since arithmetic works in any base
    // we simply convert each number to the new base
    // and our above equation will still hold true
    // the magic of aritmetic and math
    //
    // so the next step is to
    // map equation to the output base, for this example, base 7
    // ((((1*3 + 1)3 + 2)3 + 0)3 + 1)
    //
    // lastly, to determine the number in the new base,
    // we actually process each computation in the equation, in the new base
    //
    // ans = 1
    // ans = ans * 3 + 1 = (1*3) + 1 = 3 + 1 = 4
    // ans = ans * 3 + 2 = (4*3) + 2 = 15 + 2 = 20
    // ans = ans * 3 + 0 = (20*3) + 0 = 60 + 0 = 60
    // ans = ans * 3 + 1 = (60*3) + 1 = 240 + 1 = 241
    //
    // So finally, we have that
    // (11201),3 = (241),7

For full implementation of algorithm, see: https://github.com/primetimenumberline/BaseSwap/blob/master/Program.cs

Live demo over at: https://numbertheory-baseswap.netlify.app

Sample outputs:

https://i.sstatic.net/hytsi.png

https://i.sstatic.net/uL9Wr.png

https://i.sstatic.net/TRdst.png

$\endgroup$
0

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