Welcome to Exploring Computing.
Today's video is Bits, Bytes, and Binary--
part 3-- or How to Destroy a Rocket with Only 16-Bits.
So in this video, we're going to take a look at what
happens when things go wrong.
I'm going to start off with a story about a rather expensive
error where the source of the error
was the programmers chose the wrong number of bits.
We're going to go back to the year 1996.
The European Space Agency has a new rocket, the Ariane 5,
which is, as you might guess, a follow-on to the Ariane 4.
Onboard this new Ariane 5 rocket are four satellites
worth $370 million.
The rocket launches.
3, 2, 1, fire.
[ROCKET ENGINE FIRING]
Things look like they're going well,
and then 37 seconds into the flight,
the rocket starts veering wildly off course.
It starts breaking apart, and ultimately it
has to be destroyed.
What went wrong?
What went wrong was, in one place,
the program controlling the rockets
tried to store information in 16 bits.
As you might recall, in 16 bits, we
can store numbers as large as 2 to the 16,
which means we can store numbers between 0 and 65,535.
And while this number was large enough
for the Ariane 4, the predecessor to the Ariane 5,
the Ariane 5 had performance characteristics
that caused it to run much faster,
and the value that it tried to stick into the 16-bit storage
location did not fit.
And when it tried to put the value into 16 bits, what
ended up happening is we had a condition called overflow.
What can happen in overflow is, we
can have a really large number and add 1 to it
and end up with 0.
Or we can have a large positive number, add 1 to it,
and actually end up with a large negative number.
So we're going to take a look at this phenomena in a minute.
This phenomena is also related to another famous problem,
which is the Y2K problem.
I know this is a little bit before some of your time.
So you may be thinking, yeah, my parents
might be interested in this lecture.
But what happened with the Y2K problem
is that programmers, starting in the '50s,
were trying to save space in their computer programs.
And so when they tried to store the year,
they didn't store the full year with all four digits.
Instead, they would store just two digits.
So here's a little table, for example.
So let's say the programmer was interested in storing the year
1952.
They would just store 52.
And then when that 52 got read from computer memory,
the computer would just know, oh, I need to add a 19 to it.
And so this would go on.
1984, just store an 84, '95, just store 95.
But the problem is, you can see here
is, when we start getting closer and closer to the year 2000,
the programmers realized they have a bit of a problem.
If they just store 00 and they do not fix their program,
the program is going to think that the year 00 represents
the year 1900, not the year 2000.
And so this was the Y2K problem.
And what ended up happening was, we
had to spend millions and millions of dollars rewriting
computer programs so that when the year 2000 hit,
the computers didn't think we were back in the 1900s.
All right, so let's take a look at how overflow actually works.
I'm going to show you two different versions of overflow.
In the first version of this, we're
going to take a look at what happens when we're
storing positive integers.
So I'm going to stick with 8-bit, although typically
these numbers will be much larger,
but it'll be easier to understand if we only
use 8 bit.
So in 8-bits, if I'm only storing positive numbers,
we can store the numbers from 0 to 255.
And so, suppose we have the number 255
stored in a particular storage location.
So here you can see I've got all my bits on.
This is the largest possible number I can store in 8 bits.
And then I try and add 1 to it.
What happens?
Well, the natural thing, if you recall our last video
on how to add in binary--
and who can forget that video--
what happened was, when we add a 1, we had that carryover,
and we had a carryover, and we had a carryover,
and we had a carryover, and it finally
carried over to the far left.
And you can see what happens is the ninth bit gets
flipped to 1.
But guess what?
We don't have nine bits.
We only have 8 bits, because this particular value is only
being stored in 8 bits.
So what happens is that that ninth bit gets discarded.
There's no space for it.
And what has happened is our very large value
consisting of all 1s has flipped to a very low value consisting
of all 0s.
So in terms of what's happening in for decimal,
we have a 255, which is the equivalent
of having all the bits in a particular byte switch to 1.
We have 255.
We've added 1 to 255, and we've actually ended up with 0.
So this is overflow.
So for our next example, we're going
to take a look at what happens when
we have a large positive number, but we're storing it
in a space that is allowed to store
both positive and negative numbers.
So in this particular case, again, I'm
just going to store all of our data
in single byte, which allows us to store
numbers between positive 127 and negative 128.
Now, there are a number of different ways
to store negative numbers on the computer.
The simplest way to store a negative number on the computer
is something called signed magnitude representation.
In signed magnitude representation,
what we're going to do is, we're going to take the high-end bit,
and we're going to go ahead and say if it's a 0,
we have a positive number, and if it's a 1,
we have a negative number.
So in the case of our single byte, the way this would work
is the seven low-end bits would go ahead and represent
our number, and then the eighth bit
would represent whether we had a positive number
or a negative number.
It turns out that this has a number of problems, though.
Most notably, it gives us both a positive 0 and a negative 0.
So if all the bits are 0, that's a regular 0.
And if all the bits are 0 except for the leftmost bit is 1,
that's a negative 0.
So that's kind of a problem.
So there are several other schemes used,
but the most common one is something
called two's complement.
I'm not going to go into detail on two's complement.
I think we've spent enough time on math for today.
But the key point on all of these schemes
is that leftmost bit is going to represent whether or not
we have a positive or negative number.
So what we're going to do now is we're
going to go ahead and take our largest positive number, which,
again, leftmost bit is 0.
That represents we have a positive number.
And all the other seven bits are 1.
This represents a positive 127.
We're going to go ahead and add 1 to it.
And you can see what happens here
is that leftmost bit flips to 1, and this means
we have a negative number.
And in fact, using the standard two's
complement representation, this is actually a negative 128.
So what has happened is, we've had a very
large positive number, 127.
We've added 1 to it.
We've got 128.
So this is again an example of overflow.
So when you're working with a computer program
or you're working with some sort of application
and you think everything's going great
and suddenly your bank account gets reset to zero
or your bank account, which was at a million dollars,
gets set to negative a million, what's probably happening here
is overflow.
This probably means whoever wrote the program did not
do a very good job.
OK, I've got one more type of error
I want to introduce to you.
And this is--
I suppose it's not actually technically an error.
What we're going to see here is that when
we're working with binary numbers,
our intuition on what results should come up
is not necessarily correct.
And so what I mean by that is, we're
going to add some numbers together,
and the results should be very, very obvious to us
when working with decimal.
But we'll see that the computer has some different ideas
on what the answer should be.
So what I'm running here is, this is the Python interpreter.
This is a way in which I can interactively enter commands
in the Python programming language.
This is the programming language that CS105 students
will be using a little bit later on in this quarter.
And so what I'm going to do is I'm
going to add some numbers here.
So let's ask the Python interpreter
to take 0.1 and add it to 0.2.
And what is 0.1 plus 0.2?
Well, naturally, it's 0.3.
Let's see if the Python interpreter agrees with us.
Whoa, what is this?
OK, let's try another one.
Let's ask the Python interpreter to add 0.7 to 0.1.
It seems pretty clear this should be 0.8, right?
OK, Python interpreter, let's see what you got.
What?
OK, so what is going on here is this computer just
completely messed up.
Now, what's actually going on here
is that numbers that we can represent in decimal in a set
number of decimal places is not the same base 10 and base 2.
So you may recall that there are certain numbers that we cannot
represent in a fixed number of decimal places.
So let's say I tell you to write the decimal equivalent of 2/3.
Well, what is the decimal equivalent of 2/3?
Well, you might say it's 0.67, but that's
not actually accurate.
I could say, no, 0.66667 is a more accurate representation,
and in fact, the correct representation
would be this, 0.6 repeating where this bar above the 6
represents a repeating decimal where
that 6 is repeated forever, and ever, and ever, and ever.
So the problem we're running into here
is that it turns out that the binary number has
different repeating numbers than the decimal number system.
In particular, the number 0.1 in base 10,
obviously, it's very finite.
0.1, there you go-- that's the answer.
It does not have a finite value in binary.
In binary, it's 0.0 and then 0011 repeating.
So, for example, 0.00011001100110011 and so on.
And there's no set number of--
there's no finite number of places after the decimal point.
So what's happening here is, we're
taking these numbers where we are
sure that there is a set number of decimal places,
like 0.7 plus 1.1, and we're getting a number that does not
have a natural endpoint, and so that's why
these numbers are slightly off.
As a result of this, programmers are
cautioned not to use floating point numbers when representing
money, because you will get these slight variations that
will cause your customer to be like, wait, what?
What is going on here?
All right, so there's obviously a lot more that
can go wrong with computing.
And in fact, we'll see some of it later in the quarter.
But for now, that's it for a little exploration
of what can go wrong when we're working with binary numbers.