Playing with CADO's individual polyselect binaries
 

Since I haven't been able to get the regular Python scripts running correctly, and since even if I could their operation seems extraordinarily inflexible to me, I've taken PZ's suggestion of manually using the polyselect binaries that the scripts delegate to.

Here's my first attempt on the A4788_C195:

[code]~/cado/build/Gravemind/polyselect ∰∂ nice -n 19 ./polyselect -degree 5 -P 5000000 -admax 50000000 -nq 1000 -keep 1000 -v -t 8 -N $(cat num)
# (17c31b8) ./polyselect -degree 5 -P 5000000 -admax 50000000 -nq 1000 -keep 1000 -v -t 8 -N 105720747827131650775565137946594727648048676926428801477497713261333062158444658783837181718187127016255169032147325982158719006483898971407998273736975091062494070213867530300194317862973608499
# Compiled with gcc 4.9.2
# Compilation flags -std=c99 -g -W -Wall -O2 -msse3 -mssse3 -msse4.1 -mpclmul
# Info: initializing 316066 P primes took 16ms, nq=1000
# Info: estimated peak memory=1388.00MB (8 thread(s), batch 20 inversions on SQ)
# thread 0: ad=60
# thread 1: ad=120
# thread 6: ad=180
# thread 3: ad=240
# thread 4: ad=300
# thread 5: ad=360
# thread 2: ad=420
# thread 7: ad=480
# thread 7: ad=540
# thread 4: ad=600
# thread 2: ad=660

# sopt: start size-optimization with polynomials:
# sopt: f_raw = 120*x^5 + -37*x^4 + ...
# sopt: g_raw = 2157420360827950350617*x^1 + -244903953537066202453401636126542860406*x^0
# sopt: with lognorm = 71.270838
Keeping x = 0.260108, f(x) = 2016795408842364209203141872461793618276549461594849023160013414058503962624.000000, f''(x) = 43184121449821530246129924935985504342081783347318205967447779341609100201112371200.000000
# sopt: q-roots of Res(c2,c3) or Res(c2,c3)' = { 0.260108 }
# sopt: 8 values for the translations were computed and added in list_k
# sopt: k = 0 was added list_k
# sopt: It remains 9 values after sorting and removing duplicates
# sopt: Calling improve_list_k with sopt_effort = 0
# sopt: skew0 = 4275.446290
# sopt: skew[0] = 65
# sopt: skew[1] = 529
# sopt: skew[2] = 4275
# sopt: skew[3] = 34572
# sopt: skew[4] = 279558
# sopt: Start processing all k in list_k of length 9
# sopt: better lognorm 65.28 (previous was 71.27) for skew[2] = 4275
# sopt: better lognorm 65.23 (previous was 65.28) for skew[3] = 34572
# sopt: better lognorm 64.54 (previous was 65.23) for skew[4] = 279558
# sopt: better lognorm 64.17 (previous was 64.54) for skew[3] = 34572
# sopt: better lognorm 63.84 (previous was 64.17) for skew[3] = 34572
# sopt: better lognorm 63.72 (previous was 63.84) for skew[3] = 34572
# sopt: end of size-optimization, best polynomial are
# sopt: f_opt = 2760*x^5 + 500106045506149*x^4 + ...
# sopt: g_opt = 2157420360827950350617*x^1 + -244903875353083220572872777923498836651*x^0
# sopt: with lognorm = 63.724256

# Raw polynomial:
# n: 105720747827131650775565137946594727648048676926428801477497713261333062158444658783837181718187127016255169032147325982158719006483898971407998273736975091062494070213867530300194317862973608499
# Y1: 2157420360827950350617
# Y0: -244903953537066202453401636126542860406
# c5: 120
# c4: -37
# c3: 1188753689271031975437528
# c2: 63701574612453595484553171865323265035
# c1: -5231971310990810577211204041041772504
# c0: 39181211010549708386751205216207022495
# raw lognorm 71.27, skew 372185759744.00, alpha 0.09 (proj: -1.21), E 71.36, exp_E 63.14, 1 rroots
# Size-optimized polynomial:
n: 105720747827131650775565137946594727648048676926428801477497713261333062158444658783837181718187127016255169032147325982158719006483898971407998273736975091062494070213867530300194317862973608499
Y1: 2157420360827950350617
Y0: -244903875353083220572872777923498836651
c5: 2760
c4: 500106045506149
c3: 63601533977108612470151786
c2: -2972736829782803317901917056
c1: -77606935545503482645832413970733012323
c0: 556082758789900711444681471769664993163
# lognorm 63.72, skew 1493504.00, alpha 0.76 (proj: -1.34), E 64.49, exp_E 60.24, 3 rroots
[/code]

etc. A fair bit of output is produced per coefficient, and I hope to let this run for a long while, so we'll see what happens. It looks as though I'll have to pass the results file from here to [c]polyselect_ropt[/c] manually.

It might be interesting to combine (e.g.) RichD's GPU sizeopted output with [c]polyselect_ropt[/c] and see what we can come up with.

Given how modular CADO's binaries are (if not the scripts), mayhaps it's worth hacking GPU-Msieve to work with [c]sopt[/c] and [c]polyselect_ropt[/c]? (It seems that [c]polyselect[/c] delegates to [c]sopt[/c]? Or are they totally separate somehow...?)

It finally completed. Looks like somewhere on the order or 12-14 days of a hyper threaded Sandy Bridge quad core... I may have bitten off more than I could truly chew. Oh well, it's complete now. :smile:

Next stage: backups and root opt


