Algorithms- Suppose you are given integers a, b, c, and d, and you must compute

Question

 Algorithms-   Suppose you are given integers a, b, c, and d, and you must compute the two quantities x = ab-cc+bd and y = bb-cc+ad. As written, the equations suggest doing six multiplications, though clearly if cc is computed and stored in an intermediate variable, then only five multiplications are needed.  This could be expressed algorithmically as: temp1 = c*c x = a*b - temp1 + b*d y = b*b - temp1 + a*d which clearly illustrates how to compute the result with five multiplications. That still is not very efficient, though.  By cleverly computing more complex intermediate quantities, show how to compute x AS WELL AS y by using only a total of three multiplications (instead of the five or six multiplications suggested above; it's OK to do a few extra assignments, additions, and/or subtractions.) Clearly state your algorithmic steps, naming your intermediate quantities, and showing the order in which you compute them [like the sample pseudocode using temp1 shown above]. 

Explanation / Answer

Algorithm

1) Let, temp1 = c*c
2) Let, temp2 = b + d
3) Compute, x = temp2*(a + b) - temp1
4) Compute, y = temp2*(b + a) - temp1

Hence by following above method we can complete the computation by having to use only three multiplication.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.