I wrote a short function in python that should be fairly fast. Given number n and base b, it converts n in just O(log n) rounds. Here is the first version:
from math import log
def chbase(n, b):
if n < 1:
return 0
cols = []
power = int(log(n, b))
while power >= 0:
count = int(n / (b**power))
n -= count * b**power
power -= 1
cols += [count]
return cols
For example, calling
chbase(12, 3) would produce
[1, 1, 0] since 12 is 1*9 + 1*3 + 0*1. However, this is in
big endian representation of the number. This is useful for humans to look at but is not the only way to represent the number. The problem with this representation is that code that tries to use this list of columns has to know the length of the list before it can be used. In the following code, the
little endian list is produced. Changes to the code are in bold:
from math import log
def chbase(n, b):
if n < 1:
return 0
cols = []
power = int(log(n, b))
while power >= 0:
count = int(n / (b**power))
n -= count * b**power
power -= 1
cols = [count] + cols
return cols
Calling
chbase(12, 3) would produce
[0, 1, 1] since 12 is0*1 + 1*3 + 1*9.
To convert the number back into its original form you would use the following:
def revbase(cols, b):
power = 0
total = 0
for each in cols:
total += each * b ** power
power += 1
return total
To use it, pass the columns as the first parameter and the base as the second:
revbase([0,1,1], 3) and the result is 12. In fact this would even work:
revbase( chbase( 12, 3), 3) since it too would return 12.