Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2011:journals:charles:chapter5 [2011/03/16 06:35] – [5.5 Integer Multiplication] gouldc
+++ courses:cs211:winter2011:journals:charles:chapter5 [2011/03/16 06:57] (current) – [5.6 Convolutions and the Fast Fourier Transform] gouldc
@@ Line 34: / Line 34: @@
 (5.12) The running time of the [Closest-Pair] algorithm is O(n log n).
 ===== 5.5 Integer Multiplication =====
-It would seem that multiplying two n-digit integers requires O(n^2) time (the computation of n^2 partial products). But that is wrong. We can reduce the cost of computing the product xy by recursively performing operations on the four (n/2)-digit segments of x and y. dividing the n-digit integers (x, y) into two (n/2)-digit integers (x1, x2, y1, and y2). We rely on fewer multiplications and more additions (pp. 232-233 explain this well).
+This problem gives an algorithm that multiplies integers in sub-quadratic time (better than we usually do when we multiply by hand). It computes the product xy by recursively dividing x and y in half and performing operations on those (n/2)-digit segments. It relies on fewer multiplications and more additions (pp. 232-233 explain this well).
 This example shows why thinking about recurrence relations can be useful. For example, we knew that dividing the problem into any more than 3 subproblems (with linear time combination &etc) would result in an equivalent or worse running time than the normal algorithm. Therefore we looked for a way to divide the problem into 3 subproblems (while maintaining linear time combination &etc). Sure, it required our being clever, but the understanding of recurrence relations made it easier than it would have been.
 ===== 5.6 Convolutions and the Fast Fourier Transform =====
-...
+I learned a new math term: convolution. Convolutions are a yuge deal in signal processing. This section gives a sub-quadratic algorithm for computing the convolution. The Fast Fourier Transform computes the convolution in O(n log n) time. (5.15).