Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision |
| courses:cs211:winter2011:journals:camille:chapter5 [2011/03/13 21:24] – [Section 4: Finding the Closest Pair of Points] cobbc | courses:cs211:winter2011:journals:camille:chapter5 [2011/03/13 22:18] (current) – [Section 5: Integer Multiplication] cobbc |
|---|
| Great! They've gotten away from the end-of-section proof that it works and analysis of running time. I'm not sure if it helps or if it would be just as good to do it as they give the algorithm, but it was interesting that it came back. | Great! They've gotten away from the end-of-section proof that it works and analysis of running time. I'm not sure if it helps or if it would be just as good to do it as they give the algorithm, but it was interesting that it came back. |
| |
| ===== Section 4: Finding the Closest Pair of Points ===== | ===== Section 5: Integer Multiplication ===== |
| |
| * **Summary:** | * **Summary:** |
| | This problem will reduce running time by having more than two recursive calls at each level. The elementary school way of multiplying two numbers takes O(n^2) time, which is good, but it could be better. Instead of doing it that way, though, you can separate n-bit binary numbers (they say it works for other number systems, too) into two n/2-bit binary numbers (the first n/2 digits, "high-order" digits, x1 and y1 and the last n/2 digit, "low order" digits, x0 and y0). Then xy = x1y1*2^n + (x1y0+x0y1)*2^n/2 + x0y0 ... anyway, the equation's not the point. The point is that you trade multiplication for addition (which takes O(n) time). So the recurrence relation is T(n) <= 4*T(n/2) + cn, but that just gives us O(n^2) time back ... so there was no advantage to doing this. So instead, you can modify it a little so that you do determine x1y1 and x0y0 by recursion and get the outermost terms explicitly and the middle term by subtracting x1y1 and x0y0 from (x1+x0)(y1+y0). They show that algorithm. So now the recursive relation is T(n)<= 3*T(n/2)+cn, which results in an O(n^logbase2(3)) or O(n^1.59) running time, which is a significant improvement! |
| |
| * **Insights and Questions:** | * **Insights and Questions:** |
| | This is a really interesting example of how differently computers and people think. There's no way it would be easier or more efficient for a human to solve this problem this way. It's also an interesting example of a tradeoff between efficiency and intuitiveness ... hmm. |
| |
| * **Readability:** | * **Readability:** |
| | I thought that, once again, this section was very readable! |
