# Arbitrary Base Conversion [closed]

Create a routine that takes an array of blocks in one numeric base system, and convert them to an array of blocks in another numeric base system. Both the from and to systems are arbitrary and should be accepted as a parameter. The input array can be an arbitrary length (If using a language where array lengths are not stored with the array, such as C, a length parameter should be passed to the function).

Here's how it should work:

fromArray = [1, 1]
fromBase = 256
toBase = 16
result = convertBase(fromArray, fromBase, toBase);


Which should return [0, 1, 0, 1] or possibly [1, 0, 1] (leading 0s are optional since they don't change the value of the answer).

Here are some test vectors:

1. Identity Test Vector

fromArray = [1, 2, 3, 4]
fromBase = 16
toBase = 16
result = [1, 2, 3, 4]

2. Trivial Test Vector

fromArray = [1, 0]
fromBase = 10
toBase = 100
result = [10]

3. Big Test Vector

fromArray = [41, 15, 156, 123, 254, 156, 141, 2, 24]
fromBase = 256
toBase = 16
result = [2, 9, 0, 15, 9, 12, 7, 11, 15, 14, 9, 12, 8, 13, 0, 2, 1, 8]

4. Really Big Test Vector

fromArray = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
fromBase = 2
toBase = 10
result = [1, 2, 3, 7, 9, 4, 0, 0, 3, 9, 2, 8, 5, 3, 8, 0, 2, 7, 4, 8, 9, 9, 1, 2, 4, 2, 2, 3]

5. Non-even Base Vector

fromArray = [41, 42, 43]
fromBase = 256
toBase = 36
result = [1, 21, 29, 22, 3]


Other criteria / rules:

1. All integer variables should fit within a standard 32 bit signed integer for all sane input ranges.

2. You may convert to an intermediary representation, as long as the intermediary is nothing more than an array of 32 bit signed integers.

3. Expect to handle bases from 2 through 256. There isn't any need to support higher bases than that (but if you would like to, by all means).

4. Expect to handle input and output sizes at least up to 1000 elements. A solution that scales to 2^32-1 elements would be better, but 1000 is just fine.

5. This isn't necessarily about having the shortest code that will meet these rules. It's about having the cleanest and most elegant code.

Now, this isn't exactly trivial to do, so an answer that almost works might be accepted!

• Does #1 mean we can't use a bigint type? Mar 14, 2011 at 21:51
• @Keith: Correct. Only 32 bit integers. Mar 14, 2011 at 22:01
• You say "signed integer" but the examples are only for positive integers, so: do we have to handle negatives? Mar 15, 2011 at 15:04
• @Eelvex: I don't see a need to handle negatives. If a negative is handled, it would be outside of the converter. Mar 15, 2011 at 17:20
• Are they always integer bases? Apr 24, 2011 at 1:01

# Python

# divides longnum src (in base src_base) by divisor
# returns a pair of (longnum dividend, remainder)
def divmod_long(src, src_base, divisor):
dividend=[]
remainder=0
for d in src:
(e, remainder) = divmod(d + remainder * src_base, divisor)
if dividend or e: dividend += [e]
return (dividend, remainder)

def convert(src, src_base, dst_base):
result = []
while src:
(src, remainder) = divmod_long(src, src_base, dst_base)
result = [remainder] + result
return result

• Thank you. I was looking for a routine like this. It took me a while to convert it to Javascript though. I'll probably golf it a little and post here for the fun of it. Mar 16, 2011 at 21:06

import Data.List

type Numeral = (Int, [Int])

swap              ::  (a,b) -> (b,a)
swap (x,y)        =   (y,x)

unfoldl           ::  (b -> Maybe (b,a)) -> b -> [a]
unfoldl f         =   reverse . unfoldr (fmap swap . f)

normalize         ::  Numeral -> Numeral
normalize (r,ds)  =   (r, dropWhile (==0) ds)

divModLongInt            ::  Numeral -> Int -> (Numeral,Int)
divModLongInt (r,dd) dv  =   let  divDigit c d = swap ((c*r+d) divMod dv)
(remainder, quotient) = mapAccumR divDigit 0 (reverse dd)
in   (normalize (r,reverse quotient), remainder)

changeRadixLongInt       ::  Numeral -> Int -> Numeral
changeRadixLongInt n r'  =   (r', unfoldl produceDigit n)
where  produceDigit  (_,[])   =  Nothing
produceDigit  x        =  Just (divModLongInt x r')

changeRadix :: [Int] -> Int -> Int -> [Int]
changeRadix digits origBase newBase = snd $changeRadixLongInt (origBase,digits) newBase doLine line = let [(digits,rest0)] = reads line [(origBase,rest1)] = reads rest0 [(newBase,rest2)] = reads rest1 in show$ changeRadix digits origBase newBase

main = interact (unlines . map doLine . lines)


And running the tests from the question:

$./a.out [1,2,3,4] 16 16 [1,2,3,4] [1,0] 10 100 [10] [41, 15, 156, 123, 254, 156, 141, 2, 24] 256 16 [2,9,0,15,9,12,7,11,15,14,9,12,8,13,0,2,1,8] [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] 2 10 [1,2,3,7,9,4,0,0,3,9,2,8,5,3,8,0,2,7,4,8,9,9,1,2,4,2,2,3] [41, 42, 43] 256 36 [1,21,29,22,3]  • Oh wow. That's awesome! Now, if only I could understand it :-)... (but that's my task now)... Mar 14, 2011 at 20:45 ## R Handles many thousands of elements* in less than a minute. addb <- function(v1,v2,b) { ml <- max(length(v1),length(v2)) v1 <- c(rep(0, ml-length(v1)),v1) v2 <- c(rep(0, ml-length(v2)),v2) v1 = v1 + v2 resm = v1%%b resd = c(floor(v1/b),0) while (any(resd != 0)) { v1 = c(0,resm) + resd resm = v1%%b resd = c(floor(v1/b),0) } while (v1[1] == 0) v1 = v1[-1] return(v1) } redb <- function(v,b) { return (addb(v,0,b)) } mm = rbind(1) mulmat <- function(fromb, tob, n) { if (dim(mm)[2] >= n) return(mm) if (n == 1) return(1) newr = addb(mulmat(fromb,tob,n-1) %*% rep(fromb-1,n-1), 1, tob) newm = mulmat(fromb,tob,n-1) while (is.null(dim(newm)) || dim(newm)[1] < length(newr)) newm = rbind(0,newm) mm <<- cbind(newr, newm) return(mm) } dothelocomotion <- function(fromBase, toBase, v) { mm <<- rbind(1) return(redb(mulmat(fromBase, toBase, length(v)) %*% v, toBase)) }  * for >500 elements you have to raise the default recursion level or do not reset the mm matrix on dothelocomotion() Examples: v1 = c(41, 15, 156, 123, 254, 156, 141, 2, 24) dothelocomotion(256,16,v1) 2 9 0 15 9 12 7 11 15 14 9 12 8 13 0 2 1 8 dothelocomotion(256,36,c(41,42,43)) 1 21 29 22 3 dothelocomotion(2,10, rep(1,90)) 1 2 3 7 9 4 0 0 3 9 2 8 5 3 8 0 2 7 4 8 9 9 1 2 4 2 2 3  A less obfuscated and quicker JavaScript version: function convert (number, src_base, dst_base) { var res = []; var quotient; var remainder; while (number.length) { // divide successive powers of dst_base quotient = []; remainder = 0; var len = number.length; for (var i = 0 ; i != len ; i++) { var accumulator = number[i] + remainder * src_base; var digit = accumulator / dst_base | 0; // rounding faster than Math.floor remainder = accumulator % dst_base; if (quotient.length || digit) quotient.push(digit); } // the remainder of current division is the next rightmost digit res.unshift(remainder); // rinse and repeat with next power of dst_base number = quotient; } return res; }  Computation time grows as o(number of digits2). Not very efficient for large numbers. Specialized versions line base64 encoding take advantage of base ratios to speed up the computations. • doing god's work son – bryc Dec 13, 2018 at 7:36 # Javascript Thank you Keith Randall for your Python answer. I was struggling with the minutiae of my solution and ended up copying your logic. If anyone is awarding a vote to this solution because it works then please also give a vote to Keith's solution. function convert(src,fb,tb){ var res=[] while(src.length > 0){ var a=(function(src){ var d=[];var rem=0 for each (var i in src){ var c=i+rem*fb var e=Math.floor(c/tb) rem=c%tb d.length||e?d.push(e):0 } return[d,rem] }).call(this,src) src=a[0] var rem=a[1] res.unshift(rem) } return res }  ### Tests console.log(convert([1, 2, 3, 4], 16, 16)) console.log(convert([1, 0], 10, 100)) console.log(convert([41, 15, 156, 123, 254, 156, 141, 2, 24], 256, 16)) console.log(convert([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], 2, 10)) console.log(convert([41, 42, 43], 256, 36)) /* Produces: [1, 2, 3, 4] [10] [2, 9, 0, 15, 9, 12, 7, 11, 15, 14, 9, 12, 8, 13, 0, 2, 1, 8] [1, 2, 3, 7, 9, 4, 0, 0, 3, 9, 2, 8, 5, 3, 8, 0, 2, 7, 4, 8, 9, 9, 1, 2, 4, 2, 2, 3] [1, 21, 29, 22, 3] */  This could probably be shrunk a lot, but I actually want to use it for a little side project. So I have kept it readable (somewhat) and tried to keep variables in check. • how is it javascript? for each? Feb 10, 2014 at 18:29 • No variable names above 3 characters, deprecated for each statement and eye-watering constructs like d.length||e?d.push(e):0... Is this an obfuscated code challenge or something? You could write the same thing with an understandable syntax and better performances. – user16991 Feb 21, 2014 at 16:12 • @kuroineko This is code golf. What were you expecting? Clean, readable code using up-to-date standards? I never claimed my answer was perfect and I would certainly not use it as is in a production project. Feb 21, 2014 at 17:07 • Well I actually needed this algorithm in JavaScript for some reason, and I had to rewrite it from scratch, taking the python solution as a base. I appreciate your contribution, but for practical purposes it was hardly useable at all IMHO. – user16991 Feb 21, 2014 at 17:20 ## Mathematica No variables defined, any input accepted as long as it fits in memory. f[i_, sb_, db_] := IntegerDigits[FromDigits[i, sb], db];  Test drive: f[{1,2,3,4},16,16] f[{1,0},10,100] f[{41,15,156,123,254,156,141,2,24},256,16] f[{1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1},2,10] f[{41,42,43},256,36]  Out {1,2,3,4} {10} {2,9,0,15,9,12,7,11,15,14,9,12,8,13,0,2,1,8} {1,2,3 7,9,4,0,0,3,9,2,8,5,3,8,0,2,7,4,8,9,9,1,2,4,2,2,3} {1,21,29,22,3}  ### Scala: def toDecimal (li: List[Int], base: Int) : BigInt = li match { case Nil => BigInt (0) case x :: xs => BigInt (x % base) + (BigInt (base) * toDecimal (xs, base)) } def fromDecimal (dec: BigInt, base: Int) : List[Int] = if (dec==0L) Nil else (dec % base).toInt :: fromDecimal (dec/base, base) def x2y (value: List[Int], from: Int, to: Int) = fromDecimal (toDecimal (value.reverse, from), to).reverse  Testcode with tests: def test (li: List[Int], from: Int, to: Int, s: String) = { val erg= "" + x2y (li, from, to) if (! erg.equals (s)) println ("2dec: " + toDecimal (li, from) + "\n\terg: " + erg + "\n\texp: " + s) } test (List (1, 2, 3, 4), 16, 16, "List(1, 2, 3, 4)") test (List (1, 0), 10, 100, "List(10)") test (List (41, 15, 156, 123, 254, 156, 141, 2, 24), 256, 16, "List(2, 9, 0, 15, 9, 12, 7, 11, 15, 14, 9, 12, 8, 13, 0, 2, 1, 8)") test (List (1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1), 2, 10, "List(1, 2, 3, 7, 9, 4, 0, 0, 3, 9, 2, 8, 5, 3, 8, 0, 2, 7, 4, 8, 9, 9, 1, 2, 4, 2, 2, 3)") test (List (41, 42, 43), 256, 36, "List(1, 21, 29, 22, 3)")  Passed all tests. # J, 109 105 Handles thousands of digits no sweat. No integers harmed! e=:<.@%,.|~ t=:]}.@.(0={.)@((e{:)~h=:+//.@)^:_ s=:[t[:+/;.0]*|.@>@(4 :'x((];~[t((*/e/)~>@{.)h)^:(<:#y))1')  ### Examples 256 16 s 41 15 156 123 254 156 141 2 24 2 9 0 15 9 12 7 11 15 14 9 12 8 13 0 2 1 8 256 36 s 41 42 43 1 21 29 22 3 16 16 s 1 2 3 4 1 2 3 4 256 46 s ?.1000$45
14 0 4 23 42 7 11 30 37 10 28 44 ...

