Question

In Section 1.2.3, we studied Euclid’s algorithm for computing the greatest common divisor (gcd) of two positive integers: the largest integer which divides them both. Here we will look at an alternative algorithm based on divide-and-conquer.

(a) Show that the following rule is true.

$\mathbf{gcd}\mathbf{(}\mathbf{a}\mathbf{,}\mathbf{b}\mathbf{)}\mathbf{=}\mathbf{\{}\begin{array}{cc}\mathbf{2}\mathbf{gcd}\left(\frac{a}{2},\frac{b}{2}\right)& \mathbf{if}\mathbf{}\mathbf{a}\mathbf{,}\mathbf{b}\mathbf{}\mathbf{are}\mathbf{}\mathbf{even}\\ \mathbf{gcd}\left(a\frac{b}{2}\right)& \mathbf{if}\mathbf{}\mathbf{a}\mathbf{}\mathbf{is}\mathbf{}\mathbf{odd}\mathbf{,}\mathbf{b}\mathbf{}\mathbf{is}\mathbf{}\mathbf{even}\\ \mathbf{gcd}\left(\frac{\left(a-b\right)}{2},b\right)& \mathbf{if}\mathbf{}\mathbf{a}\mathbf{,}\mathbf{b}\mathbf{}\mathbf{are}\mathbf{}\mathbf{odd}\end{array}$

(b) Give an efficient divide-and-conquer algorithm for greatest common divisor.

(c) How does the efficiency of your algorithm compare to Euclid’s algorithm if a and b are n-bit -bit integers? (In particular, since n might be large you cannot assume that basic arithmetic operations like addition take constant time.)

Short answer

(a) The rule can be proved true by the even-odd substitution.

(b) The efficient algorithm is as follows:

Procedure gcd (a,b)

if$a=b$

return a

else if $\left(\left(a\%2=0\right)\wedge \left(b\%2=0\right)\right)$:

return $2.gcd\left(\frac{a}{2},\frac{b}{2}\right)$

else if $\left(\left(a\%2\ne 0\right)\wedge \left(b\%2=0\right)\right)$:

return $gcd\left(a,\frac{b}{2}\right)$

else if $\left(\left(a\%2\ne 0\right)\wedge \left(b\%2\ne 0\right)\wedge \left(a>b\right)\right)$:

return $gcd\left(\frac{\left(a-b\right)}{2},b\right)$

else if $\left(\left(a\%2\ne 0\right)\wedge \left(b\%2\ne 0\right)\wedge \left(a<b\right)\right)$:

return$gcd\left(a,\frac{\left(b-a\right)}{2}\right)$

(c) The running time of the divide-and-conquer algorithm is $O\left(n^2\right)$comparatively faster than the Euclid’s algorithm.

Step-by-step solution

Explain divide-and-conquer algorithm

Divide-and-conquer algorithm solves the large problem by dividing it into the smaller sub-problems. The sub-problems are solved individually and the results of the sub-problems are combined to get the output of the larger problem.

Show that the given rule is true.

(a)

Consider the following given rule,

$\gcd (\mathrm{a},\mathrm{b})=\{\begin{array}{cc}2gcd(\frac{a}{2},\frac{b}{2})& ifa,bareeven\\ gcd\left(a\frac{b}{2}\right)& ifaisodd,biseven\\ gcd(\frac{\left(a-b\right)}{2},b)& ifa,bareodd\end{array}$

If aand b are even numbers, 2 is a common divisor of aand b. Thus , the greatest common divisor will be 2 times the gcd of numbers $\frac{a}{2}$and $\frac{b}{2}$.

If is odd and b is even, then b is divisible by 2. Thus, the gcd of numbers will be same as gcd of a and $\frac{b}{2}$ .

The third property follows from the fact that if a and b are odd, then (a-b) will be even. Since gcd(a,b)=gcd(a,-b,b) and a-b is even . Now applying the second property will prove that the gcd of $\left(\frac{\left(a-b\right)}{2},b\right)$

Therefore, it has been proved that the given rule is true.

Give the efficient algorithm for divide-and conquer.

(b)

The efficient recursive algorithm for solving divide-and-conquer problem is as follows:

Procedure gcd(a,b)

if $a=b$:

return a

else if $\left(\left(a\%2=0\right)\wedge \left(b\%2=0\right)\right)$:

return $2.gcd\left(\frac{a}{2},\frac{b}{2}\right)$

else if $\left(\left(a\%2\ne 0\right)\wedge \left(b\%2=0\right)\right)$:

return$gcd\left(a,\frac{b}{2}\right)$$gcd\left(a,\frac{b}{2}\right)$

else if $\left(\left(a\%2\ne 0\right)\wedge \left(b\%2\ne 0\right)\wedge \left(a>b\right)\right)$:

return $gcd\left(\frac{\left(a-b\right)}{2},b\right)$

else if $\left(\left(a\%2\ne 0\right)\wedge \left(b\%2\ne 0\right)\wedge \left(a<b\right)\right)$:

return $gcd\left(a,\frac{\left(b-a\right)}{2}\right)$

Compare the efficiency of the algorithm with Euclid’s algorithm.

(c)

Consider that a and b are n-bit numbers. Size of a and b is 2n bits. Out of 4 if conditions, every on except the case when is odd and is even, decreases the size of aand b to 2n-2 bits. Each of the operation is constant time operation as the dividing and multiplying the numbers by 2. For two subtractions of two n-bit numbers is the number of bits of the operand. Consider the running time complexity in worst case as follows:

$$\begin{gathered} T\left(2n\right)=T(2n-1)+cn \\ T(2n-1)=T(2n-2)+cn \\ K \\ T\left(2\right)=T\left(1\right)+c \end{gathered}$$

By substitution,

$T\left(2n\right)=2c.\sum _{i=1}^{n}i$

This results in the running time $O\left(n^2\right)$for the divide-and-conquer algorithm. The running time of the Euclid’s algorithm is $O\left(n^3\right)$.

Therefore, the divide-and conquer algorithm is faster with the running time complexity of $O\left(n^2\right)$in worst case.