Question

Express the fast multiplication algorithm in pseudocode.

Short answer

Fastmultiply$\left(A_1,B_1\right)+2^n$ fastmultiply $\left(A_1-A_0,B_0-B_1\right)+\left(2^n+1\right)$fastmultiply$\left(A_0,B_0\right)$ return answer.

Step-by-step solution

Fast Multiplication definition

The algorithm for fast multiplication of integers is based on the fact that $\mathit{a}\mathit{b}$can be rewritten as:$\mathit{a}\mathit{b}\mathbf{=}\left(2^{2n}+2^n\right){\mathit{A}}_{\mathbf{1}}{\mathit{B}}_{\mathbf{1}}\mathbf{+}{\mathbf{2}}^{\mathbf{n}}\left(A_1-A_0\right)\left(B_0-B_1\right)\mathbf{+}\left(2^n+1\right){\mathit{A}}_{\mathbf{0}}{\mathit{B}}_{\mathbf{0}}\mathbf{.}$

Use Fast Multiplication and write the pseudocode

In the algorithm "fastmultiply", the input is two nonnegative integers.

Procedure is: fastmultiply ( $a,b$nonnegative integers) If the two integers are $0$or $1$, then multiply the integers directly.

Divide the two integers by $2^n$and their remainders, where $n$is half the length of the integer in binary form. if $a⩽1$and $b⩽1$then return $a,b$else

$$\begin{gathered} n:=\frac{\max \left(length\right(a),length(b\left)\right)}{2} \\ {A}_1:=⌊a/2^n⌋ \\ {B}_1:=⌊b/2^n⌋ \\ {A}_0:=a-2^n{A}_1 \\ {B}_0:=b-2^n{B}_1 \end{gathered}$$

Assume that $A_1,A_0,B_1,B_0$all have length $n$: add $0$'s in front of the number if necessary.

Next use the fact that $a,b$can be rewritten as

$ab=\left(2^{2n}+2^n\right)A_1{B}_1+2^n\left(A_1-A_0\right)\left(B_0-B_1\right)+\left(2^n+1\right)A_0{B}_0$answer $ab=\left(2^{2n}+2^n\right)$fastmultiply $\left(A_1,B_1\right)+2^n$fastmultiply $\left(A_1-A_0,B_0-B\right.)$.

Combine these steps to obtain procedure fast multiply $(a,b:$nonnegative integers with length $n$each if $a⩽1$and $b⩽1$then return $ab$else

$$\begin{gathered} n:=\frac{\max \left(\text{length}\right(a),\text{length}(b\left)\right)}{2} \\ {A}_1:=⌊a/2^n⌋ \\ {B}_1:=⌊b/2^n⌋ \\ {A}_0:=a-2^n{A}_1 \\ {B}_0:=b-2^n{B}_1 \end{gathered}$$

Answer$:=\left(2^{2n}+2^n\right)$

Fastmultiply$\left(A_1,B_1\right)+2^n$ fastmultiply $\left(A_1-A_0,B_0-B_1\right)+\left(2^n+1\right)$ fastmultiply $\left(A_0,B_0\right)$return answer.