Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |||
| courses:cs211:winter2014:journals:shannon:chapter5 [2014/03/12 01:28] – [Chapter 5.4: Finding the Closest Pair of Points] nollets | courses:cs211:winter2014:journals:shannon:chapter5 [2014/03/12 01:47] (current) – [Chapter 5.5: Integer Multiplication] nollets | ||
|---|---|---|---|
| Line 39: | Line 39: | ||
| ===== Chapter 5.5: Integer Multiplication===== | ===== Chapter 5.5: Integer Multiplication===== | ||
| + | In this section we look at a way to make the multiplication of two integers run in less than O(n^2) time. In order to do this, rather than using the traditional method, in which you multiply each digit in one integer by the other digits in the other integer and then adding the results together. | ||
| + | The change the algorithm, the section first looked at splitting the multiplication process into 4 parts of n/2 size. However, this runs in O(n^2) time, which is not an improvement. | ||
| + | If we instead divide the multiplication into 3 parts of n/2 size, we can have the algorithm run in (n^1.59) time. The algorithm (one page 233 in the text)finds a way to split the multiplication process into these three parts. We then write x1y1*2^n+(p-x1y1-x0y0)*2^n/ | ||
| + | |||
| + | This section was short and sweet, which was nice. I did not know that was how you multiplied binary numbers (we learned a different way in 210). I would give it a 8/10. | ||
