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.