Question

In Section 2.1 we described an algorithm that multiplies two n-bit binary integers x and y in time ${\mathit{n}}^{\mathbf{a}}$, where $\mathbf{a}\mathbf{=}{\mathbf{log}}_{\mathbf{2}}\mathbf{3}$. Call this procedure fast multiply (x,y).

(a) We want to convert the decimal integer ${\mathbf{10}}^{\mathbf{n}}$(a 1 followed by n zeros) into binary. Here is the algorithm (assume n is a power of 2):

function pwr2bin(n)

if n = 1: return${\mathbf{1010}}_{\mathbf{2}}$

else:

z= ???

return fastmultiply(z,z)

Fill in the missing details. Then give a recurrence relation for the running time of the algorithm, and solve the recurrence.

(b) Next, we want to convert any decimal integer x with n digits (where n is a power of 2) into binary. The algorithm is the following:

function dec2bin(x)

if n=1: return binary [ x ]

else:

split x into two decimal numbers ${\mathit{x}}_{\mathbf{t}}\mathbf{,}\mathbf{}\mathbf{}{\mathit{x}}_{\mathbf{R}}$with n/2 digits each

return ???

Here binary [.] is a vector that contains the binary representation of all one-digit integers. That is, binary role="math" localid="1659333641173" $\left[0\right]\mathbf{=}{\mathbf{0}}_{\mathbf{2}}$, binary $\mathbf{\left[}\mathbf{1}\mathbf{\right]}\mathbf{=}{\mathbf{1}}_{\mathbf{2}}$, up to binary $\mathbf{\left[}\mathbf{9}\mathbf{\right]}\mathbf{=}{\mathbf{1001}}_{\mathbf{2}}$. Assume that a lookup in binary takes 0(1) time. Fill in the missing details. Once again, give a recurrence for the running time of the algorithm, and solve it.

Short answer

a).Filling the missing details of the algorithm.

b). proving the recurrence for the running time of the algorithm.

Step-by-step solution

Solution of part (a)  

Filling the missing details of the algorithm:

function pwr2bin(n)

if n=1 :

return ${1010}_2$

else:

z = pwr2bin (n/2)

return fastmultiply(z,z)

The highlighted part of the algorithm is the missing part.

Description: • "pwr2bin" is a function that takes a decimal integer and transforms it to binary using the power of ten as an input argument.

• It first validates whether n is equal to 1 and then returns the binary number ${1010}_2$.

• If not, it calls the same function "pwr2bin" with the argument (n/2).

• It then returns the result of the function "fastmultiply" with arguments as the result of the function "pwr2bin."

o The "fastmultiply" technique returns the product of two binary digits.

The textbook contains the algorithm. Figure 2.1 shows the "fastmultiply" algorithm's execution time. is $0\left(n^{\log 3}\right)$.

Thus, it takes T(n/2) time to check the power of $0\left(n^k\right)$and a time of to perform the multiplication. So the recurrence relation is,

$T\left(n\right)=T\left(n/2\right)+\mathit{0}\mathit{\left(}{n}^{\log 3}\mathit{\right)}$ …… (1)

Consider the master theorem for the following recurrence equation,

$T\left(n\right)=aT\left(n/b\right)+\mathit{0}\left(n^c\right)$ …… (2)

By comparing equation (1) and (2), the value of “$n^c$” is “n”, “c” is “ ${\log }_{2}3$”, “b” is “2” and “a” is 1.

By master’s theorem, if the value of $\mathrm{c}>{\log }_{\mathrm{b}}\mathrm{a}$, then the running time is,

$\mathrm{T}\left(\mathrm{n}\right)=0\left({\mathrm{n}}^{\mathrm{c}}\right)$ …… (3)

Check if $\mathrm{c}>{\log }_{\mathrm{b}}\mathrm{a}$:

${\log }_{\mathrm{b}}\mathrm{a}$ …… (4)

Substitute the value of “b” as 2 and “a” as 1 in equation (4).