[code]# sopt: start size-optimization with polynomials:
# sopt: f_raw = 49999980*x^5 + 87342730*x^4 + ...
# sopt: g_raw = 75531706090637747253061*x^1 + -18409334084348638436044486591897373801*x^0
# sopt: with lognorm = 71.191531
# sopt: find_translations_extra 49394349.452506
# sopt: find_translations_extra -49394329.184788
Not keeping x = -0.236905, f(x) = -881266452414298567385496367451512255442834743137534323397114924012974975049793536.000000, f''(x) = 42362913788293809589383387284727357529134974824061360749448886093185664868476268579334914048.000000
# sopt: q-roots of Res(c2,c3) or Res(c2,c3)' = { -0.236899, -0.236912 }
# sopt: 50 values for the translations were computed and added in list_k
# sopt: k = 0 was added list_k
# sopt: It remains 27 values after sorting and removing duplicates
# sopt: Calling improve_list_k with sopt_effort = 0
# sopt: skew0 = 904.912995
# sopt: skew[0] = 30
# sopt: skew[1] = 165
# sopt: skew[2] = 905
# sopt: skew[3] = 4963
# sopt: skew[4] = 27221
# sopt: Start processing all k in list_k of length 27
# sopt: better lognorm 70.30 (previous was 71.19) for skew[2] = 905
# sopt: better lognorm 70.20 (previous was 70.30) for skew[2] = 905
# sopt: better lognorm 65.96 (previous was 70.20) for skew[3] = 4963
# sopt: better lognorm 65.31 (previous was 65.96) for skew[3] = 4963
# sopt: better lognorm 65.28 (previous was 65.31) for skew[3] = 4963
# sopt: better lognorm 64.25 (previous was 65.28) for skew[2] = 905
# sopt: better lognorm 63.67 (previous was 64.25) for skew[4] = 27221
# sopt: better lognorm 62.84 (previous was 63.67) for skew[2] = 905
# sopt: end of size-optimization, best polynomial are
# sopt: f_opt = 324399870240*x^5 + -80029460397523177360*x^4 + ...
# sopt: g_opt = 75531706090637747253061*x^1 + -18409337811083621201759661159905138289*x^0
# sopt: with lognorm = 62.837342

# Raw polynomial:
# n: 105720747827131650775565137946594727648048676926428801477497713261333062158444658783837181718187127016255169032147325982158719006483898971407998273736975091062494070213867530300194317862973608499
# Y1: 75531706090637747253061
# Y0: -18409334084348638436044486591897373801
# c5: 49999980
# c4: 87342730
# c3: -1202006018615283019865612
# c2: -4361271323601108006810005241882801604
# c1: 5777297089772007359416979193471163928
# c0: 1364051122127173272601888644114195017
# raw lognorm 71.19, skew 2042101760.00, alpha 0.07 (proj: -1.40), E 71.26, exp_E 63.99, 3 rroots
# Size-optimized polynomial:
n: 105720747827131650775565137946594727648048676926428801477497713261333062158444658783837181718187127016255169032147325982158719006483898971407998273736975091062494070213867530300194317862973608499
Y1: 75531706090637747253061
Y0: -18409337811083621201759661159905138289
c5: 324399870240
c4: -80029460397523177360
c3: -17398904458268124477723493
c2: 22144827537958081761266148134238
c1: 888071204935334410586667012400944573
c0: -256020541443086763599669214408591268137446
# lognorm 62.84, skew 361088.00, alpha -1.25 (proj: -1.47), E 61.59, exp_E 59.67, 5 rroots

