Converting to a base-n representation

Assume you want to represent a nonnegative integer with up to digits in binary. Recall that binary digits can represent any number in the range . This is the pseudo-code.

i = 1        # initialize the index
r = zeros(m) # all-zeros vector of length m
if x >= 2^m then throw("x is out of range")

while x > 0
  d = floor(x/2)
  r[i] = x mod 2
  x = d
  i = i+1
  
return reverse(r)  # so lowest value digit is rightmost

Let’s do it by hand for , using 4 digits (which can represent up to the value ).

13/2 = 6 rem 1 (d = 6, r[1] = 1)
6/2 = 3 rem 0
3/2 = 1 rem 1
1/2 = 0 rem 1

So we have 13 = 1101 in base-2, or (1*8) + (1*4) + (0*2) + (1*1).

For an unsigned trinary representation, the idea is the same, only you divide by 3 instead of 2. Let’s try it with 18, using 4 digits (which can represent up to the value , which is 80).

18/3 = 6 rem 0
6/3 = 2 rem 0
2/3 = 0 rem 2

So 18 = 0200 in base-3, or (0*27) + (2*9) + (0*3) + (0*1).

We can write a general function to convert a decimal number x to base-n representation.

# convert x to its unsigned base-n representation
# n: the base
# ndigits: the maximum number of digits
base_n = function(x, n, ndigits) {
  r = numeric(ndigits)
  if (x >= n ^ ndigits)
    stop("x is out of range")
  i = 1
  while (x > 0) {
    d = floor(x / n)
    r[i] = x %% n
    x = d
    i = i + 1
  }
  
  rev(r)
}

# convert from unsigned base-n back to decimal
to_decimal = function(r, n) {
  r = rev(r) # put the lowest digit to the leftmost
  ndigits = length(r)
  x = 0
  for (i in 1:ndigits)
    x = x + r[i] * n ^ (i - 1)
  
  x
}

# convert 13 to binary
r = base_n(13, 2, 4)
# confirm this is 13
stopifnot(to_decimal(r, 2) == 13)
r

[1] 1 1 0 1

# convert 18 to trinary
r = base_n(18, 3, 4)
# confirm this is 18
stopifnot(to_decimal(r, 3) == 18)
r

[1] 0 2 0 0

Converting to signed trinary

Recall that when solving the Four Weights problem, we established that any nonnegative integer value in the range 1:40 could be represented as

where the weights are (1, 3, 9, 27)—we write it smallest-first, consistently with the previous post on this problem—and , rather than the of unsigned trinary. A positive coefficient means the weight goes in the left pan, a negative coefficient means the weight goes in the right pan with , and 0 means the weight isn’t used.

The four digits still represent unique values, but some of them are now negative. For the Four Weights problem, we are only concerned with nonnegative , of which we can represent zero, plus values—the numbers 1:40. So we’ll concentrate on just expressing these nonnegative integers.

To modify the unsigned trinary conversion to a signed one, we use the observation that

• The equation x/3 = d rem 2 is equivalent to x/3 = (d+1) rem -1.

This is a bit of an abuse of the notation; but here’s an example of what we are trying to say. We know that

• 8/3 = 2 rem 2, which is the same as saying 8 = 2*3 + 2.

Another way of writing this is

• 8 = (2+1)*3 - 1 = 3*3 - 1 which we’ll write as: 8/3 = 3 rem -1

So (when considering only nonnegative ) the pseudo-code for the algorithm becomes:

i = 1
r = zeros(m)
maxval = (3^m - 1)/2
if x > maxval then throw("x is out of range")

while x > 0
  d = floor(x/3)
  r[i] = x mod 3
  if r[i]==2
    d = d+1
    r[i] = -1
  x = d
  i = i+1
  
return r  # we won't reverse it, to be consistent with our puzzle solution

Let’s convert 18 to signed trinary.

18/3 = 6 rem 0
6/3 = 2 rem 0
2/3 = 0 rem 2 = 1 rem -1
1/3 = 0 rem 1

So 18 codes to [0 0 -1 1] = (0*1) + (0*3) + (-1*9) + (1*27). In the scale notation that we used while solving the puzzle, we would write this as , meaning the 27-weight is in the left pan, and the 9-weight is in the right pan with .

Here’s the code.

# convert nonnegative x to signed trinary
weigh = function(x) {
  if (x > 40)
    stop("x out of range")
  r = numeric(4)
  i = 1
  while (x > 0) {
    d = floor(x / 3)
    r[i] = x %% 3
    if (r[i] == 2) {
      d = d + 1
      r[i] = -1
    }
    x = d
    i = i + 1
  }
  r
}

# write the signed trinary representation in our scale notation
scale_notation = function(signs) {
  w = c(1, 3, 9, 27)
  lefti = which(signs > 0)
  righti = which(signs < 0)
  
  leftset = paste(w[lefti], collapse = ", ")
  if (length(righti) > 0)
    rightset = paste("x,", paste(w[righti], collapse = ", "))
  else
    rightset = "x"
  
  notation = paste("[ {", leftset, "} | {", rightset, "} ]")
  notation
}

# convert signed trinary back to decimal
to_x = function(signs) {
  w = c(1, 3, 9, 27)
  x = sum(w * signs) # dot product of w and signs
}

Let’s try a few.

x = 18
signs = weigh(x)
# convert back and check it's the same number
stopifnot(x == to_x(signs))
scale_notation(signs)

[1] "[ { 27 } | { x, 9 } ]"

x = 35
signs = weigh(x)
stopifnot(x == to_x(signs))
scale_notation(signs)

[1] "[ { 9, 27 } | { x, 1 } ]"

x = 15
signs = weigh(x)
stopifnot(x == to_x(signs))
scale_notation(signs)

[1] "[ { 27 } | { x, 3, 9 } ]"

x = 30
signs = weigh(x)
stopifnot(x == to_x(signs))
scale_notation(signs)

[1] "[ { 3, 27 } | { x } ]"

x = 4
signs = weigh(x)
stopifnot(x == to_x(signs))
scale_notation(signs)

[1] "[ { 1, 3 } | { x } ]"

So now we can weigh objects we know the weight of. Hurrah? But I still think it’s cute.

Nina Zumel is a data scientist based in San Francisco, with 20+ years of experience in machine learning, statistics, and analytics. She is the co-founder of the data science consulting firm Win-Vector LLC, and (with John Mount) the co-author of Practical Data Science with R, now in its second edition.