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

1. タイトル：
   01-28 Divide And Conquer
2. 概説：

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