1.2: Suppose you are given integers a, b, c, and d, and you must compute the two

Question

 1.2: Suppose you are given integers a, b, c, and d, and you must compute the two quantities x = ab+bc+ad-cc and y = ab+cc+cd As written, the equations suggest doing seven multiplications, though clearly if cc is computed and stored in an intermediate variable, then only six multiplications are needed.  This could be expressed algorithmically as: temp1 = c*c x = a*b + b*c + a*d - temp1 y = a*b + temp1 + c*d which clearly illustrates how to compute the result with six multiplications. That still is not very efficient, though.  Note that divisions 'cost' as much as multiplications, so don't try to replace a multiplication with several divisions.  (Rather, as the problem indicates, your goal is to replace a multiplication with some additions and/or subtractions.)  Trying to simulate a multiplication with a few million repeated additions would likewise not be considered an acceptable answer.  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 six or seven multiplications suggested above; it's OK to do a few extra assignments, additions, and/or subtractions.) Hint: try to make clever use of the distributive law.  Note that the requirement is not 3 for EACH equation, but 3 multiplications in total for BOTH equations).  That is, show the pseudocode for a program that will accept a,b,c,d as input and print BOTH x and y as output, using only 3 "*" operators in your code.  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].  You will likely have lots of scratchwork to help justify how you derived your formula[s], and this is likely to obscure exactly what steps are in your final algorithm, and the order in which they should be executed.  So:  CLEARLY INDICATE YOUR PSEUDOCODE and enclose it in a box, so that I can figure out what assignment statements actually comprise your algorithm. 

Explanation / Answer

Hey,

Below is the answer to your question

Algorithm

Given, x=ab+bc+ad-cc=(a+c)(b+d)-c(c+d)

y=ab+cc+cd=ab+cc+cd=ab+c(c+d)

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

Kindly revert for any queries

Thanks.

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

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