Differences

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

--- courses:cs211:winter2012:journals:suraj:chapter5.txt [2012/03/13 03:11] – bajracharyas
+++ courses:cs211:winter2012:journals:suraj:chapter5.txt [2012/03/13 03:32] (current) – bajracharyas
@@ Line 139: / Line 139: @@
 ==== 5.5 Integer Multiplication ====
+=== The Problem ===
+The normal integer multiplication takes O(n²) time, because you go through each digit in the first integer, multiply it by each digit in the 2nd integer, and add the product up by shifting each of the following one to a digit left.
+=== Designing the Algorithm ===
+Instead of multiplying the two n-bit numbers, the following algorithm solves four n/2-bit numbers. So, we get the recursive algorithm as written in page 233.
+=== Analyzing the Algorithm ===
+Unrolling the algorithm, we get T(n) <= qT(n/2) + cn. Thus, the runtime would be reduced to O(n^(log(2) q)).
 ==== Questions and Comments ====
+=== As of March 7th, Wednesday ===
 No questions.
 Comments are on the top of the page :)
 And the chapter (so far) was easily readable, of course because of the class discussions, as usual.
+=== As of March 14th, Tuesday ===
+I would like to go through Integer Multiplication once more. I'd probably come meet you sometime this week about this. It was kind of hard to get the designing part, both from the book and from the class, though I understood the basics.
+The rest of the section was easy to understand. Class helped a lot.