State your answers legibly and concisely. Your solutions will be graded on correctness, elegance, clarity, and originality. Please remember that although group work is permitted, the work handed in must be in your own words.

Complete the design of the following algorithm for performing integer multiplication in time (1.631). (This is slower than the standard algorithm, but its verification and analysis will test your abilities.) We use a technique similar to the standard divide-and-conquer algorithm. Instead of dividing the inputs and into two parts, we divide them into three parts. Suppose and have bits, where is a power of 3. Break into three parts , , c, each with /3 bits. Break into three parts , , , each with /3 bits. Then, =24/3 +(+)2 +(++)22/3 +(+)2/3 + This can be computed as follows:

1 ≔

2 ≔(+)(+)

3 ≔

4 ≔(+)(+)

5 ≔

6 ≔(+)(+)

≔124

3 +(2 −1 −3)2 +(3 +4 −1 −5)22

3 +(6 −3 −5)2

3 +5

1. Show that, as claimed above, =24/3 +(+)2 +(++)22/3 +(+)2/3 +

2. Show that = .

3. Show that this algorithm runs in (1.631) bit-operations, as claimed