Computing real roots of real polynomials ... and now for real!

This site serves as an addendum to the article Computing real roots of real polynomials ... and now for real! (PDF).

Statically compiled binaries of the development version of RS & ANewDsc are now available for Linux, Mac OSX and Windows platforms:
  Linux • Mac OSX • Windows
All binaries are compiled for 64-bit platforms. In case of problems or incompatibilities with your hardware architecture, please contact the authors.

Known bug: The implementation of the (experimental) option -i (or --intprog) is faulty and can deliver wrong results under certain circumstances. We are currently investigating the situation.

RS-ANewDsc <https://anewdsc.mpi-inf.mpg.de/>

USAGE:
        ./test_descartes [OPTIONS] <filename>

        -h, --help
                this information
        -s, --subdivision [0/1/2]
                    0: [default] subdivision at pseudo-admissible points
                    1: classical RS' constant-memory DFS traversal
                    2: DFS traversal with full caching
        -n, --newton [0/1/2]
                    0: only bisection, with relative transformations between nodes (supports constant memory)
                    1: [default] bisection and Newton-Tests, full caching
                    2: only bisection, full caching
        -t, --truncate [0/1/2]
                    0: compute all intermediate polynomials to full degree
                    1: [default] perform only partial Taylor shifts if Newton steps succeed
                    2: [EXPERIMENTAL] try to detect local degrees and truncate polynomials
                       without taking into account multiplicity guesses from Newton-Tests
        -o, --optimize-var [0/1]
                    0: full transformations x -> x+1 in sign variation computations
                    1: [default] shortcut transformations x -> x+1 in sign variation computations
                       as soon as var != 0 and var != 1 are detected
        -p, --maxprec P
                    switch to exact arithmetic once the working precision in interval arithmetic
                    exceeds P relative bits [default: 2^30]
        -S, --sqrfree [0/1]
                    0: [default] the polynomial is not guaranteed to be square-free;
                       test for square-freeness and, if necessary, compute the square-free part
                    1: the polynomial is guaranteed to be square-free;
                       if the condition is violated, the algorithm will not terminate
        -e, --exact [0/1]
                    0: [default] switch to exact arithmetic only if <maxprec> is reached
                    1: enable heuristics to switch to exact arithmetic depending on the structure
                       of the intervals and the polynomial
        -d, --double [0/1]    [EXPERIMENTAL for some combinations]
                    0: [default] use MPFI-based arbitrary precision interval arithmetic only
                    1: use a hardware precision stage before switching to MPFI
        -i, --intprog [0/1]    [EXPERIMENTAL]
                    0: solve on intervals (-2^B, 0) and (0, 2^B), where B is a root bound
                    1: [default] solve on intervals that form a geometric progression of the form
                       +/- (1 + sum (2^(2^k), k=0..i-1), 1 + sum (2^(2^k), k=0..i))
        -v, --verbose N
                    set verbosity level to N [default: 0]
                           -2: completely quiet
                           -1: only print the isolating intervals to stdout
                            0: print warnings and few statistics
                          > 0: various debug and progress messages in different levels

INPUT FILE FORMAT:
        The input file encodes a single dense univariate polynomial with integer coefficients.
        The first line contains the degree of the polynomial,
        the following lines contain one coefficient each, starting from the trailing coefficient.
        E.g., the input
                2
                -3
                0
                1
        encodes the polynomial x^2 - 3 of degree 2.
        No comments and/or blank lines are allowed in the input.

CONFIGURATIONS:
        Not all options are fully compatible with each other and/or tested in all combinations.
        The main configurations are:
         - classical RS without exact arithmetic:
           ./test_descartes --subdivision 1 --newton 0 --truncate 0 --sqrfree 0 --intprog 0
         - classical RS with exact arithmetic (approximately the version in Maple 2015):
           ./test_descartes --subdivision 1 --newton 0 --truncate 0 --maxprec 8192 --exact 1 --intprog 0
         - ADsc:
           ./test_descartes --subdivision 1 --newton 0 --truncate 0 --sqrfree 0 --intprog 0
         - ANewDsc:
           ./test_descartes
         - ANewDsc without truncation:
           ./test_descartes --truncate 0