This is a transfer and conquers experiment, please analyze and write a source code

This is a transfer and conquers experiment, please analyze and write a source code the algorithms are provided to you, you just need to write the source code

4. Algorithm's principles 4.1 Horner's Rule Horner's rule is an old but very elegant and efficient algorithm for evaluating a polynomial. It is named after the British mathematician W. G. Horner, who published it in the early 19th century. But according to Knuth [Knu II, p. 486], the method was used by Isaac Newton 150 years before Horner. You will appreciate this method much more if you first design an algorithm for the polynomial evaluation problem by yourself and investigate its efficiency (see Problems 1 and 2 in this section's exercises). Horner's rule is a good example of the representation change technique since itis based on representing p(x) by a formula different from (6.1). This new formula is obtained from (6.1) by successively taking x as a common factor in the remaining polynomials of diminishing degrees: p(x) = ( (anx + an-1)x+ ...)x + do. For example, for the polynomial p(x) = 2x4 x3 + 3x + x - 5 = x(2x3 x + 3x + 1) - 5 = x(x (2.x2 - x + 3) + 1) - 5 = x(x(x (2x - 1) + 3) + 1) - 5. It is in the above formula that we will substitute a value of x at which the polynomial needs to be evaluated. It is hard to believe that this is a way to an efficient algorithm, but the unpleasant appearance of formula is just that, an appearance. As we shall see, there is no need to go explicitly through the transformation leading to it: all we need is an original list of the polynomial's coefficients. The pen-and-pencil calculation can be EXAMPLE 1 Evaluate p(x) = 2x4 x3 + 3x + x 5 at x = 3. coefficients 2 -1 3 1 -5 x=3 23.2+(-1)=5 3.5+3= 18 3.18+1=55 3.55+ (-5) = 160 = Thus, p(3) = 160. (On comparing the table's entries with formula (6.3), you will see that 3 2+(-1)=5 is the value of 2x 1 at x = 3,3.5+3= 18 is the value of x(2x - 1) + 3 at x = 3, 3. 18+1= 55 is the value of x(x (2x - 1) + 3) + 1 at x = 3, and, finally, 3. 55+ (-5) = 160 is the value of x(x(x (2x - 1) + 3) + 1) - 5= p(x) at x = 3.) ALGORITHM Horner(P[O..n), x) //Evaluates a polynomial at a given point by Horner's rule //Input: An array P[0..n] of coefficients of a polynomial of degreen, // stored from the lowest to the highest and a number x //Output: The value of the polynomial at x p=P[N] for in-1 downto 0 do Px*p+ P[i] return p Horner's rule for the binary polynomial p(2) Implications for a" = q P(2) p=1 //the leading digit is always 1 for n > 1 for i + 1 - 1 downto 0 do p2p+b apa? for i = 1 1 downto 0 do GP - a2p+b; But q2p+b = q?p.albi = (ap)2.4" = {cam2.aif b;=1. bi ()? 0 = (ap) Thus, after initializing the accumulator's value to a, we can scan the bit string representing the exponent n to always square the last value of the accumulator and, if the current binary digit is 1, also to multiply it by a. These observations lead to the following left-to-right binary exponentiation method of computing a". ALGORITHM LeftRightBinary Exponentiation(a, b(n)) //Computes a" by the left-to-right binary exponentiation algorithm //Input: A number a and a list b(n) of binary digits bj, ..., bo 11 in the binary expansion of a positive integer n //Output: The value of a" product a for i + 1 - 1 downto 0 do product + product * product if b; = 1 product product * a return product EXAMPLE 2 Compute a 3 by the left-to-right binary exponentiation algorithm. Here, n = 13 = 11012. So we have 1 binary digits of n product accumulator 1 az-a =a3 0 (a3)2 = 6 1 (a")2 - a =q13 a 4. Algorithm's principles 4.1 Horner's Rule Horner's rule is an old but very elegant and efficient algorithm for evaluating a polynomial. It is named after the British mathematician W. G. Horner, who published it in the early 19th century. But according to Knuth [Knu II, p. 486], the method was used by Isaac Newton 150 years before Horner. You will appreciate this method much more if you first design an algorithm for the polynomial evaluation problem by yourself and investigate its efficiency (see Problems 1 and 2 in this section's exercises). Horner's rule is a good example of the representation change technique since itis based on representing p(x) by a formula different from (6.1). This new formula is obtained from (6.1) by successively taking x as a common factor in the remaining polynomials of diminishing degrees: p(x) = ( (anx + an-1)x+ ...)x + do. For example, for the polynomial p(x) = 2x4 x3 + 3x + x - 5 = x(2x3 x + 3x + 1) - 5 = x(x (2.x2 - x + 3) + 1) - 5 = x(x(x (2x - 1) + 3) + 1) - 5. It is in the above formula that we will substitute a value of x at which the polynomial needs to be evaluated. It is hard to believe that this is a way to an efficient algorithm, but the unpleasant appearance of formula is just that, an appearance. As we shall see, there is no need to go explicitly through the transformation leading to it: all we need is an original list of the polynomial's coefficients. The pen-and-pencil calculation can be EXAMPLE 1 Evaluate p(x) = 2x4 x3 + 3x + x 5 at x = 3. coefficients 2 -1 3 1 -5 x=3 23.2+(-1)=5 3.5+3= 18 3.18+1=55 3.55+ (-5) = 160 = Thus, p(3) = 160. (On comparing the table's entries with formula (6.3), you will see that 3 2+(-1)=5 is the value of 2x 1 at x = 3,3.5+3= 18 is the value of x(2x - 1) + 3 at x = 3, 3. 18+1= 55 is the value of x(x (2x - 1) + 3) + 1 at x = 3, and, finally, 3. 55+ (-5) = 160 is the value of x(x(x (2x - 1) + 3) + 1) - 5= p(x) at x = 3.) ALGORITHM Horner(P[O..n), x) //Evaluates a polynomial at a given point by Horner's rule //Input: An array P[0..n] of coefficients of a polynomial of degreen, // stored from the lowest to the highest and a number x //Output: The value of the polynomial at x p=P[N] for in-1 downto 0 do Px*p+ P[i] return p Horner's rule for the binary polynomial p(2) Implications for a" = q P(2) p=1 //the leading digit is always 1 for n > 1 for i + 1 - 1 downto 0 do p2p+b apa? for i = 1 1 downto 0 do GP - a2p+b; But q2p+b = q?p.albi = (ap)2.4" = {cam2.aif b;=1. bi ()? 0 = (ap) Thus, after initializing the accumulator's value to a, we can scan the bit string representing the exponent n to always square the last value of the accumulator and, if the current binary digit is 1, also to multiply it by a. These observations lead to the following left-to-right binary exponentiation method of computing a". ALGORITHM LeftRightBinary Exponentiation(a, b(n)) //Computes a" by the left-to-right binary exponentiation algorithm //Input: A number a and a list b(n) of binary digits bj, ..., bo 11 in the binary expansion of a positive integer n //Output: The value of a" product a for i + 1 - 1 downto 0 do product + product * product if b; = 1 product product * a return product EXAMPLE 2 Compute a 3 by the left-to-right binary exponentiation algorithm. Here, n = 13 = 11012. So we have 1 binary digits of n product accumulator 1 az-a =a3 0 (a3)2 = 6 1 (a")2 - a =q13 a