# Stat: potential collisions=750929.12 (1.55e-01/s)
# Stat: raw lognorm (nr/min/av/max/std): 756882/58.91/70.98/71.82/0.83
# Stat: optimized lognorm (nr/min/av/max/std): 756882/58.91/64.02/67.26/0.76
# Stat: tried 833333 ad-value(s), found 756882 polynomial(s), 756882 size-optimized, 0 rootsieved
# Stat: best logmu after size optimization: 58.91 59.05 59.05 59.23 59.25 59.26 59.33 59.47 59.48 59.54 59.57 59.60 59.62 59.64 59.64 59.69 59.70 59.74 59.78 59.78 59.80 59.81 59.82 59.84 59.85 59.86 59.87 59.88 59.88 59.91 59.92 59.94 59.99 60.00 60.01 60.02 60.02 60.03 60.05 60.06 60.07 60.09 60.09 60.10 60.10 60.10 60.11 60.11 60.11 60.12 60.13 60.13 60.14 60.14 60.15 60.15 60.16 60.17 60.17 60.19 60.19 60.21 60.21 60.22 60.22 60.22 60.22 60.23 60.23 60.23 60.24 60.24 60.26 60.26 60.26 60.27 60.27 60.27 60.29 60.29 60.29 60.30 60.30 60.31 60.32 60.33 60.34 60.34 60.34 60.35 60.35 60.35 60.36 60.36 60.37 60.37 60.38 60.38 60.39 60.39 60.39 60.43 60.43 60.43 60.43 60.44 60.44 60.44 60.44 60.44 60.44 60.44 60.45 60.45 60.46 60.46 60.47 60.47 60.48 60.48 60.48 60.48 60.48 60.48 60.48 60.48 60.49 60.51 60.51 60.51 60.51 60.52 60.52 60.53 60.53 60.54 60.54 60.54 60.54 60.54 60.54 60.55 60.55 60.55 60.56 60.56 60.56 60.56 60.56 60.57 60.57 60.57 60.58 60.58 60.58 60.59 60.59 60.59 60.60 60.60 60.60 60.60 60.60 60.60 60.60 60.61 60.61 60.61 60.61 60.62 60.62 60.62 60.62 60.62 60.63 60.63 60.63 60.63 60.63 60.63 60.63 60.63 60.64 60.65 60.65 60.65 60.66 60.66 60.66 60.66 60.67 60.67 60.67 60.67 60.67 60.67 60.67 60.68 60.68 60.68 60.68 60.69 60.69 60.69 60.69 60.69 60.69 60.70 60.70 60.70 60.70 60.70 60.71 60.71 60.71 60.71 60.71 60.72 60.72 60.72 60.72 60.72 60.72 60.72 60.72 60.72 60.73 60.73 60.73 60.73 60.73 60.73 60.74 60.74 60.74 60.74 60.74 60.74 60.74 60.74 60.75 60.75 60.75 60.75 60.75 60.75 60.75 60.76 60.76 60.76 60.76 60.76 60.76 60.77 60.77 60.77 60.77 60.77 60.77 60.77 60.78 60.78 60.78 60.78 60.78 60.78 60.79 60.79 60.79 60.79 60.79 60.79 60.79 60.79 60.79 60.79 60.80 60.80 60.80 60.80 60.80 60.80 60.80 60.80 60.81 60.81 60.81 60.81 60.81 60.81 60.82 60.82 60.82 60.82 60.82 60.82 60.82 60.82 60.83 60.83 60.83 60.83 60.83 60.83 60.84 60.84 60.84 60.84 60.84 60.84 60.84 60.84 60.84 60.85 60.85 60.85 60.85 60.85 60.85 60.85 60.85 60.85 60.86 60.86 60.86 60.86 60.86 60.86 60.86 60.86 60.86 60.86 60.86 60.86 60.86 60.86 60.86 60.87 60.87 60.87 60.87 60.87 60.87 60.87 60.87 60.88 60.88 60.88 60.88 60.88 60.88 60.88 60.88 60.88 60.88 60.89 60.89 60.89 60.89 60.89 60.89 60.90 60.90 60.90 60.90 60.90 60.90 60.90 60.91 60.91 60.91 60.91 60.91 60.91 60.91 60.91 60.91 60.91 60.91 60.92 60.92 60.92 60.92 60.92 60.92 60.92 60.92 60.92 60.92 60.93 60.93 60.93 60.93 60.93 60.93 60.93 60.93 60.93 60.93 60.93 60.93 60.93 60.93 60.93 60.93 60.94 60.94 60.94 60.94 60.94 60.94 60.94 60.94 60.94 60.94 60.94 60.95 60.95 60.95 60.95 60.95 60.95 60.95 60.95 60.95 60.95 60.95 60.96 60.96 60.96 60.96 60.96 60.96 60.96 60.96 60.96 60.96 60.96 60.96 60.96 60.96 60.96 60.96 60.96 60.97 60.97 60.97 60.97 60.97 60.97 60.97 60.97 60.97 60.97 60.97 60.98 60.98 60.98 60.98 60.98 60.98 60.98 60.98 60.98 60.98 60.98 60.99 60.99 60.99 60.99 60.99 60.99 60.99 60.99 60.99 60.99 60.99 60.99 60.99 60.99 60.99 60.99 61.00 61.00 61.00 61.00 61.00 61.00 61.00 61.00 61.00 61.00 61.00 61.00 61.01 61.01 61.01 61.01 61.01 61.01 61.01 61.01 61.01 61.01 61.01 61.01 61.01 61.01 61.02 61.02 61.02 61.02 61.02 61.02 61.02 61.02 61.02 61.02 61.02 61.02 61.02 61.02 61.02 61.02 61.02 61.03 61.03 61.03 61.03 61.03 61.03 61.03 61.03 61.03 61.04 61.04 61.04 61.04 61.04 61.04 61.04 61.04 61.04 61.04 61.05 61.05 61.05 61.05 61.05 61.05 61.05 61.05 61.05 61.05 61.05 61.05 61.05 61.05 61.05 61.05 61.05 61.06 61.06 61.06 61.06 61.06 61.06 61.06 61.06 61.06 61.07 61.07 61.07 61.07 61.07 61.07 61.07 61.07 61.07 61.07 61.07 61.07 61.07 61.07 61.07 61.07 61.07 61.08 61.08 61.08 61.08 61.08 61.08 61.08 61.08 61.08 61.08 61.08 61.08 61.08 61.09 61.09 61.09 61.09 61.09 61.09 61.09 61.09 61.09 61.09 61.09 61.09 61.09 61.09 61.09 61.09 61.09 61.10 61.10 61.10 61.10 61.10 61.10 61.10 61.10 61.10 61.10 61.10 61.10 61.10 61.10 61.10 61.10 61.10 61.11 61.11 61.11 61.11 61.11 61.11 61.11 61.11 61.11 61.11 61.11 61.11 61.11 61.11 61.11 61.12 61.12 61.12 61.12 61.12 61.12 61.12 61.12 61.12 61.12 61.12 61.12 61.12 61.12 61.12 61.12 61.12 61.12 61.12 61.12 61.12 61.13 61.13 61.13 61.13 61.13 61.13 61.13 61.13 61.13 61.13 61.13 61.13 61.13 61.13 61.13 61.13 61.13 61.14 61.14 61.14 61.14 61.14 61.14 61.14 61.14 61.14 61.14 61.14 61.14 61.14 61.15 61.15 61.15 61.15 61.15 61.15 61.15 61.15 61.15 61.15 61.15 61.15 61.15 61.15 61.15 61.15 61.15 61.15 61.15 61.15 61.15 61.16 61.16 61.16 61.16 61.16 61.16 61.16 61.16 61.16 61.16 61.16 61.16 61.16 61.16 61.16 61.16 61.16 61.16 61.17 61.17 61.17 61.17 61.17 61.17 61.17 61.17 61.17 61.17 61.17 61.17 61.17 61.17 61.17 61.17 61.17 61.17 61.17 61.17 61.17 61.17 61.17 61.18 61.18 61.18 61.18 61.18 61.18 61.18 61.18 61.18 61.18 61.18 61.18 61.18 61.18 61.18 61.18 61.18 61.18 61.18 61.19 61.19 61.19 61.19 61.19 61.19 61.19 61.19 61.19 61.19 61.19 61.19 61.19 61.19 61.19 61.19 61.19 61.19 61.19 61.19 61.19 61.20 61.20 61.20 61.20 61.20 61.20 61.20 61.20 61.20 61.20 61.20 61.20 61.20 61.20 61.20 61.20 61.20 61.20 61.20 61.20 61.20 61.20 61.20 61.20 61.20 61.20 61.20 61.21 61.21 61.21 61.21 61.21 61.21 61.21 61.21 61.21 61.21 61.21 61.21 61.21 61.21 61.21 61.21 61.21 61.21 61.21 61.21 61.21 61.22 61.22 61.22 61.22 61.22 61.22 61.22 61.22 61.22 61.22 61.22 61.22 61.22 61.22 61.22 61.22 61.22 61.22 61.23 61.23 61.23 61.23 61.23 61.23 61.23 61.23 61.23 61.23 61.23 61.23 61.23 61.23 61.23 61.23 61.23 61.23 61.23 61.23 61.23 61.23 61.23 61.23 61.23 61.23 61.24 61.24 61.24 61.24 61.24 61.24 61.24 61.24 61.24 61.24 61.24 61.24 61.24 61.24 61.24 61.24 61.24 61.24 61.24 61.24 61.24 61.24 61.24 61.24 61.24 61.24 61.24 61.25 61.25 61.25 61.25 61.25 61.25 61.25 61.25 61.25 61.25 61.25 61.25 61.25 61.25 61.25 61.25 61.25 61.25 61.25 61.25 61.25 61.25 61.25 61.25 61.25 61.25 61.25 61.25 61.26 61.26 61.26 61.26 61.26 61.26 61.26 61.26 61.26 61.26 61.26 61.26 61.26 61.26 61.26 61.26 61.26 61.26 61.26 61.26 61.26 61.26 61.26 61.26 61.26 61.26 61.26 61.26 61.27 61.27 61.27 61.27 61.27 61.27 61.27 61.27 61.27 61.27 61.27 61.27 61.27 61.27 61.27 61.27 61.27 61.27 61.27 61.27 61.27 61.27 61.27
# Stat: total phase took 4856295.06s
# Stat: size-optimization took 39902.63s[/code]

