Placeholder Image

Subtitles section Play video

  • >> DAVID J MALAN: All right, so this is CS50.

  • And this is clearly a Friday.

  • And this is the end of week one.

  • So you may recall that we left off, last time, with a cliffhanger of sorts.

  • Whereby we expose this lie, that no matter what you've been taught growing

  • up, 1 divided by 10 is not, in fact, 0.1 or 0.100 or 0.10000.

  • In fact, if we compile this program, as we did yesterday, with,

  • make imprecision, and then do dot, slash, imprecision,

  • we learned that this is what's 1 divided by 10 actually is.

  • So that's not really quite the case.

  • But this does hint at some fundamental limitation of computers.

  • And indeed, among the things we're going to do

  • today is take a look at why this has happened, what implications this has,

  • how humanity has failed to grasp this in some very

  • serious situations-- the result of the which

  • has been quite tragic and expensive-- and also

  • take a look at how we can actually defend

  • against these kinds of limitations.

  • So intuitively, perhaps, why is 1 divided by 10,

  • according to my computer here, not just 1/10, 0.10?

  • Yeah.

  • What do you think?

  • >> AUDIENCE MEMBER: The radix is different?

  • >> DAVID J MALAN: The what is?

  • Oh, the radix is different?

  • So not quite.

  • It's actually more fundamental to the hardware.

  • Other thoughts?

  • Yeah.

  • AUDIENCE MEMBER: They represent numbers differently?

  • DAVID J MALAN: So they-- Right.

  • They represent numbers differently.

  • Inaccurately, apparently.

  • So that is-- Well, differently from what?

  • Or from whom?

  • From us?

  • AUDIENCE MEMBER: Yeah.

  • They don't use the decimal system to [INAUDIBLE].

  • DAVID J MALAN: OK.

  • So in a sense, they don't use the decimal system.

  • Underneath the hood, everything is, indeed, binary,

  • and that's related, in fact.

  • But it's even a simpler explanation than that.

  • Yeah.

  • >> AUDIENCE MEMBER: They only have so many bits.

  • They can only store up to a certain extent, like with the decimals.

  • >> DAVID J MALAN: Yeah.

  • This is what's really getting at it.

  • It turns out that computers typically, will always only

  • use a finite amount of information to represent something.

  • Right?

  • After all, we only have a fixed amount of hard disk space.

  • We only have a fixed amount of RAM, or computer memory.

  • And if you only have a fixed amount of something,

  • surely you can't actually count up to infinity or any number you want.

  • You, kind of, have to pick and choose what range

  • of values you're going to support.

  • >> And so for instance, a week or two ago, when we talked about ASCII,

  • and we talked about 8 bits, or a byte, so to speak,

  • the biggest number we could represent with 8 bits was what?

  • 255.

  • And we can represent 256 total values but not if we spend one of them

  • on 0-- Well, but if we spend one of them on 0,

  • then the biggest number is, of course, 255.

  • >> So it turns out, that this is the case too, in this context.

  • We started talking, last time, about floating-point numbers, which

  • are different from integers, in that they have a decimal point

  • and, hopefully, some numbers after that, but they are too.

  • A computer is only typically going to use 32 bits, maybe 64 bits

  • to represent a floating point value.

  • So even though we've grown up learning mathematics and knowing

  • that you can absolutely have an infinite number of numbers

  • after the decimal point, not if you have finite memory.

  • You, kind of, have to round, or pick and choose which

  • numbers you're going to represent.

  • And so you can think of, in a sense, this being the computer's closest

  • approximation to the value 1/10 that it can get, with just 32 or so bits.

  • And it's not just 1/10.

  • >> For instance, if I change this to 1/3, which we think is even simpler.

  • So 1 divided by 3.

  • Let me save the file.

  • Let me go ahead and recompile it.

  • And let me re-run it.

  • Here too, apparently, 1/3 is not 0.3 and then an infinite number of 3's

  • thereafter.

  • You have this imprecision at the end.

  • So we humans are correct, and what you learned is, in fact, correct,

  • but we're bumping up against some limitations.

  • >> And what I thought we'd do today, is begin

  • by looking at, frankly, the tragic consequences of this

  • sometimes, when mankind does not quite implement

  • for this reality and these limitations.

  • And we'll see a series of vignettes from the History Channel that takes

  • a look at how things have gone wrong.

  • It's about 8 minutes long, and we'll come back after this

  • and take a look at exactly what else can go wrong.

  • If we could dim the lights--

  • >> [VIDEO PLAYBACK]

  • >> -Computers, we've all come to accept the often frustrating problems that

  • go with them.

  • Bugs, viruses, and software glitches are small prices

  • to pay for the convenience.

  • But in high-tech and high-speed military and space program applications,

  • the smallest problem can be magnified into disaster.

  • On June 4, 1996, scientists prepared to launch an unmanned Ariane 5 rocket.

  • It was carrying scientific satellites designed

  • to establish precisely how the Earth's magnetic field interacts

  • with solar winds.

  • The rocket was built for the European Space Agency

  • and lifted off from its facility on the coast of French Guiana.

  • >> -And about 30 seconds into the flight, they first

  • noticed something was going wrong.

  • That the nozzles were swiveling in a way they really shouldn't.

  • Around 40 seconds into the flight, clearly the vehicle was in trouble,

  • and that's when they made the decision to destroy it.

  • A Range Safety Officer with tremendous guts pressed the button,

  • blew up the rocket before it could become a hazard to public safety.

  • >> -This was the maiden voyage of the Ariane 5,

  • and its destruction took place because of a flaw

  • embedded in the rocket's software.

  • -The problem on the Ariane was that there

  • was a number that required 64 bits to express,

  • and he wanted to convert it to a 16 bit number.

  • They assumed that the number was never going to be very big,

  • that most of those digits in the 64 bit number were 0's.

  • They were wrong.

  • >> -The inability of one software program to accept

  • the kind of number generated by another was at the root of the failure.

  • Software development had become a very costly part of new technology.

  • The Ariane 4 rocket had been very successful, so much of the software

  • created for it was also used on the Ariane 5.

  • >> -The basic problem was that the Ariane 5 was faster, accelerated faster.

  • And the software hadn't accounted for that.

  • >> -The destruction of the rocket was a huge financial disaster,

  • all due to a minute software error.

  • But this wasn't the first time data conversion problems

  • had plagued modern rocket technology.

  • >> -In 1991, with the start of the First Gulf War,

  • the Patriot missile experienced a similar kind

  • of number conversion problem.

  • As a result, 28 people, 28 American soldiers

  • were killed and about 100 others wounded,

  • when the Patriot, which was supposed to protect against incoming scuds,

  • failed to fire a missile.

  • >> -When Iraq invaded Kuwait and America launched Desert Storm in early 1991,

  • Patriot missile batteries were deployed to protect Saudi Arabia and Israel

  • from Iraqi Scud missile attacks.

  • The Patriot is a US, medium-range surface-to-air system

  • manufactured by the Raytheon company.

  • >> -The size of the Patriot interceptor, itself, is about, roughly 20 feet long.

  • And it weighs about 2000 pounds.

  • And it carries a warhead of about-- I think it's roughly 150 pounds.

  • And the warhead, itself, is a high explosive,

  • which has fragments around it.

  • The casing of the warhead is designed to act like buckshot.

  • >> -The missiles are carried, 4 per container,

  • and are transported by a semi-trailer.

  • >> -The Patriot anti missile system goes back at least 20 years now.

  • It was originally designed as an air defense missile

  • to shoot down enemy airplanes.

  • In the First Gulf War, when that war came along,

  • the Army wanted to use it to shoot down scuds, not airplanes.

  • The Iraqi Force was not so much of a problem,

  • but the Army was worried about scuds.

  • And so they tried to upgrade the Patriot.

  • >> -Intercepting an enemy missile traveling at mach five

  • was going to be challenging enough.

  • But when the Patriot was rushed into service,

  • the Army was not aware of an Iraqi modification that made

  • their scuds nearly impossible to hit.

  • >> -What happened, is the scuds that were coming in, were unstable,

  • they were wobbling.

  • The reason for this, was the Iraqis, in order

  • to get 600 kilometers out of a 300 kilometer range missile,

  • took weight out of the front warhead and made the warhead lighter.

  • So now, the Patriot's trying to come at the scud, and most of the time,

  • the overwhelming majority of the time, it would just fly by the scud.

  • >> -Once the Patriot system operators realized the Patriot missed its target,

  • they detonated the Patriot's warhead, to avoid possible casualties if it

  • was allowed to fall to the ground.

  • >> -That was what most people saw, those big fireballs in the sky,

  • and misunderstood as intercepts of Scud warheads.

  • Although in the night skies, Patriots appeared

  • to be successfully destroying scuds, at Dhahran,

  • there could be no mistake about its performance.

  • There, the Patriot's radar system lost track of an incoming Scud,

  • and never launched, due to a software flaw.

  • It was the Israelis who first discovered that the longer the system was on,

  • the greater the time discrepancy became, due to a clock embedded

  • in the system's computer.

  • >> -About 2 weeks before the tragedy in Dhahran,

  • the Israelis reported to the Defense Department,

  • that the system was losing time, that after about 8 hours of running,

  • they noticed that the system was becoming noticeably less accurate.

  • The Defense Department responded by telling all of the Patriot batteries

  • to not leave the systems on for a long time.

  • They never said what a long time was.

  • 8 hours?

  • 10 hours?

  • 1000 hours?

  • Nobody knew.

  • -The Patriot battery stationed at the barracks

  • at Dhahran, and its flawed internal clock, had been on over 100 hours

  • on the night of February 25.

  • >> -It tracked time to an accuracy of about 1/10 of a second.

  • Now 1/10 of a second is an interesting number

  • because it can't be expressed in binary, exactly.

  • Which means, it can't be expressed, exactly,

  • in any modern digital computer.

  • It's hard to believe, but use this as an example.

  • Let's take the number, 1/3.

  • 1/3 cannot be expressed in decimal, exactly.

  • 1/3 is 0.333 going on for infinity.

  • There's no way to do that, with absolute accuracy, in decimal.

  • That's exactly the same kind of problem that happened in the Patriot.

  • The longer the system ran, the worse the time error became.

  • >> -After 100 hours of operation, the error in time was only about 1/3 of a second.

  • But in terms of targeting a missile traveling at mach 5,

  • it resulted in a tracking error of over 600 meters.

  • It would be a fatal error for the soldiers at Dhahran.

  • >> -What happened, is a Scud launch was detected by early-warning satellites,

  • and they new that the Scud was coming in their general direction.

  • They didn't know where it was coming.

  • >> -It was now up to the radar component of the Patriot system,

  • defending Dhahran, to locate and keep track of the incoming enemy missile.

  • >> -The radar was very smart.

  • It would actually track the position of the Scud

  • and then predict where it probably would be,

  • the next time, the radar sent a pulse out.

  • That was called the range gate.

  • >> -Then, once the Patriot decides enough time has

  • passed to go back and check the next location for this detected object,

  • it goes back.

  • So when it went back to the wrong place, it then sees no object

  • and it decides that there was no object, it was a false detection,

  • and drops the track.

  • The incoming Scud disappeared from the radar screen,

  • and seconds later, it slammed into the barracks.

  • The Scud killed 28 and was the last one fired during the First Gulf War.

  • Tragically, the updated software arrived at Dhahran the following day.

  • The software flaw had been fixed, closing

  • one chapter in the troubled history of the Patriot missile.

  • >> [END PLAYBACK]

  • >> DAVID J MALAN: So we'll take a look at some similar limitations in just a bit.

  • But first, let's transition to a few FYI's.

  • So one-- this weekend, there will be super sections,

  • which are meant to supplant regularly scheduled sections, which

  • will start up a week hence.

  • Take a look at the CS50's website for more information on those.

  • They will also be filmed and streamed live for those unable to attend.