Understanding Applied to Double Dabble

Understanding is a funny thing. Sometimes you can trick yourself into thinking you understand something you really don’t. But most times you kinda sorta know that you don’t fully understand it, and I’m just not really sure how that works.

In particular, there are two kinds of levels to "understanding." There’s that level where you – for lack of a better explanation – recognize that all the right "keywords" are associated with the thing that you would like to understand, and this allows you to talk about it intelligently, within certain limits. But the back of your mind knows you don’t really "get it."

Alternately, sometimes you really understand something, but find yourself at a loss for how to transmit the information to someone else. You can answer any question about the thing thrown at you – however unexpected – completely accurately, but you might not be able to teach someone else how to do the same.

And of course there are still more layers to this onion. I could go on like this all day – the point is that something happened recently that reminded me that I’d really like to know where that ineffable feeling that you UNDERSTAND something comes from.

I was reading a book on computer hardware and came across double dabble for like the 20th time in my existence. I’m talking about double dabble in its original meaning: that method you use to convert a decimal number into binary. (So, not the more recent use where it means converting a binary number into BCD.)

It works like this. Say we want to convert 243 into binary. Do the following:

  1. Divide by 2
  2. If there is a remainder, it’s 1 – prepend it to any other accumulated digits
  3. If there is no remainder, prepend a 0 to any other accumulated digits
  4. If the result of your division was greater than 0, queue that number and goto (1)

So, for 243:

  1. Divide by 2: 121 – remainder 1
  2. so, the accumulator is "1"
  3. Divide 121 by 2: 60, remainder 1
  4. so, the accumulator is "11"
  5. Divide 60 by 2: 30, remainder 0
  6. so, the accumulator is "011"
  7. Divide 30 by 2: 15, remainder 0
  8. so, the accumulator is "0011"
  9. Divide 15 by 2: 7, remainder 1
  10. so, the accumulator is "10011"
  11. Divide 7 by 2: 3, remainder 1
  12. so, the accumulator is "110011"
  13. Divide 3 by 2: 1, remainder 1
  14. so, the accumulator is "1110011"
  15. Divide 1 by 2: 0, remainder 1
  16. so, the accumulator is "11110011"
  17. STOP

Now, on hearing about this, it makes sense in the sense that I get all the keywords. All this dividing by 2 – I mean, it’s a binary number system, after all. But why do we keep dividing? And why prepend rather than append? I’m always initially at the level where double dabble doesn’t surprise me, and yet I don’t have that gut feeling of really "getting" it either.

I find it helps to do (the decimal equivalent of) double dabble on a decimal number – you know, convert decimal into decimal. Here, of course, the remainder can be anything from 1 to 9. But otherwise it works the same:

  1. Divide 243 by 10: 24, remainder 3
  2. so, the accumulator is "3"
  3. Divide 24 by 10: 2, remainder 4
  4. so, the accumulator is "43"
  5. Divide 2 by 10: 0, remainder 2
  6. so, the accumulator is "243"
  7. STOP

Unsurprisingly, it works. But something about going from decimal to decimal gets me over the gulf into real intuitive understanding.

NOW I think I get it.

243 is really just 240 plus 3.

243 is really just 240 – a number evenly divisible by 10 – plus 3.

243 is really just twenty four tens – a number evenly divisible by 10 (obviously) – plus 3.

We memoize the "3".

24 is really just 20 plus 4.

24 is really just two tens plus 4.

BUT, because we got "24" from there being "twenty four tens", the 2 here is really hundreds. That "4" that’s left over is "4 tens."

Which, you know, is what it is: 243. 243 is 2 hundreds plus 4 tens plus 3. When we’re dividing "tens," remainders are "ones." When we’re dividing "hundreds," remainders are "tens."

It’s all so transparent in decimal.

Which just sort of implies that the only reason that double dabble is initially non-intuitive is simple lack of experience. I’ve internalized decimal systems, but not binary systems. For binary systems, I have to reason it all out again when I pick it up again after a long absense because it’s just never something I’ve practiced to the point of it being second nature.

Which, when you get back to the opening point, rounds out the concept. That ineffable feeling we get of really understanding something is all down to familiarity. Which is why "real understanding" doesn’t imply "ability to communicate." Because something can be completely familiar without your being consciously aware of it.

In any case, it makes double dabble make sense. We divide 243 by 2 – after all, it’s a binary system, and in any number system shifting is division by the base. (243 divided by 10 is 24.3, after all.) So, if 243 is binary 11110011, then 243 divided by two is 1111001 … with a remainder of 1. And of course if we check, then 1111001 is indeed 121 in binary.