:censored:. It doesn't save them to file unless you specify -out (which will get you msieve style output). I did not save the stdout. Only the last 5K lines are saved by my tty, which includes roughly 0.014% of the total output.

:bangheadonwall:

Okay, looks like the Python scripts that are otherwise meant to run CADO redirect stdout to file, and then parse said output for the top n lognorm polys itself. That is, the scripts parse out the best n hits, not the polyselect binary itself. The [c]-keep[/c] parameter is meaningless (except for the stats at the end).


For reference, here is the params.c90 documentation:

[code]###########################################################################
# Polynomial selection task with Kleinjung's algorithm (2008)
###########################################################################

tasks.polyselect.degree = 4 # degree of the algebraic polynomial

#tasks.polyselect.threads = 2
# # How many threads to use per polyselect process

tasks.polyselect.P = 10000 # choose lc(g) with two prime factors in [P,2P]
# Setting a large value will most likely find better polynomials,
# but the number of found polynomials will be smaller.
# As a rule of thumb, we want at least 100 found polynomials in total
# (without norm limitation, see below).

tasks.polyselect.admin = 0 # min value for leading coefficient of f(x)
# If not set, the default is 0.

tasks.polyselect.admax = 150e3 # max value for leading coefficient of f(x)

tasks.polyselect.incr = 60 # increment for leading coefficient of f(x)
# This factor is usually a smooth number, which forces projective roots in
# the algebraic polynomial. 60 is a good start, 210 is popular as well.
# Warning: to ensure lc(f) is divisible by incr, admin should be divisible
# by incr too.

# The polynomial selection search time is proportional to the
# length of the search interval, i.e., (admax-admin)/incr.

tasks.polyselect.nrkeep = 40

tasks.polyselect.adrange = 5000 # size of individual tasks
# Polynomial selection is split into several individual tasks. The
# complete range from admin to admax has to be covered for the polynomial
# selection to complete. The number of individual tasks is
# (polsel_admax-polsel_admin)/polsel_adrange. Each such task is issued as
# a workunit to a slave for computation.

tasks.polyselect.nq = 256
# Number of small primes in the leading coefficient of the linear polynomial
# Safe to leave at the default value
# Recommended values are powers of the degree, e.g., 625 for degree 5,
# or 1296 for degree 6. Here 256 = 4^4 thus the leading coefficient of
# the linear polynomial will be q1*q2*q3*q4*p1*p2 where q1,q2,q3,q4 are
# small primes, and P <= p1, p2 < 2*P.[/code]

And also suggested params for a C190:

[code]###########################################################################
# Polynomial selection
###########################################################################

tasks.polyselect.degree = 5

tasks.polyselect.P = 5000000
tasks.polyselect.admax = 5e7
tasks.polyselect.adrange = 5e5
tasks.polyselect.incr = 60
tasks.polyselect.nq = 1000
tasks.polyselect.nrkeep = 1000[/code]

[QUOTE=Dubslow;430433]
It might be interesting to combine (e.g.) RichD's GPU sizeopted output with [c]polyselect_ropt[/c] and see what we can come up with.
[/QUOTE]

I didn't find the python scripts inflexible, once I figured out what each parameter controlled. It was pretty easy to pick a coefficient range, P-value (which correlates to how long to spend on each coeff), and number of polys to keep for root-opt step.

I can post my top ~500 size-opt hits from msieve, if you'd like to try root-opting them. But, my best poly was worse than Rich's, so my hits may just not be very good. Lemme know if you'd like them.

[QUOTE=VBCurtis;432099]I didn't find the python scripts inflexible, once I figured out what each parameter controlled. It was pretty easy to pick a coefficient range, P-value (which correlates to how long to spend on each coeff), and number of polys to keep for root-opt step.
[/quote]

There are endless parameters to tweak, and that's wonderful, but what I consider "inflexible" is the fact that you must set *all* parameters for *all* stages merely to run poly select. I have no idea how many large primes we're going to use thank you very much, and I certainly don't know what filtering density, etc. Essentially, there's no -np or -ns or -nc equivalent.

[QUOTE=VBCurtis;432099]
I can post my top ~500 size-opt hits from msieve, if you'd like to try root-opting them. But, my best poly was worse than Rich's, so my hits may just not be very good. Lemme know if you'd like them.[/QUOTE]
As I recall from the RSA-896 experimental poly search, CADO's root siever is noticeably better than Msieve's. Whether or not that's enough to beat RichD's poly, I'm not sure, but I definitely want to try it for posterity's sake, as well as of course trying CADO's first stage/size opt as has so far been the point here.

Attached is my top 500 hits from 15 GPU-days. Worst norm is 1.46e26, best 1.33e25. Please post best poly or two from CADO root-opt on this file.

jasonp, are the size optimized hit "norms" calculated the same way in Msieve as in CADO? I recall that the Murphy E is definitely different, but it seems that the norms are calculated the same (though CADO gives lognorms, here varying from 60-70, where for reference e^65 ~ 1.695e28).

