Differences

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

--- courses:cs211:winter2012:journals:ian:chapter5 [2012/03/14 03:59] – 5.3 5.4 sturdyi
+++ courses:cs211:winter2012:journals:ian:chapter5 [2012/03/14 04:08] (current) – sturdyi
@@ Line 26: / Line 26: @@
    * This chapter seems really focused on improving on O(n^2) runtimes. Having seen the difference between O(n log n) and O(n^2) in practice (in Economics I have Ns ranging above 10e7), I am not complaining. But why the fixation on polynomial time as the standard for efficiency, given how often brute force achieves it and how often we attempt to improve on it?
    * No complaints.
+====== 5.5 Integer Multiplication ======
+   * The conventional multiply-and-carry multiplication algorithm is O(n^2) for multiplying two n digit numbers (n nx1 multiplications, each O(n), plus n O(n) additions). One can also multiply by divide-and conquer; instead of using the equivalence that if a=10q+r, ab=10bq+br, one uses a=2^(n/2)a_1+a_0 and b=2^(n/2)b_1+b_0, ab=a_1b_1*2^n+(a_1b_0+a_0+b_1)^(n/2)+a_0x_0. This creates 4 subproblems of size n/2, plus a constant number of O(n) additions. This comes back to the earlier recurrence relation T(n) <= 4T(n/2)+O(n), but this gives O(n^2). Improving requires a reduction in the number of multiplications; using the equality ab=a_1b_!*2^n+((a_1+a_0)(b_1+b_0)-a_1b_1-a_0b_0)*2^(n/2)+a_0b_0 uses just three, with running time O(n^(log_2 3))=O(n^1.59).
+   * No insights.
+   * No questions.
+   * No complaints. I appreciated their giving the derivation of the second identity.