You can assume that all addition, subtraction and division by a constant are ().

In class, we described and analyzed Karatsuba's algorithm for long integer multiplication. It turns out the Karatsuba algorithm is a special case of the Toom-Cook multiplication that splits the integers into k pieces.Toom-3 is a very common approach, in Toom-3 integers A and B are each split into 3-parts. Below is a description of Toom-3: - Given two integers A and B, split into A3,A2,A1 and B3,B2,B1, with A3 and B3 being the most significant chunks -leftmost bits-. - Calculate the following intermediate values: X=A1B1Y=(A3+A2+A1)(B3+B2+B1)Z=(A3A2+A1)(B3B2+B1)U=(4A32A2+A1)(4B32B2+B1)V=A3B3 - find C1,C2,C3,C4,C5 using: C1=XC5=VC3=(Y+Z)/2XVC4=(3C1+6C3+18+C5VY)/6C2=YC1C3C4C5 - The result C is the concatenation of C1,C2,C3,C4,C5 4- Find the formula describing the cost of layer k of the tree. ( 2 points) 5- What is the depth of the tree in terms of n. ( 2 points) 6- Find the of Toom-3 using the previous values -from the tree-. ( 2 points)