The recorded best 1000 norms from my first run (whose results are lost, but best lognorms are in the second post of this thread) seem to be from 3.84e25 - 4.97e26.

The norm (last field in the .ms file) is a rectangular integral very similar to the (now obsolete) GGNFS polynomial selection tool. CADO-NFS uses the same integral but in radial coordinates, which leads to a different expression to optimize. The two versions will in general not compute the same answer but the hope is the two norms can rank polynomials in approximately the same way.

CADO-NFS now also uses lattice-reduction based size optimization techniques that can potentially search a larger space than Msieve does. They took our RSA-768 stage 1 dataset and produced a polynomial that was actually better than the one used for the factorization.

The E-values computed by Msieve and CADO-NFS should be exactly comparable now.

[QUOTE=jasonp;432173]The norm (last field in the .ms file) is a rectangular integral very similar to the (now obsolete) GGNFS polynomial selection tool. CADO-NFS uses the same integral but in radial coordinates, which leads to a different expression to optimize. The two versions will in general not compute the same answer but the hope is the two norms can rank polynomials in approximately the same way.

CADO-NFS now also uses lattice-reduction based size optimization techniques that can potentially search a larger space than Msieve does. They took our RSA-768 stage 1 dataset and produced a polynomial that was actually better than the one used for the factorization.

The E-values computed by Msieve and CADO-NFS should be exactly comparable now.[/QUOTE]

1) That's a shame. They at least seem to be nearly the same, within an order of magnitude. (Btw, when you say "identical integral except for the coordinates", I would otherwise interpret that mean same final result, since the value of an integral is independent of the coordinates of computation... presumably you meant something slightly different here)

2) You mean what Msieve calls stage 1, pre-size-optimization, that CADO doesn't bother to separate from size optimization? As in, they used CADO to perform size optimization on Msieve's stage 1 hits?

3) Really? Since when? Which code base changed to match the other? And also I recall that CADO's Murphy E depends on the selected sieve region size, called [c]I[/c] in most places?

Thanks for the awesome knowledge bombs regardless :smile:

1) The value of the integrals would be the same, but remember that we are optimizing very large polynomial expressions, and rectangular vs radial coordinates yield different polynomials that have different gradients and hessians. Our experience is that radial coordinates are better behaved numerically, presumably because polynomial size in the sieving region naturally has radial patterns in it

2) In CADO-NFS the size optimization is considered part of the initial hashtable-based searching. I think they made an exception for the RSA-768 dataset, because all we had was the Msieve stage 1 output and it would have taken quite a while to regenerate it.

3) My memory is hazy on what the difference was; the formula for the E-value does include the sieving bound and sieve area size as parameters, but those are pretty much always chosen to be the same numbers across the different implementations I know about. Actually I remember now they gave different answers because Dickman's function is computed in segments, and the RSA-896 poly search required a few more segments than that version of CADO had tabulated. So we should always have produced the same answers, but in that specific case there was a small bug that they fortunately found quickly

[QUOTE=jasonp;432238]1) The value of the integrals would be the same, but remember that we are optimizing very large polynomial expressions, and rectangular vs radial coordinates yield different polynomials that have different gradients and hessians. Our experience is that radial coordinates are better behaved numerically, presumably because polynomial size in the sieving region naturally has radial patterns in it

2) I believe you are correct, the size optimization is considered part of the initial hashtable-based searching.

3) My memory is hazy on what the difference was; the formula for the E-value does include the sieving bound and sieve area size as parameters, but those are pretty much always chosen to be the same numbers across the different implementations I know about. Actually I remember now they gave different answers because Dickman's function is computed in segments, and the RSA-896 poly search required a few more segments than that version of CADO had tabulated. So we should always have produced the same answers, but in that specific case there was a small bug that they fortunately found quickly[/QUOTE]
1) Again, I think "the" polynomials and their gradients/hessians, the mathematical objects, are "the same" amongst coordinate changes, but I understand you to mean that the numerical computation of the mathematical objects use different numbers (vacuously), and the different numbers tend to behave better from a floating point implementation standpoint, presumably due to some symmetry of the mathematical objects in question?

2) I've just discovered that the binaries produced by building CADO include [c]polyselect[/c], which does "stage 1" and size opt at the same time, as well as a separate [c]sopt[/c] binary which takes "raw" polynomials (presumably the results of the hashtable search...?) for size opting as well, and the equivalent output of either binary can then be fed to [c]polyselect_ropt[/c] whose function should be obvious in this context.

3) I've just started a run of the latter for my Aliquot 4788 efforts, and it seems that it prints the input values to the MurphyE score as well as the score itself, so I guess we can compare against whatever Msieve uses (though I don't really feel like digging through its source, maybe you can comment? Here's an example:)

[code]### root-optimized polynomial 13 ###
# n: 105720747827131650775565137946594727648048676926428801477497713261333062158444658783837181718187127016255169032147325982158719006483898971407998273736975091062494070213867530300194317862973608499
# Y0: -36095620248719813997359851316167411851
# Y1: 287364767617774550963053
# c0: -56088615892505493935209426379951715142392160
# c1: -144890118607664376088446114937854122208
# c2: -8348445372213634471790816940388
# c3: 28963477043189504738748320
# c4: -11102776326974469
# c5: 1725480
# skew: 3267584.000
# # lognorm 63.38, alpha -5.35 (proj -1.53), E 58.03, 3 real roots
# # MurphyE(Bf=1.00e+07,Bg=5.00e+06,area=1.00e+16)=3.27e-15
### Best MurphyE so far is 4.50e-15[/code]

Incidentally, I'm really a fan of taking the log of all these numbers with large exponents. Wouldn't it be nicer for everyone if we also used logMe (and lognorm obviously) in place of the raw MurphyE and norm?

[QUOTE=VBCurtis;432166]Attached is my top 500 hits from 15 GPU-days. Worst norm is 1.46e26, best 1.33e25. Please post best poly or two from CADO root-opt on this file.[/QUOTE]

Err... I may be misinterpreting the .ms file (been years since I worked with one), but... were you searching for degree 6 polys...?

