English 字幕

← 01-28 Divide And Conquer


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

  1. We're taking a moment to try to understand what it is about the way that the Russian algorithm
  2. is designed that makes it so much better than the naive approach that is just repetitive addition.
  3. Let's just go back for a moment to what multiplication is--at least integer multiplication.
  4. It is repeated addition, a times b. Let's focus for the moment on the case where a is even.
  5. Can be written as b plus b plus b plus b, repeated 8 times.
  6. We're considering the case were a is even here--we can regroup them as 2 sums.
  7. B added to itself a over 2 times, and then b added to itself a over 2 times again,
  8. and those 2 things added together, but it's silly to compute the same thing twice.
  9. Clearly if we're doing this calculation, we could just compute it once,
  10. b added to itself a over 2 times, and then just double the result that we get.
  11. Doing this calculation here is basically now repeating the same operation over again.
  12. Each time we're doing part of the sum here,
  13. we're actually saving ourselves a tremendous amount of effort.
  14. The idea of divide and conquer is that you can break a problem into roughly
  15. equal size sub-problems, solve the sub-problems separately, and combine the results.
  16. And in this particular instance, the sub-problems themselves, these 2 sums, are identical.
  17. It only has to be done once--so you're saving yourself half the effort every time that you do this,
  18. half keeps compounding and that's how we get down to algorithmic number of steps
  19. instead of a linear number of steps.
  20. So this way if looking at the Russian peasant algorithm leads to
  21. a very interesting way of expressing the algorithm recursively.
  22. The idea here is that we're going to do is to multiply a and b together.
  23. What we're going to do is say if a 0 to start, we can just return 0 and be done with it.
  24. On the other hand if a is even, then just because of the derivation that we just worked out
  25. a moment ago, multiplying a times b is really the same thing as adding b to itself
  26. a over 2 times, so it's a over 2 times b, which we're going to compute recursively.
  27. So the Russian algorithm is going to go off and do whatever it does to compute a over 2 times b.
  28. And once we had the answer to that,
  29. we need to multiply that by 2 to get the answer to the original problem.
  30. So we can use the solution to the sub-problem to solve the big problem.
  31. In the case where it's odd, it's a little bit more complicated. Pull one of the b's at.
  32. We're actually adding a's and b's together, but a is odd, so let's pull one of the b's out and add to that,
  33. well what's left--there is a minus 1, repetitions of b that we're adding together, but a minus 1
  34. is now even, so we can have that--compute what a minus 1 over 2 times b is recursively.
  35. Once we have the answer to that, we can multiply it by 2.
  36. Well, it's going to give us what a minus 1 times b is, which is a times b minus b.
  37. So we just add the b back in and we should be done.
  38. Using the solution to the sub-problem, we can compute the solution to the original problem.
  39. So this may be seems a little bit circular, but each time that the Russian peasant algorithm
  40. is being called here, it's being called with a much smaller value--a half that it was before.
  41. And that's where we're getting a lot of our mileage from. Let's actually analyze this algorithm.
  42. It is going to be the same answer as what we got for the Russian peasant algorithm,
  43. but it's going to introduce a new tool that's going to be helpful for us
  44. analyzing lots of other algorithms.