Get a number from an array of digits

Question

To split a number into digits in a given base, Julia has the digits() function:

julia> digits(36, base = 4)
3-element Array{Int64,1}:
 0
 1
 2

What's the reverse operation? If you have an array of digits and the base, is there a built-in way to convert that to a number? I could print the array to a string and use parse(), but that sounds inefficient, and also wouldn't work for bases > 10.

Answer 1

The answer seems to be written directly within the documentation of digits:

help?> digits
search: digits digits! ndigits isdigit isxdigit disable_sigint

  digits([T<:Integer], n::Integer; base::T = 10, pad::Integer = 1)

  Return an array with element type T (default Int) of the digits of n in the given base,
  optionally padded with zeros to a specified size. More significant digits are at higher
  indices, such that n == sum([digits[k]*base^(k-1) for k=1:length(digits)]).

So for your case this will work:

julia> d = digits(36, base = 4);

julia> sum([d[k]*4^(k-1) for k=1:length(d)])
36

And the above code can be shortened with the dot operator:

julia> sum(d.*4 .^(0:(length(d)-1)))
36

Answer 2

The previous answers are correct, but there is also the matter of efficiency:

sum([x[k]*base^(k-1) for k=1:length(x)])

collects the numbers into an array before summing, which causes unnecessary allocations. Skip the brackets to get better performance:

sum(x[k]*base^(k-1) for k in 1:length(x))

This also allocates an array before summing: sum(d.*4 .^(0:(length(d)-1)))

If you really want good performance, though, write a loop and avoid repeated exponentiation:

function undigit(d; base=10)
    s = zero(eltype(d))
    mult = one(eltype(d))
    for val in d
        s += val * mult
        mult *= base
    end
    return s
end

This has one extra unnecessary multiplication, you could try to figure out some way of skipping that. But the performance is 10-15x better than the other approaches in my tests, and has zero allocations.

Edit: There's actually a slight risk to the type handling above. If the input vector and base have different integer types, you can get a type instability. This code should behave better:

function undigits(d; base=10)
    (s, b) = promote(zero(eltype(d)), base)
    mult = one(s)
    for val in d
        s += val * mult
        mult *= b
    end
    return s
end