Appears in collection : 2023 - T3 - WS1 - Fundamental algorithms and algorithmic complexity

In modern numerical computations, real numbers are approximated with floating-point numbers, of the form $s2^e$, where $s$ and $e$ are integers with a fixed precision. This representation is compact and can represent numbers with small and large magnitudes. In this talk, we will generalize this idea to approximate univariate polynomial functions with piecewise polynomials of the form $s(X)X^e$ where $s$ is a polynomial of fixed degree and e is an integer. Using tools such as the Newton polygon, this representation can be computed efficiently both in theory and in practice. Moreover, it can be used to efficiently evaluate and find roots approximations of a high-degree polynomial.