TheAlgorithms-Python

1
from collections.abc import Sequence
2

3

4
def evaluate_poly(poly: Sequence[float], x: float) -> float:
5
    """Evaluate a polynomial f(x) at specified point x and return the value.
6

7
    Arguments:
8
    poly -- the coefficients of a polynomial as an iterable in order of
9
            ascending degree
10
    x -- the point at which to evaluate the polynomial
11

12
    >>> evaluate_poly((0.0, 0.0, 5.0, 9.3, 7.0), 10.0)
13
    79800.0
14
    """
15
    return sum(c * (x**i) for i, c in enumerate(poly))
16

17

18
def horner(poly: Sequence[float], x: float) -> float:
19
    """Evaluate a polynomial at specified point using Horner's method.
20

21
    In terms of computational complexity, Horner's method is an efficient method
22
    of evaluating a polynomial. It avoids the use of expensive exponentiation,
23
    and instead uses only multiplication and addition to evaluate the polynomial
24
    in O(n), where n is the degree of the polynomial.
25

26
    https://en.wikipedia.org/wiki/Horner's_method
27

28
    Arguments:
29
    poly -- the coefficients of a polynomial as an iterable in order of
30
            ascending degree
31
    x -- the point at which to evaluate the polynomial
32

33
    >>> horner((0.0, 0.0, 5.0, 9.3, 7.0), 10.0)
34
    79800.0
35
    """
36
    result = 0.0
37
    for coeff in reversed(poly):
38
        result = result * x + coeff
39
    return result
40

41

42
if __name__ == "__main__":
43
    """
44
    Example:
45
    >>> poly = (0.0, 0.0, 5.0, 9.3, 7.0)  # f(x) = 7.0x^4 + 9.3x^3 + 5.0x^2
46
    >>> x = -13.0
47
    >>> # f(-13) = 7.0(-13)^4 + 9.3(-13)^3 + 5.0(-13)^2 = 180339.9
48
    >>> evaluate_poly(poly, x)
49
    180339.9
50
    """
51
    poly = (0.0, 0.0, 5.0, 9.3, 7.0)
52
    x = 10.0
53
    print(evaluate_poly(poly, x))
54
    print(horner(poly, x))
55