Nope, definitely degree 5.

[QUOTE=VBCurtis;432317]Nope, definitely degree 5.[/QUOTE]

Could you help me spot my error then?

Here's the code (msieve/gnfs/poly/poly_skew.c):

[code]static void sizeopt_callback_log(uint32 deg, mpz_t *alg_coeffs, mpz_t *rat_coeffs,
double sizeopt_norm, double projective_alpha,
void *extra)
{
uint32 i;
FILE *mfile = (FILE *)extra;

for (i = deg; (int32)i >= 0; i--)
gmp_fprintf(mfile, "%Zd ", alg_coeffs[i]);

gmp_fprintf(mfile, "%Zd %Zd %.2lf %le\n", rat_coeffs[1],
rat_coeffs[0], projective_alpha,
exp(projective_alpha) * sizeopt_norm);
fflush(mfile);
}[/code]

And here's the first three lines of your file I downloaded:

[code]971700 273849234706546 225962405583700796407442 -84054861767065123330509949866 -29517104017082095088929447630073626321 3262277732054109330095369390256411899572767 1660633240515241123 -40487932918725137061265492892721380626 -1.59 1.338783e+25
628488 25807572840266955 303999146710932834523652 -3119549682722644921895399900207 -14123903064615248232023501030205940006 48260972168255749244473149176534441863659851 29048885255261071969 -44174601963086515462086860672795847500 -1.77 1.614272e+25
546960 -5605325602623737 -1955381755454195745958 6621960285938958484871001763602 -1854857638980877962690869298795624892 -1032866398309654043779803193974135126928581602 4835900641980806243 -45419351810482876976420189466026262897 -1.37 1.842692e+25[/code]

I count 8 coefficients per line (plus the two scores), so it definitely looks like degree 6... :unsure:

No idea, sir- but the polys in msieve.log are degree 5, and I am certain I didn't invoke the degree=6 flag in the command line. Msieve doesn't pick degree 6 on its own...

Try running -npr on the file from msieve to convince yourself?

[QUOTE=Dubslow;432334]Could you help me spot my error then?
[/QUOTE]

Sure, deg 5 polys have 6 coefficients. (I'm sure you'll be kicking yourself for that :smile:)

[QUOTE=jcrombie;432383]Sure, deg 5 polys have 6 coefficients. (I'm sure you'll be kicking yourself for that :smile:)[/QUOTE]

Aww crud. I usually have a feeling that I'm doing something stupid, hence all the ellipses, and... well I wasn't wrong, about the feeling stupid part at least... ugh.

Thanks :smile: Obviously I'm rusty.

General note -- before realizing that CADO can and will happily read Msieve format size opted polys, I wrote a short Python script to convert formats. Unfortunately, it took me a few days (only 20 minutes of actual effort) to discover that having more than one blank line separating polys in the file is beyond CADO's ability to parse. Just a heads up, and for future reference.

Okay, here's the results from my cluster:censored: of messing around with CADO.

A search of LCs from 0-10M (only those divisible by 60, per CADO default) (roughly 3 CPU days), then passing the top 500 size norm hits to CADO rootopt, produced the following top 5 polys (I have all 500 available):

[code]n: 105720747827131650775565137946594727648048676926428801477497713261333062158444658783837181718187127016255169032147325982158719006483898971407998273736975091062494070213867530300194317862973608499
skew: 62078976.0
c0: 2078861482606939262732348788772234729500066505
c1: -81452413435682187177974315743754413126
c2: -1256739981486858947548697657268
c3: -22396930453004670461906
c4: -263922878237933
c5: 2547840
Y0: -33388556319178604525067212126801994606
Y1: 96874809441465515717599
# MurphyE (Bf=1.00e+07,Bg=5.00e+06,area=1.00e+16) = 1.16e-14
# lognorm 59.06

n: 105720747827131650775565137946594727648048676926428801477497713261333062158444658783837181718187127016255169032147325982158719006483898971407998273736975091062494070213867530300194317862973608499
skew: 57720832.0
c0: -17160072336623445558486491447680793046654059460
c1: -1654348007928800032775401504767487803936
c2: 28947429876755966986844833643017
c3: 946553263211289715531399
c4: -3924318619058088
c5: 5516640
Y0: -47025518976311715704856348352373464079
Y1: 176154525925723359784759
# MurphyE (Bf=1.00e+07,Bg=5.00e+06,area=1.00e+16) = 8.85e-15
# lognorm 61.5

n: 105720747827131650775565137946594727648048676926428801477497713261333062158444658783837181718187127016255169032147325982158719006483898971407998273736975091062494070213867530300194317862973608499
skew: 25583616.0
c0: -685992159184539512613548044513984252041883140
c1: 134610898781364897801610290286626955999
c2: 7109903060621761009580559757488
c3: -238819588636731179920283
c4: -8746008810620432
c5: 53587200
Y0: -27519388373819676833051410839329305921
Y1: 1839671560743535632496133
# MurphyE (Bf=1.00e+07,Bg=5.00e+06,area=1.00e+16) = 8.51e-15
# lognorm 60.22

n: 105720747827131650775565137946594727648048676926428801477497713261333062158444658783837181718187127016255169032147325982158719006483898971407998273736975091062494070213867530300194317862973608499
skew: 14503936.0
c0: -65698494574585654869665676718988331163562112
c1: 97332536632788185915561208310178169236
c2: -371931585676372953901140963249
c3: -870401356387883046717037
c4: -910339736204828
c5: 3553440
Y0: -41220600122861670237999244493991322477
Y1: 118715258484298437008683
# MurphyE (Bf=1.00e+07,Bg=5.00e+06,area=1.00e+16) = 7.93e-15
# lognorm 60.58

n: 105720747827131650775565137946594727648048676926428801477497713261333062158444658783837181718187127016255169032147325982158719006483898971407998273736975091062494070213867530300194317862973608499
skew: 58310656.0
c0: -18280501391805263953245129313762844281481248662
c1: 646040699763406262391803981659489087237
c2: 36712368286900883073060051628284
c3: -529564887634112218615187
c4: -6061192475321092
c5: 10035120
Y0: -33492176102045778534763735786623971315
Y1: 2449174464852706655304347
# MurphyE (Bf=1.00e+07,Bg=5.00e+06,area=1.00e+16) = 7.81e-15
# lognorm 61.1[/code]

