Describe a divide and conquer algorithm to compute the square of an n$-$digit

integer in O$($n

log$2$

$3$

$)$ time, by reducing to the squaring of three $$n$/2-$digit integers.

Adding two numbers with k digits, and shifting a number with k digits take O$($k$)$

time.

Your submission should include the following points:

$$ Problem statement. You need not provide an example.

$$ The main idea of the algorithm. Argue the correctness of your algorithm here,

by showing how the algebraic derivations are used by your algorithm.

$$ Algorithm pseudo$-$code.

$$ Running time analysis. You can directly use the solution of the recurrence

relation worked in class $($aka Master Theorem $/$ recursion trees section in the

text$).$

Hint: use the identity xy $=$

x

$2+$y

$2($x$$y$)$

$2$

$2$

$.$