In some ways there are some awkward incompatibilities between the decimal
that we like to use and the binary which is so efficient and wonderful for computers
to use. We've seen one example of this already. I think I mentioned in a
previous video that .1, or .10, (ten cents in otrher words) in decimal, in your current bank balance is
not exactly representable as a binary number. You look at what it is in binary
0.00011001100 It just isn't, you know. It keeps on
recurring. Just as 1/3 in decimal isn't exact. It goes .333333 for ever.
Decimal and binary sometimes don't mix. Now here's going
to be a classic example. Let's just think this through, without even writing
anything down. if we've got a 4-bit nibble,
we know that in hex it goes from 0000 to 1111, 15 represented as F [hex]. We can't use
our full range [for BCD]. This is binary-coded decimal not binary-coded hexadecimal.
Yeah?! We have got to say that the moment that representation, even in one nibble,
gets to 1010 that is 10 [decimal] you can't leave it as 1010 you've now got have
2 nibbles. The left nibble with a 1 in it and the right nibble wants to look like 0.
You can't compress it into a single nibble, say 1010 and say: "I'm sorry folks
you'll have to learn hex, because otherwise you won't understand your bank
balance!" This is not going to go down very well. The challenge then is, if you're
using a 4-bit nibble, but only for the decimal range 0-9, you've somehow
got to make - in all your bit twiddles - you've got to make it carry into another
nibble on the left at 10[decimal] and not at 16 [decimal], which is what hexadecimal will do for you.
So, how does one, sort of, bridge that gap? Probably the best way for me to get
in to the hard bit about this is [to] go straight away for that magic
number 10. Let's represent it in binary and then say: "How do we convert it into
BCD?" And realize that we need that second nibble on the left. What I'd like to do
here is to draw myself columns, and I'm going to restrict myself to things that
are, at most, 2 decimal digits. Let's remind ourselves, up here, that we're
going to have a tens nibble and a units nibble, and we'll initialize everything
to zeros. But, above here, just to keep things very simple,
we'll use 4-bit binary representations. And I hope you will all agree that 1010
is ten, in base ten. And the reason for that is that the binary - in
four bits - that's an 8, that's the 2, so that's 10. This technique which is
called Double Dabble - I don't know how it was discovered, it's fiendishly clever -
but the idea is we'd love to convert binary into BCD by, as far as possible,
using simple bit shifts all the time and doing the minimum of mucking about to
get it to carry early. So the 'Double' reflects the fact that we're going to shift
this bit-pattern across into here. And we're going to regard it as one
huge, great big, 12-bit register here. A walloping great shift register - all joined together.
Even though I've drawn it out separately. It's just going to move from
the right across to the left. I'm going to move them across. And remember, every time you
shift the thing by one place left you are basically doubling it. OK,
that's where the 'Double' comes from. But we find we have to intervene to make it
look right at the end and that is where the 'Dabble' comes from. If you look up
'dabble', as I did in Chambers' dictionary it's one of the meanings is " ... to make a
trivial alteration to". OK to make a small alteration to something you're 'dabbling'
with it. OK, so that's where Double Dabble comes. OK, so it's basically
doubling, with a little bit of dabbling. And the truth really hits you at 10. So,
let's progressively shift this by 1 bit left. What's going to
happen first of all? You shift over that '1' bit
You push it across into here because this is a unified register, for the moment.
Prists will say: "Ah! but when you shift left, like that, you should fill in with
zeros on the right." Yes, that is what will actually happen, inside the hardware,
But I prefer not to pad with zeros, on the right, at a shift, because I want you
to see when I've finished. So, we could call this shift no. 1. Let's do another
one. That 1 moves into that position but you're bringing over another 0
out of that part and that's leaving you with 10 in there. Now, notice what's
happened. On shift 1, here, you had a 1 on the right, in that nibble. By the time
you've shifted it left one place it's in the 2s position.
So, you've doubled it. Let's do shift no. 3 and a zero is left, So, that is
shift 3. Now, this is where we can begin to see trouble on the horizon.
We have got one more shift left to do and, if you don't do anything about it, it's
just going to end up with 1010 in here. I mean, all right, what's
happened here, look, is that was 2 - you doubled it, but because you shifted a
1 in, and not a 0, you've doubled it and added 1. That now says 5, OK?
So, basically it's doubling but sometimes if the bit you shift over is 1, and
not a 0, it's double and add 1. But essentially it's doubling. Now the
trouble is coming on the horizon because I can see that if I just push that 0
bit over here, I'm going to end up with 1010. I know, it's 10 [decimal]. Fine!
It's not representable as a digit from 0-9. So, what should you do
then? Let it happen anyway and then look at it and say: "Oh my golly, it's gone to
ten; it's gone to eleven; it's gone to fifteen even! I'd better backtrack and undo
it and then redo it ?!" No! Dive in early and reason as follows:
Concentrate everybody! OK, what we want here
is for this thing to come out looking like 0001 0000.
Let's say that's the "desired result".
Because that - regarding these as BCD digits -
that's 1 0 i.e. ten. That's exactly what you want. So how do we make that happen?
How do we make it carry over into this left-hand nibble, here, when it doesn't
want to at the moment. So the fiendishly clever thing says: "Take a look at what
you've currently got because if what you got is 5 or more, the act of doubling
it is bound to get you into a number that needs to carry across [tothe next BCD nibble]. So, if it is
going to cause you trouble, at 5 or more, we wanted to carry at 10 [decimal], it
innately would like to carry at 16 and you don't want that. What's the
difference, Sean, between 10 and 16? >> Sean: 6 >> DFB: 6. what's half of that? >> Sean: 3
>> DFB: All right. So, if we add three the fact that we're then shifting it will double our 3
contribution [to] 6, And we'll make it carry [because we'll force that nibble past 16] So, the rule is - on Double Dabble - if
what you see in your nibble [before shifting] is 5 or more, then add 3. So, here we go, look.
Next stage now. Because we've seen trouble on the horizon. It's 5, so add
3. And 3, we agree, is 11 [binary]. Now, here you do have to do a little
addition with carries. You can't avoid it. Some carries will
have to take place. 1 and 1 is 0 (carry 1); 1 and 1 is 0(carry 1);
1 and 1 is 0 (carry 1). The act of adding 3 will make it look not like
0101 - you've added the 3, it now looks like 1000.
Magic! But, what happens when you shift the final 0 in? That 1 will shift
left, into the left-hand nibble. And you'll end up with:
0001 0000. And this thing is now empty. So you know you've come to the
end of your conversion. It's so cool. I love it dearly.
You could argue though, the one problem with all this is that, in order to do
your shifts quickly, you've got this [bit pattern] in a sort of a unified shift register
full of bits. Your nibbles - in the end - end up looking correct. But you're going to have
to dig them out of the shift register. "Oh yeah! ... that's clearly a 4, yes, that's a 2 isn't it?!"
Magic! Of course, if you're using this seriously you have to try and
generate these BCD digits in a way where they don't necessarily need digging out
of a bigger representation - but on the other hand you're using that behind the scenes.
I've found, for you, the ultimate reference [that] I've taken this example from,
and used the methodology. It's by a guy called Chuck Falconer. It's actually
referred to in the Wikipedia articles on BCD and Double Dabble, So, we've pulled
that over. It's freely available. You can go and dive in there to your heart's
content, because he covers about how to make them [the nibbles] appear in a much more useable
way. And what he also says is that when you start looking at this, you realize
you are actually doing the "division by ten and remainders" thing that we
discussed earlie. But you're doing it in a pretty efficient way [mainly bitshifts] and only
occasionally needing that little addition of 3. So that's ... I'm not
saying there aren't other ways. There seems to be endless variants on this:
there's signed BCD; there's packed BCD; there's all sorts. But if you just want
to understand the fundamentals I would say go through the [EXTRA BITS video] 42 example. T then go to
Chuck Falconers memo. And he does 255, as decimal, and boy that needs
spotting problems in about three sets of nibbles - not two. You have to spot one in
the middle thing happening and so on. >> Sean: You mentioned 255, so this goes
up to hundreds, thousand ... you just add more ... ? >> DFB: Yes, you just add more BCD digits on the
left to cope. But you give yourself a bigger problem when examining each of these
[nibble] digits to see if they're about to go beyond ten, when they're doubled,
by shifting left left one more time. You give yourself a bigger and bigger inspection
task, there's no question. So, like I say the Chuck Falconer memo from
which this is derived ... we'll put a link out to it. It is freely available.
He doesn't explain how the people who invented this actually discovered it,
worked out that it really does work. It seems almost like magic when you do it.
And every so often I pull out another number and I think: "I bet it won't work for this".
But it does. It's quitey incredible. So, there we are then. I think we've fairly
well summarized now what the situation is - that for great big engineering,
scientific calculations - even for finding new prime numbers as huge integers - you
really do need proper binary to speed things up. But for some sorts of trivial
calculations, you might even want to do it in BCD all the time. But even if you
are basically binary and want to print out your answers, you still have to convert
from binary through to BCD. And that is always a worry for the people who
write the I/O routines, shall we say for C and so on. Is this going to be
efficient? What we're saying is, at the computing end of things, you should be
able to prepare that BCD-digit stream as quickly as possible.