Question

The grade-school algorithm for multiplying two n-bit binary numbers x and y consist of addingtogethern copies of r, each appropriately left-shifted. Each copy, when shifted, is at most 2n bits long.
In this problem, we will examine a scheme for adding n binary numbers, each m bits long, using a circuit or a parallel architecture. The main parameter of interest in this question is therefore the depth of the circuit or the longest path from the input to the output of the circuit. This determines the total time taken for computing the function.
To add two m-bit binary numbers naively, we must wait for the carry bit from position i-1before we can figure out the ith bit of the answer. This leads to a circuit of depth$\mathbf{{\rm O}}\left(m\right)$. However, carry-lookahead circuits (seewikipedia.comif you want to know more about this) can add in$\mathbf{{\rm O}}\mathbf{}\left(\mathrm{logn}\right)$depth.

1. Assuming you have carry-lookahead circuits for addition, show how to add n numbers eachm bits long using a circuit of depth $\mathbf{{\rm O}}\left(\left(\mathrm{logn}\right)\left(\mathrm{logm}\right)\right)$.
2. When adding three m-bit binary numbers $\mathbf{x}\mathbf{+}\mathbf{y}\mathbf{+}\mathbf{z}$, there is a trick we can use to parallelize the process. Instead of carrying out the addition completely, we can re-express the result as the sum of just two binary numbers$\mathbf{r}\mathbf{+}\mathbf{s}$, such that the ith bits of r and s can be computedindependently of the other bits. Show how this can be done. (Hint: One of the numbers represents carry bits.)
3. Show how to use the trick from the previous part to design a circuit of depth$\mathbf{{\rm O}}\left(\mathrm{logn}\right)$for multiplying two n-bit numbers.

Short answer

1. Here, totally this addition operation contains$\mathrm{{\rm O}}\left(\left(\mathrm{logn}\right)\left(\mathrm{logm}\right)\right)$ depth.
2. The value of"r" and "s"has been taken and then it can be mentionedas$\mathrm{x}+\mathrm{y}+\mathrm{z}=\mathrm{r}+\mathrm{s}$.
3. The multiplication process can be represented as $\mathrm{n}\times {\left(\frac{2}{3}\right)}^{\mathrm{k}}=1$where $\mathrm{k}=\frac{\log \mathrm{n}}{\log 3-\log 2}=\mathrm{{\rm O}}\left(\log \mathrm{n}\right)$.

Step-by-step solution

Step 1: Introduction to the Concept

Parallel architectures are a type of distributed computing in which multiple processes work together to solve a single problem.

Step 2: Solution Explanation

a)

Assume that "n" equals "$2$" and "k" equals a fixed value for minimalism.

• Here are the instructions for adding "n" numbers:
  1. At first, the "$2^{\mathrm{k}}$" numbers must be divided into “$2^{\mathrm{k}-1}$”different pairs."
  2. Next, add each pair of values using look-ahead circuits.
  3. Repeat the process for each of the results returned by the previous operation.
  4. A complete binary tree with "$\log \mathrm{n}$" levels have been created utilizing the results of the foregoing process.
• Each level employs " $\log \mathrm{m}$" extra levels for additional operations.
• Take note that if "n" is not a power of "2", the tree will not be completed.

As a result, this additional operation comprises “$\mathrm{{\rm O}}\left(\left(\log \mathrm{n}\right)\left(\log \mathrm{m}\right)\right)$”in total in-depth.

Step 3: Solution Explanation

b)

Assume that the "${\mathrm{i}}^{\mathrm{th}}$" bit of "r" is the result of adding the "${\mathrm{i}}^{\mathrm{th}}$" bits of all three values.

• Also, consider "s" as the carry of adding the "${\mathrm{i}}^{\mathrm{th}}$" bit of three integers (i.e., the carry is "1" when two or three of the "${\mathrm{i}}^{\mathrm{th}}$" values are "1").

As a result, assuming the previous steps have taken the values of "r" and "s" it may be written as "$\mathrm{x}+\mathrm{y}+\mathrm{z}=\mathrm{r}+\mathrm{s}$."

Step 4: Solution Explanation

c)

To multiply, "n" copies of "x" that are slightly moved must be added together.

• The copies of numbers must be split into triplets and the addition operation conducted in the part (b) must be completed.
• Repeat these steps for each of the "k" levels until only three numbers remain.

As a result, “$\mathrm{n}={\left(\frac{2}{3}\right)}^{\mathrm{k}}=1$can be used to describe the multiplication process, where

“$\mathrm{k}=\frac{\log \mathrm{n}}{\log 3-\log 2}=\mathrm{{\rm O}}\left(\log \mathrm{n}\right)$”.