${\log }_{\mathrm{b}}\mathrm{a}={\log }_{2}1=0$

Thus, the value of ${\log }_{b}a$is less than “c” which is ${\log }_{2}3=1.58$.

Substitute ${\mathrm{n}}^{\mathrm{k}}$as $n^{lo{g}_{2}3}$in equation (3). The running time of algorithm is shown below:

$\mathrm{T}\left(\mathrm{n}\right)=0\left({\mathrm{n}}^{{\log }_{2}3}\right)$

Therefore, the algorithm takes a run time of $0\left({\mathrm{n}}^{{\log }_{2}3}\right)$.

Solution of part (b)

Filling the missing details of the algorithm:

function dec2bin(x )

if n = 1:

return binary [x]

else:

split x into two decimal numbers ${\mathrm{x}}_{\mathrm{L}},{\mathrm{x}}_{\mathrm{R}}$with $n/2$digits each

return ( fastmultiply ( pwr2bin(n/2), dec2bin(localid="1659334894381" ${\mathrm{x}}_{\mathrm{L}}$)))+ dec2bin(localid="1659334900087" ${\mathrm{x}}_{\mathrm{R}}$)

The highlighted part of the algorithm is the missing part.

Explanation:

• “dec2bin” is the function which accepts the decimal value “x” as the input parameter and it converts the decimal integer “x” with “n” digits into binary.

• Initially, it checks whether the number of digits “n” is equal to 1 and returns the binary value.

• Otherwise, it splits the decimal into two halves.

• Then, it returns the value returned by the function “fastmultiply” with parameters as the value of the function “ pwr2bin(n/2) ” and “dec2bin($x_L$)” along with the addition of dec2bin(${\mathrm{x}}_{\mathrm{R}}$).

o Here, “pwr2bin” function convert the decimal integer (n/2) into binary.

o “dec2bin” function convert the decimal integer “$x_L$” into binary.

o Then, finally the value returned by the fastmultiply is added with the value returned by dec2bin($x_R$)

The algorithm “dec2bin” splits the number into two halves and process which takes a time of 2T(n/2) and as seen already the running time of “fastmultiply” algorithm is $0\left({\mathrm{n}}^{{\log }_{2}3}\right)$.

So the recurrence relation is,

$\mathrm{T}\left(\mathrm{n}\right)=2\mathrm{T}(\mathrm{n}/2)+\mathit{0}\left({\mathrm{n}}^{{\log }_{2}3}\right)$ …… (1)

Consider the master theorem for the following recurrence equation,

role="math" localid="1659335661292" $\mathrm{T}\left(\mathrm{n}\right)=\mathrm{a}\mathrm{T}(\mathrm{n}/\mathrm{b})+{\mathrm{n}}^{\mathrm{c}}$ …… (2)

By comparing equation (1) and (2), the value of “n” is “ ${\mathrm{n}}^{{\log }_{2}3}$”, “c” is ${\log }_{2}3$, “b” is “2” and “a” is 2.

By master’s theorem, if the value of c > log_ba, then the running time is,

$\mathrm{T}\left(\mathrm{n}\right)=0\left({\mathrm{n}}^{\mathrm{c}}\right)$ …… (3)

Check if $\mathrm{c}>{\log }_{\mathrm{b}}\mathrm{a}$:

${\log }_{\mathrm{b}}\mathrm{a}$ …… (4)

Substitute the value for “b” as 2 and “a” as 2, in equation (4).

${\log }_{\mathrm{b}}\mathrm{a}={\log }_{2}2=1$

Thus, the value of ${\log }_{b}a$is less than “c” which is role="math" localid="1659335310024" ${\log }_{2}3=1.58$.

Substitute “c” as ${\log }_{2}3$in equation (3). The running time of algorithm is shown below:

$T\left(n\right)=0\left(n^{{\log }_{2}3}\right)$

Therefore, the algorithm takes a run time of $0\left(n^{{\log }_{2}3}\right)$.