Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision |
| courses:cs211:winter2011:journals:david:chapter5 [2011/03/09 03:55] – [5.4 - Finding the Closest Pair of Points] margoliesd | courses:cs211:winter2011:journals:david:chapter5 [2011/03/09 04:18] (current) – [5.5 - Integer Multiplication] margoliesd |
|---|
| |
| Readability: 6/10. Rereading this section a few times helped my understanding, so I'd rate my understanding at an 8/10 now. | Readability: 6/10. Rereading this section a few times helped my understanding, so I'd rate my understanding at an 8/10 now. |
| | |
| | ====5.5 - Integer Multiplication==== |
| | |
| | When considering the standard elementary way of multiplying two numbers, we get an efficiency of O(n<sup>2</sup>). Our first attempt at a solution is to break up each number into its higher order half and its lower order half. We then compute the products of each set of bits and add them together, which means we have broken our problem into 4 recursive calls. Unfortunately, this still gives O(n<sup>2</sup>) efficiency. To find a more efficient solution, we need to break the problem up into less than 4 recursive calls. The trick is to subtract the sum of the product of the first two halves and the last two halves from the total product. This gives us only 3 recursive calls, and an efficiency of O(N<sup>1.59</sup>). |
| | |
| | Readability: 7/10 |
