Still incomplete answer, but already has content on complete polynomials.Complete PolynomialsBy complete polynomials we understand polynomials that can be represented by BeingI different from zero; that is, no coefficient is null and therefore the polynomial will have all terms relative to the powers of x.Mathematical considerationsTake as an example polynomial a complete polynomial represented by Where p(x) is the polynomial, theI is the actual non-zero coefficient of grade i and $x^i I-- power x. If we expand this sum, we will obtain: We can observe that, excepting the term $0, all terms have x and we know that given the associative property we can put the term in common in evidence, obtaining: If we do this recursively with the terms within the relatives we will get: In this way, to calculate the value of p(x), we can solve:bn =nbNo =No + bn xbNo. =No. + bNo x...b1 =1 + b2 xb0 =0 + b1 xThus resulting in p(x) = b0, so that we reduce the resolution of a degree n polynomial for the first-degree polynomial resolutions. That's the Horner method.BehaviorWhile for the calculation of a point of grade n polynomial in the traditional method demande n(n+1)/2 multiplications and n additions, with the Horner method the number of operations is reduced to n multiplications and n additions and we know that the less operations not only the calculation tends to get faster as it will be less susceptible to errors.A possible implementation of the Horner method is, calculating p(x=1) = x5 - 4x4 + 3x3 - 2x2 + x - 9:float x = 1;
float coefficients[] = {1, -4, 3, -2, 1, -9};
float result = 0;
for (int i = 0; i < sizeof(coefficients)/sizeof(float); i++) {
result = coefficients[i] + result*x;
}
printf("%f\n", result);
Although we have the gain with the reduction of operations necessary for the calculation, we still have considerations to do.First, the intrinsic problem of computing in working with floating point number. The guy float of language C is represented according to the IEEE 754 specification using 32 bits, being 1 bit of signal, 8 bits to represent the exponent and 23 bits to represent the mantissa, which gives us a accuracy of only 7 decimal houses. Even, the greater the mantissa, the less decimal houses we will have available for the decimal part, then it is expected that if the value grows too much the decimal part is lost and therefore our result will suffer truncations. https://pt.stackoverflow.com/q/5642/5878 https://pt.stackoverflow.com/q/260685/5878 https://pt.stackoverflow.com/q/219211/5878 Second, our result will be defined by coefficients[i] + resultx. From mathematics, we know that a + b will tend a if a it is much bigger than b, a >> b. For example, 10000+1 is approximately 10000. It will imply that if resultx it is much bigger than coefficients[i] the value of the latter will be despicable, making also the truncation of value.For comparison purposes, https://ideone.com/cdXKIR above, to x = 1, we get the result -10, which https://www.wolframalpha.com/input/?i=x%5E5-4x%5E4%2B3x%5E3-2x%5E2%2Bx-9%20for%20x%20%3D%201 . Now, when https://ideone.com/fFDKCs , we get the result 996003050160128, while the https://www.wolframalpha.com/input/?i=x%5E5-4x%5E4%2B3x%5E3-2x%5E2%2Bx-9%20for%20x%20%3D%201000 .
