
タイトル：
0128 Divide And Conquer

概説：

We're taking a moment to try to understand what it is about the way that the Russian algorithm

is designed that makes it so much better than the naive approach that is just repetitive addition.

Let's just go back for a moment to what multiplication isat least integer multiplication.

It is repeated addition, a times b. Let's focus for the moment on the case where a is even.

Can be written as b plus b plus b plus b, repeated 8 times.

We're considering the case were a is even herewe can regroup them as 2 sums.

B added to itself a over 2 times, and then b added to itself a over 2 times again,

and those 2 things added together, but it's silly to compute the same thing twice.

Clearly if we're doing this calculation, we could just compute it once,

b added to itself a over 2 times, and then just double the result that we get.

Doing this calculation here is basically now repeating the same operation over again.

Each time we're doing part of the sum here,

we're actually saving ourselves a tremendous amount of effort.

The idea of divide and conquer is that you can break a problem into roughly

equal size subproblems, solve the subproblems separately, and combine the results.

And in this particular instance, the subproblems themselves, these 2 sums, are identical.

It only has to be done onceso you're saving yourself half the effort every time that you do this,

half keeps compounding and that's how we get down to algorithmic number of steps

instead of a linear number of steps.

So this way if looking at the Russian peasant algorithm leads to

a very interesting way of expressing the algorithm recursively.

The idea here is that we're going to do is to multiply a and b together.

What we're going to do is say if a 0 to start, we can just return 0 and be done with it.

On the other hand if a is even, then just because of the derivation that we just worked out

a moment ago, multiplying a times b is really the same thing as adding b to itself

a over 2 times, so it's a over 2 times b, which we're going to compute recursively.

So the Russian algorithm is going to go off and do whatever it does to compute a over 2 times b.

And once we had the answer to that,

we need to multiply that by 2 to get the answer to the original problem.

So we can use the solution to the subproblem to solve the big problem.

In the case where it's odd, it's a little bit more complicated. Pull one of the b's at.

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,

well what's leftthere is a minus 1, repetitions of b that we're adding together, but a minus 1

is now even, so we can have thatcompute what a minus 1 over 2 times b is recursively.

Once we have the answer to that, we can multiply it by 2.

Well, it's going to give us what a minus 1 times b is, which is a times b minus b.

So we just add the b back in and we should be done.

Using the solution to the subproblem, we can compute the solution to the original problem.

So this may be seems a little bit circular, but each time that the Russian peasant algorithm

is being called here, it's being called with a much smaller valuea half that it was before.

And that's where we're getting a lot of our mileage from. Let's actually analyze this algorithm.

It is going to be the same answer as what we got for the Russian peasant algorithm,

but it's going to introduce a new tool that's going to be helpful for us

analyzing lots of other algorithms.