Browsing by Subject "Symmetry"

This thesis provides a program to compute minimal values of polynomials of degree two to get a transcendence measure for e, Napier’s (Neper’s) number. This is an indication of how close to zero some non-zero integer coefficient polynomial can come at e: Since e is transcendental, no such polynomial can actually attain zero. The thesis concentrates on the case of second degree polynomials. The program is written in the R5RS dialect of the programming language Scheme, a reasonably modern LISP version that offers integer and rational arithmetic only limited by the memory. The program is validated by comparison to results computed by hand, using another programming language, J. The program was also rewritten in the programming language C, providing the relevant rational number arithmetic by the library gmp. Performance characteristics of the programs are briefly compared. To appoximate the needed value of e, the programs use continued fractions. Relevant mathematical background for the subject is presented. Symmetries of the grid that represents the polynomial coefficients are used to speed up the computation: The symmetry with respect to the origin effectively halves the number of polynomial evaluations needed. The others employed are interesting but less significant. The idea came from a description of a chess endgame program of Ken Thompson by Jon Bentley, although it is likely to be older. These lead to employing the concept of a layer of polynomials with integer coefficients, the border of a punctured grid, in a sense. Layers turned out to rather nicely fit the handling of the accuracy requirements for e. The complexity of the program is still bounded from below by the number of points in the grid of polynomials, partitioned by the layers, making it bounded from below by a second degree polynomial in H, Omega(H²), where H is the natural number bounding the absolute values of the coefficients of the second and first power of e in the polynomial. The program is reasonably easily changed to handle any transcendental number other than e, in particular, if there is a convenient continued fraction to compute approximations to the number. Strictly speaking, the program does not compute the full transcendence measure, that is, a safe upper bound for each integer coefficient polynomial considered, but if this larger output is actually needed, only a minor change in the program is required.