time'256 46 s ?.3000\$45'  NB. Timing conversion of 3000-vector.
1.96s


It gets shorter.

# Smalltalk, 128

o:=[:n :b|n>b ifTrue:[(o value:n//b value:b),{n\\b}]ifFalse:[{n}]].
f:=[:a :f :t|o value:(a inject:0into:[:s :d|s*f+d])value:t].


tests:

f value:#[41 15 156 123 254 156 141 2 24]
value:256
value:16.
-> #(2 9 0 15 9 12 7 11 15 14 9 12 8 13 0 2 1 8)

f value:#[1 2 3 4]
value:16
value:16.
-> #(1 2 3 4)

f value:#[1 0]
value:10
value:100.
-> #(10)

f value:#[1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1]
value:2
value:10.
-> #(1 2 3 7 9 4 0 0 3 9 2 8 5 3 8 0 2 7 4 8 9 9 1 2 4 2 2 3)

f value:#[41 42 43]
value:256
value:36.
-> #(1 21 29 22 3)


and for your special amusement (challenge: figure out, what's so special about the input value):

f value:#[3 193 88 29 73 27 40 245 35 194 58 189 243 91 104 156 144 128 0 0 0 0]
value:256
value:1000.
-> #(1 405 6 117 752 879 898 543 142 606 244 511 569 936 384 0 0 0)
`