AI Translated from Chinese

The story begins from yesterday:

The blogger was solving some simple algorithm problems, and one of them was Polynomial Output, which seemed simple so I decided to AC it first. Unfortunately, my C language skills weren’t enough, so I switched to Python. Turns out I still overestimate my abilities; such a simple program requires so many judgments

Simple problem

Generating Polynomials

Referenced from the original problem, but the input/output format is slightly different.

get_polynomial_feature.py

def get_polynomial(*n):
    """Generate polynomial. First parameter is degree, other parameters are coefficients"""
    power, coefficients = n[0], {}
    for i in range(power+1):
        coefficients['a' + str(i+1)] = n[i+1]  # Dictionary to store coefficients

    counter = 0
    polynomial = ""
    while counter <= power:
        poly = coefficients[f'a{counter+1}']
        if abs(poly) != 1:  # Check if absolute value of coefficient is 1
            if counter != 0:  # Check if it's the highest degree term
                if power-counter != 1:  # Check if it's a linear term
                    if counter != power:  # Check if it's a constant term
                        if poly > 0:
                            polynomial += f"+{poly}*x**{power-counter}"
                        elif poly < 0:
                            polynomial += f"{poly}*x**{power-counter}"
                        else:
                            pass
                    else:
                        if poly > 0:
                            polynomial += '+' + str(poly)
                        elif poly < 0:
                            polynomial += '-' + str(poly)
                        else:
                            pass
                else:
                    if poly > 0:
                        polynomial +=  "+" + str(poly) + "*x"
                    elif poly < 0:
                        polynomial +=  "-" + str(poly) + "*x"
                    else:
                        pass
            else:
                if poly > 0:
                    polynomial += f"{poly}*x**{power-counter}"
                elif poly < 0:
                    polynomial += f"{poly}*x**{power-counter}"
                else:
                    pass
        else:
            if counter != 0:
                if power-counter != 1:
                    if counter != power:
                        if poly > 0:
                            polynomial += f"+x**{power-counter}"
                        else:
                            polynomial += f"-x**{power-counter}"
                    else:
                        if poly > 0:
                            polynomial += '+1'
                        else:
                            polynomial += '-1'
                else:
                    if poly > 0:
                        polynomial += "+x"
                    else:
                        polynomial += "-x"
            else:
                if poly > 0:
                    polynomial += f"x**{power-counter}"
                elif poly < 0:
                    polynomial += f"-x**{power-counter}"
                else:
                    pass
        counter += 1
    return polynomial


if __name__ == '__main__':
    print(get_polynomial(3, 5, -1, 0, 11))

Comments on the code above:

  • High EQ: To exercise programming skills, firmly refuse to use third-party libraries;
  • Low EQ: Randomly pile up code, stubbornly reinventing the wheel

Newton’s Method for Polynomial Approximate Roots

Recently reviewing Princeton, so I decided to try Newton’s method.

Theoretical Foundation

Newton’s Method

Assume a is an approximation to the solution of equation $f(x) = 0$. If we set $b = a - f(a) / f’(a)$, then in many cases, $b$ is a better approximation than $a$.

For now, not considering cases where Newton’s method fails (see “The Princeton Calculus Reader” P260~262)

Code

newtons_method.py

from sympy import *

from get_polynomial_feature import *

x = symbols('x')  # x is the symbolic variable
x0 = -0.5  # Initial value
x_list = [x0]
i = 0  # Counter
polynomial_feature = get_polynomial(3, 5, -1, 0, 11)  # Polynomial to solve


def f(x):
    f = eval(polynomial_feature)
    return f


while True:
    if diff(f(x), x).subs(x, x0) == 0:  # subs() replaces variable x with x0; if f'(x0)=0
        print("Extremum point:", x0)
        break
    else:
        x0 = x0 - f(x0) / diff(f(x), x).subs(x, x0)  # Newton's method
        x_list.append(x0)
    if len(x_list) > 1:
        i += 1
        error = abs((x_list[-1] - x_list[-2]) / x_list[-1])  # Calculate error
        if error < 10 ** (-6):
            print(f"After {i} iterations, error less than 10^(-6), error is {error}")
            break
    else:
        pass
print(f"The root of {polynomial_feature} is {x_list[-1]}")

Example run result

After 7 iterations, error less than 10^(-6), error is 4.12656549474007E-8
5*x**3-x**2+11's root is -1.23722554155332

***Repl Closed***

Summary

When Python meets math, it’s quite interesting.

The blogger plans to learn the SymPy and Numpy libraries when there’s a chance.

Source Code Repository

If interested, you can star it (will anyone really star such boring code?)

References

[1] (USA) Adrian Banner. The Princeton Calculus Reader [M]. Beijing: People’s Posts and Telecommunications Press, 2016.

[2] Newton’s Method - Python Program for Iterative Root Finding