Note that I had originally searched 0-50M (roughly two weeks CPU time), but lost the results in one of the greater :censored:ups of recent times, and no doubt the top 5 would have been substantially better using those results, if not a better top 1. (Edit: 0-50M produced 1 hit below lognorm 59, and 33 total below 60; 0-10M produced the same hit below 59, and only 6 others below 60.)

And secondly, I also ran an identical rootsieve of VBCurtis' top 500 Msieve GPU stage 1 and sizeopt hits (~2 weeks GPU+CPU time?), which produced the following top 5 (again, all 500 available upon request):

[code]n: 105720747827131650775565137946594727648048676926428801477497713261333062158444658783837181718187127016255169032147325982158719006483898971407998273736975091062494070213867530300194317862973608499
skew: 146997248.0
c0: -131414304044478185366394231747951586868400235157
c1: 4029601527701148189310418069976213395221
c2: 30149105678605166244788285142337
c3: -268424081661710226278041
c4: -1338222885809036
c5: 1505028
Y0: -37095662305095086253404478445430777250
Y1: 9762700048268674463
# MurphyE (Bf=1.00e+07,Bg=5.00e+06,area=1.00e+16) = 9.54e-15
# lognorm 61.02

n: 105720747827131650775565137946594727648048676926428801477497713261333062158444658783837181718187127016255169032147325982158719006483898971407998273736975091062494070213867530300194317862973608499
skew: 115310592.0
c0: 72654783078207317663016087360899076774225974549
c1: -13183316839111760341950789781721971964575
c2: -29276900156268889268041437680369
c3: 1780141248353293122105769
c4: 1020057436955814
c5: 912600
Y0: -40999253791772676218846852869952650362
Y1: 4848218606269847041
# MurphyE (Bf=1.00e+07,Bg=5.00e+06,area=1.00e+16) = 8.51e-15
# lognorm 62.36

n: 105720747827131650775565137946594727648048676926428801477497713261333062158444658783837181718187127016255169032147325982158719006483898971407998273736975091062494070213867530300194317862973608499
skew: 81494016.0
c0: -98942718328354657571921135515000654102809275280
c1: -1094123364329131040120216467254391237420
c2: 65859755925338247464662996618032
c3: -1618738878212462977815579
c4: -4830711805039576
c5: 687420
Y0: -43389796499263425737859091822712579063
Y1: 47084851870118530061
# MurphyE (Bf=1.00e+07,Bg=5.00e+06,area=1.00e+16) = 8.25e-15
# lognorm 62.48

n: 105720747827131650775565137946594727648048676926428801477497713261333062158444658783837181718187127016255169032147325982158719006483898971407998273736975091062494070213867530300194317862973608499
skew: 81166336.0
c0: 45557711067352835790870412530520906044046352000
c1: 538182327666734598053665140544142650228
c2: -35247498407001430812508122651020
c3: -85598128594418788150756
c4: 4204857918193797
c5: 1081860
Y0: -39627605646451711638391781283296477421
Y1: 9440158732784987191
# MurphyE (Bf=1.00e+07,Bg=5.00e+06,area=1.00e+16) = 8.21e-15
# lognorm 61.04

n: 105720747827131650775565137946594727648048676926428801477497713261333062158444658783837181718187127016255169032147325982158719006483898971407998273736975091062494070213867530300194317862973608499
skew: 54214656.0
c0: 21724609728591871248210729947586274756512302379
c1: -317862276216193685941919711583925203153
c2: -10170954010451741993810971872497
c3: 13022944940440380507497
c4: -8295877607702306
c5: 1175280
Y0: -38976584207204966069784298467971861060
Y1: 559932214212309221
# MurphyE (Bf=1.00e+07,Bg=5.00e+06,area=1.00e+16) = 8.17e-15
# lognorm 61.54
[/code]

I haven't done any test sieving on any poly, CADO or otherwise, for this search.

Note that CADO's default "rootsieve effort" is 5, on a scale of 1-10; one line of inquiry for the next poly search is to see if effort 10 over say, 50 or 100 hits is better than effort 5 over 500 hits.

And btw, I definitely vote for taking the log of Murphy E in much the same way CADO takes the log of the sizeopt norm.

CADO size optimization of MSIEVE polynomial
 

[QUOTE=Dubslow;432240]2) I've just discovered that the binaries produced by building CADO include [c]polyselect[/c], which does "stage 1" and size opt at the same time, as well as a separate [c]sopt[/c] binary which takes "raw" polynomials (presumably the results of the hashtable search...?) for size opting as well, and the equivalent output of either binary can then be fed to [c]polyselect_ropt[/c] whose function should be obvious in this context.
[/QUOTE]

On your machine, what is the location of the separate [c]sopt[/c] binary? I use cado-nfs-2.2.0 and can't find [c]sopt[/c] binary anywhere.

