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

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

We apologize for the current layout and lack of explanations; we will update this website as soon as possible and include more details.

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


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

nested Mignotte polynomials: $\prod_{i=1}^4 \Big(x^{n/4+1} - \big((2^{\tau/8}-1)x^2 - 1)^{2i}\Big)$
degree bitsize MPSolve CF Sage RS RS
treesize
ADsc ADsc
treesize
ANewDsc ANewDsc
treesize
260 38
260 79 2.6 0.4 0.2 0.9 272 0.9 279 0.6 144
260 100 2.6 0.6 0.3 1.2 342 1.2 346 0.3 123
260 160 3.1 1.4 0.3 2.2 550 2.3 565 0.9 166
260 220 3.3 2.4 error 3.6 750 3.6 757 0.3 149
260 320 4.0 4.6 6.6 1084 5.9 1106 1.8 191
260 440 4.6 8.2 12.5 1494 11.3 1506 0.4 172
260 640 5.8 14.9 20.8 2168 19.2 2196 0.9 272
260 900 9.3 28.2 39.5 3052 40.7 3071 0.7 228
260 1280 13.2 54.9 77.9 4330 66.4 4361 1.6 374
260 1800 23.6 112.2 184.9 6092 151.2 6115 2.0 426
260 2560 33.7 222.6 301.2 8660 254.0 8684 3.7 573
260 3620 62.2 444.8 573.9 12242 >600 NaN 2.8 384
260 5120 98.0 >600 >600 NaN 7.7 578
260 7240 173.7 12.3 738
260 10240 248.0 31.4 1434
260 14480 451.3 44.6 1903
260 20480 >600 98.5 2603
260 28960 89.9 2148
260 40960 341.2 4899
260 57920 482.4 6726
260 81920 >600 NaN
nested Mignotte polynomials: $\prod_{i=1}^4 \Big(x^{n/4+1} - \big((2^{\tau/8}-1)x^2 - 1)^{2i}\Big)$
degree bitsize MPSolve CF Sage RS RS
treesize
ADsc ADsc
treesize
ANewDsc ANewDsc
treesize
132 140 1.1 0.1 1.0 0.2 266 0.2 271 0.1 147
180 140 1.6 0.2 1.2 0.7 346 0.6 351 0.1 128
260 140 2.7 1.0 1.9 1.6 484 1.7 491 0.4 162
364 140 6.0 4.6 2.2 5.7 660 5.9 670 0.4 146
516 140 9.5 21.6 3.3 18.0 926 18.0 934 0.8 172
724 140 38.7 102.1 5.3 73.9 1288 74.9 1301 1.5 153
1028 140 67.8 565.0 error 230.3 1820 232.4 1830 7.1 180
1452 140 156.8 >600 >600 NaN >600 NaN 5.7 174
2052 140 283.6 13.1 219
2900 140 >600 24.0 204
4100 140 88.4 217
5796 140 175.6 234
8196 140 394.0 249
11588 140 >600 NaN
Chebyshev polynomials of the first kind: $T_0(x)=1;\quad T_1(x)=x;\quad T_{i+1}(x)=2x T_i(x)-T_{i−1}(x)$
degree bitsize MPSolve CF Sage RS RS
treesize
ADsc ADsc
treesize
ANewDsc ANewDsc
treesize
128 321 1.2 0.1 1.0 0.2 295 0.2 206 0.2 189
181 456 3.3 0.2 1.2 0.4 401 0.5 289 0.4 268
256 646 10.3 0.6 1.5 1.1 576 1.1 370 1.1 347
362 916 33.1 1.6 2.1 2.9 787 3.1 543 3.3 524
512 1297 143.6 5.0 2.8 10.7 1141 10.7 707 9.6 668
724 1836 546.3 16.4 6.8 22.8 1566 32.6 1089 29.6 1032
1024 2599 >600 59.1 7.4 101.3 2270 120.2 1417 117.3 1323
1448 3677 224.5 15.3 292.6 3107 355.0 1911 374.8 2048
2048 5202 >600 35.4 >600 NaN >600 NaN >600 NaN
Chebyshev polynomials of the second kind: $U_0(x)=1;\quad U_1(x)=2x;\quad U_{i+1}(x)=2x U_i(x)-U_{i−1}(x)$
degree bitsize MPSolve CF Sage RS RS
treesize
ADsc ADsc
treesize
ANewDsc ANewDsc
treesize
128 322 1.1 0.1 0.1 0.2 297 0.2 212 0.2 195
181 457 3.1 0.2 0.1 0.4 403 0.5 279 0.5 258
256 647 10.4 0.6 0.2 1.1 578 1.3 374 1.2 341
362 917 32.9 1.6 0.8 2.7 789 3.2 551 3.1 513
512 1298 142.8 5.1 0.8 8.8 1143 10.5 709 9.7 666
724 1837 554.2 17.1 2.5 24.3 1560 32.2 1077 29.8 1030
1024 2599 >600 59.8 4.2 95.7 2266 120.2 1428 117.4 1325
1448 3677 213.6 11.7 240.6 3105 355.2 1915 385.6 2058
2048 5203 >600 29.2 >600 NaN >600 NaN >600 NaN
clustered random polynomials with $\Theta(\sqrt n)$ real roots: $f^2-1$ for $f = \sum_i a_i \binom{n}{i}^{1/2} x^i / \sqrt{i+1}$ with $a_i$ drawn from a normal Gaussian distribution, rounded to $\mathbb{Z}[x]$
degree bitsize MPSolve CF Sage RS RS
treesize
ADsc ADsc
treesize
ANewDsc ANewDsc
treesize
16 1025 0.1 0.0 0.1 0.1 2040 0.1 2049 0.0 104
22 1024 0.1 0.1 0.2 0.3 5114 0.3 5134 0.1 292
32 1026 0.2 0.1 0.2 0.2 2088 0.2 2097 0.0 91
44 1025 0.4 0.3 0.5 0.5 4196 0.6 4213 0.0 200
64 1025 0.8 1.1 0.8 1.3 6528 1.2 6551 0.1 386
90 1026 1.3 2.1 0.9 2.0 5396 1.9 5416 0.1 310
128 1026 2.6 7.0 0.3 3.9 6498 4.0 6519 0.1 317
180 1026 5.1 31.8 1.7 13.7 12616 14.9 12654 0.5 717
256 1025 8.8 98.1 1.1 29.6 13546 31.4 13578 0.8 754
362 1025 17.5 354.1 1.9 75.1 17230 78.4 17275 1.4 923
512 1026 34.4 >600 2.1 114.4 13256 117.8 13291 2.4 705
724 1026 79.8 12.1 >600 NaN >600 NaN 8.6 1263
1024 1027 173.2 20.9 18.5 1698
1448 1026 389.6 50.7 28.7 1206
2048 1027 >600 558.7 100.2 2230
2746 1027 375.2 106.8 1466
3640 1027 >600 198.9 1515
4832 1026 330.2 1523
6428 1026 577.4 1512
8594 1027 >600 NaN
clustered random polynomials with $\Theta(\log n)$ real roots: $f^2-1$ for $f = \sum_i a_i x^i$ with $a_i$ drawn uniformly at random from $\{-2^\tau, \dots, 2^\tau\}$
degree bitsize MPSolve CF Sage RS RS
treesize
ADsc ADsc
treesize
ANewDsc ANewDsc
treesize
16 1025 0.1 0.0 0.1 0.1 2066 0.1 2078 0.0 101
22 1026 0.1 0.0 0.1 0.1 1032 0.1 1037 0.0 91
32 1027 0.2 0.1 0.2 0.2 2132 0.2 2142 0.0 146
44 1027 0.4 0.3 0.5 0.6 4300 0.7 4322 0.1 277
64 1027 0.7 0.4 0.6 0.6 2088 0.6 2097 0.1 134
90 1027 1.3 1.2 0.8 1.4 3122 1.5 3135 0.1 186
128 1027 2.3 4.6 1.1 3.3 4304 3.4 4323 0.2 253
180 1028 4.2 6.0 1.2 3.0 2068 3.1 2075 0.1 143
256 1028 8.7 34.8 1.7 13.4 4608 13.8 4625 0.3 232
362 1028 17.9 184.0 2.8 49.7 8484 51.1 8508 0.9 441
512 1029 33.5 339.2 3.1 71.5 6544 73.0 6568 1.3 395
724 1029 67.4 284.6 3.3 43.9 2068 44.4 2074 0.9 144
1024 1029 141.8 >600 8.2 288.5 6648 292.4 6670 5.2 419
1448 1030 305.1 20.3 >600 NaN >600 NaN 10.1 428
2048 1030 >600 16.4 13.6 292
2896 1030 42.2 37.9 407
4096 1031 119.4 49.8 271
5792 1031 229.6 171.3 421
8192 1031 >600 345.4 467
11584 1031 489.9 307
16384 1032 >600 NaN
Hermite polynomials
degree bitsize MPSolve CF Sage RS RS
treesize
ADsc ADsc
treesize
ANewDsc ANewDsc
treesize
128 869 0.8 0.2 0.1 0.1 288 0.2 194 0.2 197
181 1313 2.0 0.4 0.2 0.5 409 0.5 273 0.4 265
256 1977 5.1 1.1 0.4 1.1 570 1.1 373 1.3 364
362 2968 17.6 3.2 0.7 3.1 805 3.2 515 2.6 507
512 4443 58.8 10.3 1.5 8.6 1122 8.8 723 7.6 714
724 6631 237.3 38.0 3.8 28.8 1589 28.3 1006 22.6 1022
1024 9875 >600 140.5 11.9 88.3 2237 91.0 1427 79.6 1396
1448 14668 490.4 34.0 337.7 3164 342.6 2020 242.1 1967
2048 21748 >600 68.7 >600 NaN >600 NaN >600 NaN
Laguerre polynomials
degree bitsize MPSolve CF Sage RS RS
treesize
ADsc ADsc
treesize
ANewDsc ANewDsc
treesize
128 743 0.8 0.2 0.1 0.2 290 0.2 196 0.2 191
181 1134 1.9 0.4 0.2 0.5 403 0.5 275 0.4 263
256 1723 5.1 1.0 0.3 1.1 572 1.2 377 1.3 370
362 2608 18.0 3.1 0.8 3.0 802 3.1 519 2.5 502
512 3933 58.4 9.2 1.4 8.8 1126 8.8 735 7.6 720
724 5910 239.0 32.1 4.1 27.9 1585 29.1 1004 22.7 1008
1024 8854 >600 118.1 12.9 88.9 2239 91.9 1425 79.7 1408
1448 13223 424.7 >600 337.3 3156 342.4 2028 239.8 1949
2048 19702 >600 >600 NaN >600 NaN >600 NaN
Legendre polynomials of the first kind
degree bitsize MPSolve CF Sage RS RS
treesize
ADsc ADsc
treesize
ANewDsc ANewDsc
treesize
128 572 1.1 0.1 0.1 0.2 297 0.2 208 0.2 193
181 809 3.4 0.2 0.1 0.5 403 0.5 290 0.5 266
256 1153 10.5 0.7 0.2 1.2 582 1.1 374 1.2 339
362 1630 33.0 1.7 0.8 3.0 789 3.2 543 3.3 518
512 2315 149.5 6.0 0.9 10.2 1143 10.6 705 9.7 662
724 3274 540.9 21.6 2.7 27.8 1564 32.6 1085 29.4 1022
1024 4640 >600 79.0 4.5 118.2 2272 120.9 1416 117.2 1325
1448 6562 286.7 11.7 340.1 3111 354.6 1911 385.9 2054
2048 9291 >600 30.3 >600 NaN >600 NaN >600 NaN
Mignotte polynomials with rational center of the cluster: $x^n - \big((2^{\tau/2}-1)x-1\big)^2$
degree bitsize MPSolve CF Sage RS RS
treesize
ADsc ADsc
treesize
ANewDsc ANewDsc
treesize
129 10 0.2 0.0 1.1 0.7 644 0.7 646 0.0 34
129 16 0.2 0.0 0.1 1.1 1044 1.1 1052 0.0 49
129 22 0.2 0.0 0.1 1.6 1434 1.5 1441 0.0 42
129 32 0.4 0.0 0.1 2.6 2084 2.7 2094 0.0 34
129 44 0.3 0.1 0.1 4.4 2864 4.3 2874 0.0 47
129 64 0.7 0.1 0.2 8.1 4164 7.6 4176 0.1 36
129 90 0.5 0.1 0.3 14.6 5854 14.6 5866 0.1 40
129 128 1.2 0.3 0.5 26.2 8326 25.1 8340 0.1 40
129 180 1.1 0.5 0.7 53.3 11706 52.2 11720 0.1 42
129 256 2.5 0.9 1.3 100.0 16648 76.9 16784 0.2 40
129 362 2.5 1.9 1.9 203.3 23538 166.2 23726 0.1 44
129 512 5.9 3.8 3.9 378.5 33292 293.8 33550 0.4 47
129 724 6.0 7.2 6.6 >600 NaN >600 NaN 0.5 46
129 1024 16.5 16.7 16.2 1.3 51
129 1448 15.9 35.2 31.6 1.3 48
129 2048 43.4 78.4 error 3.3 53
129 2896 41.8 162.8 3.2 50
129 4096 111.7 431.8 8.1 55
129 5792 108.1 >600 7.9 52
129 8192 274.7 20.8 57
129 11584 262.2 19.7 54
129 16384 577.7 46.0 59
129 23170 >600 42.7 56
129 32768 96.8 61
129 46340 93.5 58
129 65536 223.9 63
129 92680 211.1 60
129 131072 503.0 65
129 185362 494.7 62
129 262144 >600 NaN
Mignotte polynomials with rational center of the cluster: $x^n - \big((2^{\tau/2}-1)x-1\big)^2$
degree bitsize MPSolve CF Sage RS RS
treesize
ADsc ADsc
treesize
ANewDsc ANewDsc
treesize
129 14 0.2 0.0 1.1 0.8 914 1.0 916 0.0 45
181 14 0.4 0.0 1.3 2.5 1278 2.6 1281 0.1 43
257 14 0.7 0.1 1.6 7.6 1810 7.7 1813 0.1 48
363 14 1.7 0.1 2.1 25.9 2552 26.3 2556 0.1 55
513 14 2.9 0.2 2.4 87.6 3602 89.1 3606 0.2 51
725 14 7.6 0.5 3.4 334.9 5072 337.4 5077 0.5 52
1025 14 13.8 1.1 4.8 >600 NaN >600 NaN 0.7 60
1449 14 42.1 1.9 11.0 1.6 65
2049 14 78.5 7.2 12.8 2.9 60
2897 14 258.6 21.0 87.6 6.3 78
4097 14 486.3 67.6 85.8 11.2 82
5793 14 >600 154.7 error 24.0 56
8193 14 224.3 43.2 69
11585 14 >600 107.8 79
16385 14 188.1 90
23171 14 488.0 76
32769 14 >600 NaN
Mignotte polynomials with irrational center of the cluster: $x^n - \big((2^{\tau/4}-1)x^2-1\big)^2$
degree bitsize MPSolve CF Sage RS RS
treesize
ADsc ADsc
treesize
ANewDsc ANewDsc
treesize
129 10 0.2 0.3 1.0 0.4 639 0.4 644 0.1 74
129 16 0.2 0.7 0.0 0.8 1049 0.8 1057 0.1 109
129 22 0.1 1.1 0.1 1.1 1441 1.2 1449 0.1 100
129 32 0.2 2.4 0.1 1.8 2095 1.9 2108 0.1 141
129 44 0.3 4.0 0.1 2.8 2883 3.1 2896 0.0 123
129 64 0.4 7.8 0.1 5.0 4191 5.0 4210 0.1 110
129 90 0.5 14.9 0.2 8.2 5893 8.6 5908 0.1 152
129 128 0.9 29.4 0.4 15.4 8387 15.4 8411 0.2 168
129 180 0.9 55.6 0.5 30.5 11795 30.9 11818 0.1 147
129 256 2.2 117.1 1.0 56.8 16773 47.6 16799 0.3 195
129 362 2.2 223.9 1.4 97.4 23715 98.9 23734 0.2 155
129 512 5.1 444.9 2.9 219.8 33549 174.2 33570 0.9 182
129 724 5.0 >600 4.3 462.6 47335 376.1 47464 0.4 168
129 1024 13.9 9.7 >600 NaN >600 NaN 1.6 206
129 1448 14.0 16.1 0.9 169
129 2048 35.5 42.7 6.6 199
129 2896 35.0 78.7 2.2 185
129 4096 95.2 error 15.7 204
129 5792 93.0 8.8 196
129 8192 238.0 23.0 183
129 11584 226.7 19.7 231
129 16384 450.9 52.7 193
129 23170 495.7 86.9 313
129 32768 >600 132.2 223
129 46340 105.1 246
129 65536 293.3 243
Mignotte polynomials with irrational center of the cluster: $x^n - \big((2^{\tau/4}-1)x^2-1\big)^2$
degree bitsize MPSolve CF Sage RS RS
treesize
ADsc ADsc
treesize
ANewDsc ANewDsc
treesize
129 14 0.2 0.5 1.1 0.6 913 0.8 917 0.0 80
181 14 0.3 2.0 1.3 1.9 1275 2.1 1282 0.1 107
257 14 0.6 10.7 1.6 5.6 1805 5.8 1813 0.2 106
363 14 1.4 53.6 2.1 17.9 2551 18.5 2563 0.3 123
513 14 2.4 317.1 2.8 55.9 3593 55.7 3605 0.6 131
725 14 6.2 >600 3.8 195.4 5073 198.7 5088 1.2 137
1025 14 11.5 5.3 >600 NaN >600 NaN 2.9 145
1449 14 33.6 9.8 5.6 161
2049 14 63.8 12.9 8.3 156
2897 14 198.3 68.4 21.3 179
4097 14 365.6 75.8 38.4 190
5793 14 >600 error 67.6 211
8193 14 126.1 208
11585 14 509.2 222
16385 14 >600 NaN
resultants of random dense bivariate integer polynomials
degree bitsize MPSolve CF Sage RS RS
treesize
ADsc ADsc
treesize
ANewDsc ANewDsc
treesize
100 2070 0.1 0.0 0.8 0.0 26 0.0 22 0.0 17
144 2076 0.1 0.0 1.0 0.0 36 0.0 32 0.0 20
196 2094 0.2 0.0 1.2 0.1 26 0.1 24 0.0 11
256 2108 0.3 0.1 0.1 0.1 52 0.1 48 0.1 33
324 2086 0.9 0.1 1.7 0.1 36 0.1 34 0.1 20
400 2126 1.2 0.2 2.0 0.2 38 0.2 36 0.2 30
484 2125 1.7 0.1 2.4 0.2 28 0.2 28 0.2 17
576 2125 2.5 0.3 2.7 0.4 40 0.4 38 0.3 28
676 2157 3.2 0.4 3.3 0.6 52 0.6 46 0.5 35
784 2160 4.3 0.8 3.7 1.1 64 0.9 56 0.8 48
900 2195 5.5 0.7 5.0 1.1 58 1.1 52 0.7 28
1024 2216 7.4 0.9 2.5 1.6 66 1.5 60 1.2 41
1156 2221 9.0 1.4 6.4 1.6 50 1.5 44 1.4 32
1296 2228 11.2 1.9 7.0 2.2 70 2.5 62 2.1 42
1444 2205 14.2 2.1 9.8 2.5 52 2.5 50 2.3 33
1600 2243 17.6 2.7 11.7 3.0 60 3.0 50 2.5 34
polynomials with coefficients drawn uniformly at random from $\{-2^\tau, \dots, 2^\tau\}$
degree bitsize MPSolve CF Sage RS RS
treesize
ADsc ADsc
treesize
ANewDsc ANewDsc
treesize
128 1024 0.1 0.0 1.1 0.0 16 0.0 16 0.0 16
181 1024 0.1 0.0 1.2 0.0 17 0.0 17 0.0 17
256 1024 0.2 0.0 1.3 0.1 16 0.1 16 0.0 16
362 1024 0.5 0.0 0.1 0.1 12 0.0 12 0.0 12
512 1024 0.9 0.1 2.3 0.2 22 0.2 20 0.2 20
724 1024 1.5 0.1 2.9 0.5 28 0.5 26 0.5 26
1024 1024 2.5 0.3 4.1 0.6 20 0.6 18 0.5 18
1448 1024 5.0 0.3 4.7 0.5 12 0.4 12 0.4 12
2048 1024 9.8 0.9 8.4 1.6 18 1.7 16 1.7 16
2896 1024 19.2 4.2 19.8 5.7 30 5.7 26 5.9 26
4096 1024 37.5 2.7 29.1 3.8 14 3.7 14 3.5 14
5792 1024 75.2 47.3 60.4 28.6 34 28.7 32 32.0 32
8192 1024 159.4 22.1 183.5 36.0 24 36.3 22 36.5 22
11585 1024 293.2 54.1 >600 72.3 31 73.1 29 73.0 29
16384 1024 578.9 376.6 275.1 46 280.9 40 279.0 40
23170 1024 >600 >600 190.0 18 183.3 16 183.2 16
32768 1024 >600 NaN >600 NaN >600 NaN
monic polynomials with coefficients drawn uniformly at random from $\{-2^\tau, \dots, 2^\tau\}$, leading coefficient one
degree bitsize MPSolve CF Sage RS RS
treesize
ADsc ADsc
treesize
ANewDsc ANewDsc
treesize
128 1024 0.1 0.0 1.6 1.1 2352 0.7 2348 0.0 6
181 1024 0.2 0.0 2.9 2.1 3085 1.9 3083 0.0 8
256 1024 0.3 0.0 5.8 3.5 3086 3.4 3084 0.0 8
362 1024 0.5 0.0 13.7 6.4 3088 6.2 3086 0.1 8
512 1024 0.9 0.1 227.2 12.0 3084 11.9 3082 0.1 9
724 1024 1.5 0.1 63.3 21.0 2762 21.0 2758 0.3 23
1024 1024 2.6 0.7 >600 38.8 2582 39.2 2578 1.2 38
1448 1024 5.0 0.7 90.2 3098 91.6 3096 0.9 19
2048 1024 9.4 4.3 179.7 3104 182.3 3098 3.2 27
2896 1024 19.3 3.3 315.1 2746 322.9 2742 3.4 13
4096 1024 37.6 8.5 >600 NaN >600 NaN 14.8 31
5792 1024 71.9 13.8 28.6 29
8192 1024 148.6 31.6 24.9 13
11585 1024 297.0 156.6 76.6 24
16384 1024 579.3 279.2 143.1 13
23170 1024 >600 >600 404.1 13
32768 1024 >600 NaN
monic polynomials with coefficients drawn uniformly at random from $\{-2^\tau, \dots, 2^\tau\}$, leading and trailing coefficient one
degree bitsize MPSolve CF Sage RS RS
treesize
ADsc ADsc
treesize
ANewDsc ANewDsc
treesize
128 1024 0.1 0.0 5.2 1.3 2736 0.8 2736 0.0 4
181 1024 0.1 0.0 2.8 1.9 2745 1.6 2743 0.0 7
256 1024 0.3 0.0 27.0 3.2 2738 3.1 2738 0.0 4
362 1024 0.5 0.0 11.5 5.0 2354 4.9 2352 0.1 9
512 1024 0.8 0.0 225.7 12.1 3082 12.0 3082 0.1 4
724 1024 1.5 0.1 470.5 18.8 2460 18.8 2460 0.1 4
1024 1024 2.6 0.2 184.1 45.8 3084 46.5 3082 0.3 9
1448 1024 4.8 0.3 >600 90.2 3078 91.1 3078 0.3 4
2048 1024 9.7 0.6 158.2 2740 160.1 2740 0.5 4
2896 1024 19.2 1.2 295.0 2568 300.3 2568 1.0 4
4096 1024 38.0 10.3 569.9 2482 576.9 2480 10.1 21
5792 1024 76.3 9.4 >600 NaN >600 NaN 13.0 11
8192 1024 155.7 44.2 48.6 21
11585 1024 309.4 54.5 75.5 15
16384 1024 >600 >600 419.7 41
23170 1024 523.1 20
32768 1024 >600 NaN
Wilkinson-like polynomials with rational non-dyadic roots: $\prod_{i=1}^n (x-\frac{i}{n+1})$
degree bitsize MPSolve CF Sage RS RS
treesize
ADsc ADsc
treesize
ANewDsc ANewDsc
treesize
128 888 1.2 0.1 1.0 0.2 267 0.2 148 0.2 146
181 1248 4.0 0.2 1.3 1.0 427 0.5 236 0.6 235
256 2189 14.0 0.7 1.6 1.6 524 1.7 280 1.7 278
362 2968 45.4 1.8 2.5 5.2 843 5.5 599 13.1 597
512 4394 213.6 7.5 3.9 17.3 1037 17.6 541 53.8 536
724 6763 >600 28.3 6.2 59.4 1674 60.5 1177 185.8 1159
1024 10112 105.3 15.4 232.7 2062 233.4 1057 >600 NaN
1448 14131 378.2 >600 >600 NaN >600 NaN
2048 22566 >600
Wilkinson polynomials: $\prod_{i=1}^n (x-i)$
degree bitsize MPSolve CF Sage RS RS
treesize
ADsc ADsc
treesize
ANewDsc ANewDsc
treesize
128 721 1.3 0.0 1.0 0.1 269 0.2 203 0.3 199
181 1107 4.1 0.1 1.3 0.3 378 0.6 301 1.6 288
256 1690 14.0 0.2 1.5 1.3 526 2.0 382 4.4 391
362 2567 45.6 0.4 2.5 6.9 742 5.2 582 22.8 562
512 3882 213.0 1.1 3.6 14.9 1039 20.5 726 116.0 733
724 5847 >600 3.9 6.7 98.7 1467 59.0 1134 177.9 1069
1024 8777 12.6 14.1 219.1 2064 268.7 1416 >600 NaN
1448 13130 42.1 33.5 >600 NaN >600 NaN
2048 19589 153.5 82.6

Alexander Kobel, Max-Planck-Institut für Informatik, Saarbrücken, Germany
Fabrice Rouillier, INRIA Paris & Université Pierre et Marie Curie Paris VI & Institut de Mathématiques de Jussieu Paris Rive Gauche, Paris, France
Michael Sagraloff, Max-Planck-Institut für Informatik, Saarbrücken, Germany

Last modified: Mon May 2 11:11:32 CEST 2016