11110011 is …

1 one PLUS

1 two PLUS

1 sixteen PLUS

1 thrity-two PLUS

1 sixty-four PLUS

1 one-twenty-eight

Interestingly, there’s an easier way to do the reverse conversion which is just to … do the reverse conversion. Take the binary number from left to right and double each time, adding one where you have to. Or, in other words – words that make more sense – just go up my list of instructions from before rather than down. I mean, that’s what "undoing" something is, right? Doing it backward? Here’re those instructions again:

  1. Divide by 2: 121 – remainder 1
  2. so, the accumulator is "1"
  3. Divide 121 by 2: 60, remainder 1
  4. so, the accumulator is "11"
  5. Divide 60 by 2: 30, remainder 0
  6. so, the accumulator is "011"
  7. Divide 30 by 2: 15, remainder 0
  8. so, the accumulator is "0011"
  9. Divide 15 by 2: 7, remainder 1
  10. so, the accumulator is "10011"
  11. Divide 7 by 2: 3, remainder 1
  12. so, the accumulator is "110011"
  13. Divide 3 by 2: 1, remainder 1
  14. so, the accumulator is "1110011"
  15. Divide 1 by 2: 0, remainder 1
  16. so, the accumulator is "11110011"
  17. STOP

So basically, we need a mental process that goes "1, 3, 7, 15, 30, 60 121, 243." One based on "11110011." And since we know it’s just doing what we did before in reverse, it’s obvious what that process is:

  1. Starting at the left, add whatever’s in the current column to your accumulator (which starts at 0)
  2. Double what you have and move to the next column, if there is one. Otherwise, STOP.
  3. goto (1)

  4. 0 + 1 is 1
  5. (1 * 2) + 1 is 3
  6. (3 * 2) + 1 is 7
  7. (7 * 2) + 1 is 15
  8. (15 * 2) + 0 is 30
  9. (30 * 2) + 0 is 60
  10. (60 * 2) + 1 is 121
  11. (121 * 2) + 1 is 243

It makes perfect sense. It’s only not intuitive because it’s not familiar.

Notice that double dabble is a natural reduce case. That is, we’re taking a list of values ([1,1,1,1,0,0,1,1]), operating on each one, and accumulating the results of these operations into a single value. And each operation feeds the next. That’s a reduce if ever there was one! Which means double-dabble is a straightforward one-liner in Coffeescript(/Javascript):

double_dabble = (input) ->
  (parseInt(i) for i in input.split('')).reduce((a,i) -> a * 2 + i)

Let’s unpack it.

input is a string representation of our binary number: "11110011" in this case.

We need to turn that into a list (of columns), so we split input on the empty string: ['1','1','1','1','0','0','1','1']

Those are all still strings, and we need them to be ints, so, using a list comprehension, we call parseInt on each one: [1,1,1,1,0,0,1,1]

And that’s the list we call reduce on. Reduce, in Javascript (and so also in Coffeescript) is a method on Arrays that calls a function on each element in the array in order. The function takes two arguments: an accumulator and the individual element we’re operating on. Let’s call those a and i. Coffeescript allows anonymous (aka "lambda") functions, so we just write exactly what we mean: (a,i) -> a * 2 + i

Reduce calls that automatically on each element in the list. It’s also smart enough to use a default value – 0 in the case of int – for a on the first iteration. Though, if you wanted to be thorough you could’ve passed 0 in explicitly as a second argument to reduce, just after the function – i.e.:

(parseInt(i) for i in input.split('')).reduce(((a,i) -> a * 2 + i), 0)

And and actually, you could compact that further by doing away with the list comprehension altogether. input.split('') is already a list that we can call reduce on; we could do the int conversion on i directly:

double_dabble = (input) ->
  input.split('').reduce((a,i) -> a * 2 + parseInt(i))

But I personally think it’s more transparent the other way – when it’s organized into "generate list" and "operate on generated list" sections(halves).

Interestingly – what I assume is some kind of bug in the Javascript(/Coffeescript) interpreter – is that this doesn’t work:

double_dabble = (input) ->
  input.split('').map(parseInt).reduce((a,i) -> a * 2 + i)

That returns NaN for some reason. If I log it out, on my computer it’s the second '1' that fails to get parsed:

console.log input.split('').map(parseInt) # yields [ 1, NaN, 1, 1, 0, 0, 1, 1 ]

No idea why.

UPDATE – It’s not a Javascript "bug," it’s a "feature" of the way map gets called. StackOverflow has the goods.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>