I need help size-optimizing the following msieve poly ([URL]http://stdkmd.com/nrr/c.cgi?q=68881_216[/URL]) in cado:
[code]# Murphy_E = 4.296e-12
# expecting poly E from 4.51e-012 to > 5.19e-012; sieved all c5 < 564
n: 6964469412395724414400887219282737626566096536914345017855771078382532118955354745772117936678678317022004114419569353913029298176668228168002524415033
Y0: -719974750345759133972843201212
Y1: 2509148016863593
c0: -645947407201258180676614400938960976175
c1: 123446188733445544772289511592948
c2: 18319373780518695347898595
c3: -2567126999321415502
c4: -18908689182
c5: 36
skew: 32970491.17[/code]

I don't think I can recreate this polynomial in cado because Y1=2509148016863593=7.31.10223.11447.98809 and 98809>2*11447. Maybe somebody knows the way to recreate it?

When I pass the msieve polynomial to [c]polyselect_ropt[/c], the best output is:
[code]
# Best polynomial found:
n: 6964469412395724414400887219282737626566096536914345017855771078382532118955354745772117936678678317022004114419569353913029298176668228168002524415033
Y0: -719974797818859686216157669956
Y1: 2509148016863593
c0: -74098902767640540677544413831582460335175
c1: 3710094808934559412128037232637690
c2: 120979270663498122139675645
c3: -1007248783970378638
c4: -22314290622
c5: 36
skew: 63127552.000
# lognorm 48.59, alpha -7.30 (proj -1.24), E 41.28, 5 real roots
# MurphyE(Bf=1.00e+07,Bg=5.00e+06,area=1.00e+16)=4.12e-12
[/code]

After that, I can change the skew to 83758158.21476 (that increases the lognorm I assume) which gives Murphy_E=4.14415907e-12. ([URL]http://myfactors.mooo.com/[/URL], Optimal Skew)

I didn't do actual sieving, just trying to compare Murphy_E scores.
[COLOR=green][/COLOR]

[code]bill@Gravemind⌚2258 ~/cado/build/Gravemind/polyselect ∰∂ ls | grep -v "[Cc]1"
cadops.bash
CMakeFiles
cmake_install.cmake
CTestTestfile.cmake
dlpolyselect
libpolyselect_common.a
Makefile
ms_to_cado.py
num
polyselect
polyselect_ropt
rotate
rotate_all
sopt
sort_polys.py
sys

[/code]

Importing other polys can be a bit difficult, you'll have to play around with the individual binaries to figure out how they work (or read code or view the -help output).

For instance I wrote this small bash script to glue things together for a start-to-stop polyselect run:

[code]bill@Gravemind⌚2300 ~/cado/build/Gravemind/polyselect ∰∂ cat cadops.bash
#! /usr/bin/env bash

n=51703345090678007603283094883953312763757798669035713906213433384993369348322376058745609326491127794881496108288948261956762322783390589392048698391

name=C149_3408_1631
threads=8

# Typically you should copy these from cado/parameters/factor/params.cxxx
deg=5
P=500000
admin=0
admax=20000000
incr=60
nq=1000
keep=900

##############################################################################

# http://stackoverflow.com/a/9194117/1497645
# Round admin up to nearest multiple of incr
admin=$(( ((admin + incr - 1) / incr) * incr ))

f1="$name.sizeopt"
f2="$name.rootopt"

nice -n 19 ./polyselect -degree "$deg" -P "$P" -admax "$admax" -nq "$nq" -keep "$keep" -t "$threads" -N "$n" | tee "$f1"

cmd="./sort_polys.py $f1 $keep"

$cmd && nice -n 19 ./polyselect_ropt -inputpolys "$f1.sorted" -t "$threads" | tee "$f2"

./sort_polys.py "$f2"
[/code]

It also makes use of the following small Python script, which is largely lifted from CADO's own Python glue code (which I otherwise found too inflexible for my taste):

[code]bill@Gravemind⌚2300 ~/cado/build/Gravemind/polyselect ∰∂ cat sort_polys.py
#! /usr/bin/env python3

import sys

sys.path.append('/home/bill/cado/scripts/cadofactor')

from cadotask import Polynomials, PolynomialParseException

def read_blocks(input):
""" Return blocks of consecutive non-empty lines from input

Whitespace is stripped; a line containing only whitespace is
considered empty. An empty block is never returned.

>>> list(Polysel1Task.read_blocks(['', 'a', 'b', '', 'c', '', '', 'd', 'e', '']))
[['a', 'b'], ['c'], ['d', 'e']]
"""
block = []
for line in input:
line = line.strip()
if line:
block.append(line)
else:
if block:
yield block
block = []
if block:
yield block

def parse_block(block):
try:
poly = Polynomials(block)
except:
print(block)
raise
if not poly:
raise ValueError("useless poly:\n{}".format(block))
return poly

def sort(filename, keep=None):
lst = []
with open(filename, 'r') as f:
for block in read_blocks(f):
if '### root-optimized polynomial' in block[0]:
# For whatever reason, all output from `polyselect_ropt` is prefaced by "# ",
# so remove it
block = [line[2:] for line in block if '# Stat:' not in line]
# The very last output poly has no blank line between it and stat output, so
# knock that out here
lst.append(parse_block(block))
elif any('# Size-optimized polynomial:' in line for line in block):
lst.append(parse_block(block))
print("Read {} polys from {}".format(len(lst), filename))
have_murphyE = bool(lst[0].MurphyE)
if have_murphyE:
if not all(poly.MurphyE for poly in lst):
raise ValueError("Some polys have MurphyE, some don't")
key, reverse = lambda poly: poly.MurphyE, True
else:
if any(poly.MurphyE for poly in lst):
raise ValueError("Some polys have MurphyE, some don't")
key, reverse = lambda poly: poly.lognorm, False
lst.sort(key=key, reverse=reverse)
if keep:
lst = lst[:keep]
with open(filename+'.sorted', 'w') as g:
for poly in lst:
poly = '\n'.join(l for l in str(poly).splitlines() if '(x) =' not in l)
g.write(poly+'\n\n')

if __name__ == '__main__':
filename = sys.argv[1]
keep = None
if len(sys.argv) > 2:
keep = int(sys.argv[2])
sort(filename, keep)
[/code]

Note that ./polyselect does both first stage and size opt at the same time. You'll again have to play with the binary/review code to figure out how to separate the two stages (I believe it is possible, but I might be remembering incorrectly).

sopt binary --> resolved

@Dubslow
[QUOTE]Importing other polys can be a bit difficult, you'll have to play around with the individual binaries to figure out how they work (or read code or view the -help output).
[/QUOTE]It actually was very easy (thank you, Shi Bai!) My mistake was that I used an official release CADO-NFS-2.2.0. After installing a development version from a git repository I found sopt library where it should have been. After that
[code]
/home/max/Desktop/cado-nfs/build/Phenom/polyselect/sopt -inputpolys /home/max/Desktop/cado-nfs/work/c140_1/raw.txt -sopteffort 1000 -v >> /home/max/Desktop/cado-nfs/work/c140_1/sopt.txt
[/code]does what I wanted to do.
Thank you to everybody!