Question

Determine a value for the constant $\mathit{C}$in Example 4 and use it to estimate the number of bit operations needed to multiply two 64-bit integers using the fast multiplication algorithm.

Short answer

$34,000$

Step-by-step solution

Recurrence Relation definition

A recurrence relation is an equation that recursively defines a sequence where the next term is a function of the previous terms:$\mathbf{\text{f(n) = a f(n / b) + c}}$

Apply the Recurrence Relation

This issue is soliciting us to appraise the number from bit operations expected to do the movements, increments, and subtractions in increasing two $2\text{n}$-bit whole numbers by the calculation in Example 4.

In the first place review from Example 9 in Segment 4.2 that the quantity of bit operations required for an expansion of two k-bit numbers is at most$3\text{k}$; the same headed holds for subtraction. Give us a chance to accept that to move a number $\text{k}$bits adition subtractions of n-bit numbers to get $A_1-A_0$and $B_0-B_1$; these will take up to 6 n bit operations through and through. We have to move$A\_1,B\_1,2n$places (requiring $2n$bit operations), and furthermore $n$places (requiring n bit operations); we have to move places (requiring bit operations); and we have to move $A_0{B}_0\text{n}$places, likewiserequiring $n$bit operations.

This makes an aggregate of $5\text{n}$may incorporate a subtraction if the center term is negative).

On the off chance that we are shrewd, we can include the four terms that include at most $3n$bits first (that is, everything with the exception of the $2^{2n}{A}_1{B}_1$).

Three increments are required, each taking 9n bit operations, for a sum of$27n$piece operations. At last we have to perform one expansion including a$4n$-bit number, taking $12n$operations.

This makes a sum of$39n$piece operations for the augmentations.

Clearly this bound is not correct; it relies on upon the real execution of these twofold operations.

Utilizing $C=50$as evaluated over, the repeat connection for quick increase is$f\left(2n\right)=3f\left(n\right)+50n$, with $f\left(l\right)=1$(one duplication of bits is all that is required on the off chance that we have 1 -bit numbers).

In this way we can figure $f\left(64\right)$as takes after:

$$\begin{gathered} f\left(2\right)=3\times 1+50=53; \\ f\left(4\right)=3\times 53+100=259; \\ f\left(8\right)=3\times 259+200=977; \\ f\left(16\right)=3\times 977+400=3331; \\ f\left(32\right)=3\times 3331+800=10793 \end{gathered}$$

lastly $f\left(64\right)=3\times 10793+1600=33979$.

In this manner around $34,000$piece operations are required.