English 字幕

← 01-09 Correctness: Naive


Showing Revision 1 created 06/27/2012 by Amara Bot.

  1. Let's go through and actually do a proof of the correctness
  2. of the naive algorithm we just spoke about.
  3. We're going to proceed by taking advantage of a particular observation.
  4. What we're trying to prove here is the correctness of the claim
  5. that naive(a,b) outputs the product of a and b.
  6. The observation that I'm going to make is that before or after the "while" loop
  7. in the implementation of naive, this statement is always true.
  8. The variables x and y multiply together and added to z
  9. is exactly equal to a times b. How are we going to show that this is the case?
  10. The first time we're going through the "while" loop in the very beginning
  11. and the top of the function, x is assigned to a, y is assigned to b, and z is assigned to 0.
  12. Let's check the expression with those variables plugged in.
  13. We're saying that's ab equals ab+0. Well, that's kind of obvious.
  14. Well, the next thing we're going to show is that if it's the case
  15. that at the beginning of the "while" loop, this condition holds that a times b
  16. is exactly equal to x times y plus z,
  17. then it's going to be the case that with the new values, so x, y, and z may change.
  18. The new values x prime, y prime, and z prime are going to satisfy this as well.
  19. If it was true before, then it has to be true after.
  20. Why would this be true? Let's remind ourselves what the code looks like again.
  21. What happens in each integration of the loop is that a new value of z is computed,
  22. which is the old value plus the value of y,
  23. and a new value of x is computed, which is the old value minus 1.
  24. We basically had the new value of x if the old value minus 1, the new value of y not been changed,
  25. and the new value of z is the old value of z plus y.
  26. All right! What can we say about x prime times y prime plus z prime?
  27. We know what x prime, y prime, and z prime are, so let's substitute those in.
  28. That's x minus 1 times y plus z plus y. Now we just do a little bit of algebra.
  29. Multiplying this out, we get xy minus y plus z plus y.
  30. and these y's, +y and -y cancel and so we get xy plus z.
  31. But, notice what we assumed--we say if it was the case the xy plus z is equal to ab,
  32. then what we're showing is that x prime, y prime plus z prime is equal to ab.
  33. Well guess what? We showed that x prime times y prime plus z prime does indeed equal ab
  34. if it was true at the top of the loop--so this condition that we're testing here
  35. this ab equals xy plus z is maintained through each step of the "while" loop.
  36. It starts out true but it remains true each time it goes through the "while" loop.
  37. What we know is that while this code is running each time we go through the "while" loop,
  38. this condition is always true and eventually, the "while" loop terminates.
  39. The "while" loop terminates when x equals 0, so what does that mean?
  40. The xy plus z has to equal ab, but x is 0, so that 0 times y plus z equals to ab. This has to be true.
  41. Well, 0 times y is 0, so this is actually saying that z has to be equal to ab at the end of the loop.
  42. Once x reaches 0, z has to equal ab. Keep in mind that's exactly what we return--the value of z.
  43. The thing that is returned is going to be a times b.
  44. Let's just take a look at the code again to see that that's what it's doing.
  45. Each time it goes through, it's decrementing x accumulating the values in z,
  46. and eventually when x is exhausted, it returns z and it is exactly a times b.