mersenneforum.org Improving Polynomials With CADO-NFS and Msieve Tools
 Register FAQ Search Today's Posts Mark Forums Read

 2020-12-03, 18:33 #1 EdH     "Ed Hall" Dec 2009 Adirondack Mtns 23·3·5·31 Posts Improving Polynomials With CADO-NFS and Msieve Tools Forum member Max0526 has been "spinning" polynomials for various projects for a while now with noted success. With his permission, this thread will be an attempt to bring that procedure and a script based on it to light. It will discuss the steps Max uses and the script that is being developed. Steps used to "spin" polynomials, to find better ones: Step 1a: Compile a list of polynomials to "spin" in the CADO-NFS format, with one empty line in between each. Example of CADO-NFS polynomials (step 1a): Code: # norm 3.955008e-15 alpha -10.525549 e 1.263e-15 rroots 4 skew: 20719118.62 c0: 762197820414584056355396858170301594531724356640 c1: 282438427720261099877094537227345105837822 c2: 10694897894745705918703999452376463 c3: -1550660754332995251622323056 c4: -74517626418497602049 c5: 2925078878448 c6: 45360 Y0: -66175567287217599588365775303500573 Y1: 284594098468775320577861 # norm 3.905700e-15 alpha -10.006285 e 1.255e-15 rroots 6 skew: 14837476.76 c0: -48435262418969769514610791143274851397285135584 c1: 33010637664063929475758747878463381423956 c2: 10301020259326875457171150530613793 c3: -1575557113665696390916906444 c4: -73281005399858760929 c5: 2948001010128 c6: 45360 Y0: -66175543317848844252701950274313570 Y1: 284594098468775320577861 Step 1b: Replace all the "# norm..." lines with "n: . Example with changes (step 1b): Code: n: 105846620118997527795673923816494096564538879551655755948941841181964527982935974672375053674066636955526325748344171237200759216056332103525354574858042635016393534861038293333116405407677018242280598840418822711 skew: 20719118.62 c0: 762197820414584056355396858170301594531724356640 c1: 282438427720261099877094537227345105837822 c2: 10694897894745705918703999452376463 c3: -1550660754332995251622323056 c4: -74517626418497602049 c5: 2925078878448 c6: 45360 Y0: -66175567287217599588365775303500573 Y1: 284594098468775320577861 n: 105846620118997527795673923816494096564538879551655755948941841181964527982935974672375053674066636955526325748344171237200759216056332103525354574858042635016393534861038293333116405407677018242280598840418822711 skew: 14837476.76 c0: -48435262418969769514610791143274851397285135584 c1: 33010637664063929475758747878463381423956 c2: 10301020259326875457171150530613793 c3: -1575557113665696390916906444 c4: -73281005399858760929 c5: 2948001010128 c6: 45360 Y0: -66175543317848844252701950274313570 Y1: 284594098468775320577861 Step 2a: Duplicate the entire list of polynomials into a new file. Step 2b: Change the signs for all the c#'s in the new file. Do NOT alter the Y#'s. Step 2c: Append the new file to the original remembering the empty lines. Example of polynomial file with all changes (step 2c): Code: n: 105846620118997527795673923816494096564538879551655755948941841181964527982935974672375053674066636955526325748344171237200759216056332103525354574858042635016393534861038293333116405407677018242280598840418822711 skew: 20719118.62 c0: 762197820414584056355396858170301594531724356640 c1: 282438427720261099877094537227345105837822 c2: 10694897894745705918703999452376463 c3: -1550660754332995251622323056 c4: -74517626418497602049 c5: 2925078878448 c6: 45360 Y0: -66175567287217599588365775303500573 Y1: 284594098468775320577861 n: 105846620118997527795673923816494096564538879551655755948941841181964527982935974672375053674066636955526325748344171237200759216056332103525354574858042635016393534861038293333116405407677018242280598840418822711 skew: 14837476.76 c0: -48435262418969769514610791143274851397285135584 c1: 33010637664063929475758747878463381423956 c2: 10301020259326875457171150530613793 c3: -1575557113665696390916906444 c4: -73281005399858760929 c5: 2948001010128 c6: 45360 Y0: -66175543317848844252701950274313570 Y1: 284594098468775320577861 n: 105846620118997527795673923816494096564538879551655755948941841181964527982935974672375053674066636955526325748344171237200759216056332103525354574858042635016393534861038293333116405407677018242280598840418822711 skew: 20719118.62 c0: -762197820414584056355396858170301594531724356640 c1: -282438427720261099877094537227345105837822 c2: -10694897894745705918703999452376463 c3: 1550660754332995251622323056 c4: 74517626418497602049 c5: -2925078878448 c6: -45360 Y0: -66175567287217599588365775303500573 Y1: 284594098468775320577861 n: 105846620118997527795673923816494096564538879551655755948941841181964527982935974672375053674066636955526325748344171237200759216056332103525354574858042635016393534861038293333116405407677018242280598840418822711 skew: 14837476.76 c0: 48435262418969769514610791143274851397285135584 c1: -33010637664063929475758747878463381423956 c2: -10301020259326875457171150530613793 c3: 1575557113665696390916906444 c4: 73281005399858760929 c5: -2948001010128 c6: -45360 Y0: -66175543317848844252701950274313570 Y1: 284594098468775320577861 Step 3a: Run CADO-NFS size optimization (sopt) against the polynomials using an effort of 0, and save the results into a size-opts file. Step 3b: Run CADO-NFS size optimization (sopt) against the polynomials using an effort of 1, and append the results to the size-opts file. Step 3c: Run CADO-NFS size optimization (sopt) against the polynomials using an effort of 10, and append the results to the size-opts file. Step 3d: Run CADO-NFS size optimization (sopt) against the polynomials using an effort of 100, and append the results to the size-opts file. Step 3e: Examine the size-opts file and extract all the unique polynomials based on the exp_E value in the "# lognorm..." line. Step 3f: Create a duplicate list with swapped signs, as before. Step 3g: Append both lists to the previous list of polynomials remembering the empty line spacing between polynomials. Step 4a: Run CADO-NFS root optimization (polyselect_ropt) against the polynomials using an effort of 0, and save the results into a root-opts file. Step 4b: Run CADO-NFS root optimization (polyselect_ropt) against the polynomials using an effort of 0.01, and append the results to the root-opts file. Step 4c: Examine the root-opts file and extract all the unique polynomials based on the MurphyE value at the end of the "# MurphyE(..." line. Step 4d: Create a duplicate list with swapped signs, as before. Step 4e: Append both lists to the previous list of polynomials remembering the empty line spacing between polynomials. Note: The preceding steps can be rerun multiple times, and/or the values of 1 and 2 can be used for the effort. After the runs, duplicate, change signs and append as before. Step 5a: Run CADO-NFS root optimization (polyselect_ropt) against the polynomials using an effort of 10, and save the results into a root-opts file. Step 5b: Examine the end of the root-opts file to find the "# Best polynomial found..." section. The process used by Max0526 continues with further steps, some which include Msieve and other programs. These additional steps will be added at a later time.
 2020-12-03, 18:34 #2 EdH     "Ed Hall" Dec 2009 Adirondack Mtns 23×3×5×31 Posts In the previous post, a method of finding better polynomials from already good ones was described. With help from Max0526 and swellman, I have written a bash script following the above steps. The script itself is provided below this description of use. This Bash script, written for linux, uses external programs from the CADO-NFS package, specifically sopt and polyselect_ropt, both from within the polyselect folder within the specific build directory for the machine on which CADO-NFS was compiled. The script has been written in a manner to work from a subdirectory of cado-nfs, e.g. polyspin (this will be used for the examples below). In its present form, the script will search the build directory to find the name to use in its program calls. Presently, this search will fail if there are multiple directories within cado-nfs/build. Failure is displayed as no values being returned for the steps and a nearly immediate return to the calling prompt. In this case, the variable "bfolder" in the script should be changed to reflect the directory (from the build directory) to be used when running the script. Note: If the CADO-NFS default build was used, the value shown by "echo $HOSTNAME" should be the name of the folder to use, but if the default was changed during the build, it could be different. That's why the current method is in place. The script will need a file containing a list of the polynomials to "spin." This should be formatted in the following way: Code: # norm 3.979386e-15 alpha -10.165470 e 1.273e-15 rroots 6 skew: 17426583.98 c0: -424107143151389852394750951199674677445544423680 c1: 88091499630191140625983913523351724991412 c2: 17615204059869713970942209146992473 c3: -901787453125978278572433036 c4: -99339672027298490849 c5: 2419474999248 c6: 45360 Y0: -66176095990481059463373702221884018 Y1: 284594098468775320577861 This is the typical way CADO-NFS polynomials are expressed in posts in the forum threads. Note: Multiple polynomials can be supplied in the list, but make sure a single blank line separates all polynomials: Code: . . . Y0: -66176095990481059463373702221884018 Y1: 284594098468775320577861 # norm 3.979386e-15 alpha -10.165470 e 1.273e-15 rroots 6 skew: 17426583.98 c0: -424107143151389852394750951199674677445544423680 . . . To run the script, once the polynomials file is created, from within the polyspin directory, use either: Code: $ bash  or, simply: Code: $bash  The latter of these invocations, will cause the script to prompt for the file and composite. An example of calling the script with the above single polynomial, and its subsequent output: Code: ~/Math/cado-nfs/polyspin$ bash polyspin.sh polys 105846620118997527795673923816494096564538879551655755948941841181964527982935974672375053674066636955526325748344171237200759216056332103525354574858042635016393534861038293333116405407677018242280598840418822711 Full exp_E list from sopteffort 0, 1, 10, 100: 49.90 49.74 As of ropteffort=1, Murphy_E scores: 1.269e-15 1.618e-16 1.270e-15 1.120e-15 1.243e-15 Full exp_E list from sopteffort 0, 1, 10, 100: 49.90 49.74 49.89 49.97 As of ropteffort=2, Murphy_E scores: 1.269e-15 1.618e-16 1.270e-15 1.120e-15 1.243e-15 1.327e-15 1.143e-15 1.107e-15 1.191e-15 1.123e-15 Full exp_E list from sopteffort 0, 1, 10, 100: 49.90 49.74 49.89 49.97 50.04 49.86 49.99 50.14 49.83 As of ropteffort=10, Murphy_E scores: 1.269e-15 1.618e-16 1.270e-15 1.120e-15 1.243e-15 1.327e-15 1.143e-15 1.107e-15 1.191e-15 1.123e-15 1.146e-15 1.140e-15 1.117e-15 1.224e-15 1.250e-15 1.109e-15 1.129e-15 1.157e-15 1.110e-15 1.136e-15 1.159e-15 # Best polynomial found: n: 105846620118997527795673923816494096564538879551655755948941841181964527982935974672375053674066636955526325748344171237200759216056332103525354574858042635016393534861038293333116405407677018242280598840418822711 Y0: -66175507466676477845668491119429817 Y1: 284594098468775320577861 c0: -626081313147184760199029071786307655596384808000 c1: 114155706290582003827015758825221679754150 c2: 9698330805779200485429519766575815 c3: -1612013188384034013354246592 c4: -71413365342160076609 c5: 2982285821808 c6: 45360 skew: 15664544.853 # lognorm 59.63, E 49.29, alpha -10.34 (proj -2.10), 4 real roots # MurphyE(Bf=1.000e+07,Bg=5.000e+06,area=1.000e+16)=1.327e-15 Full run time: 1:03:10 The "Best polynomial found" is the CADO-NFS assessment of all the previous polynomials starting from the original set that was given when the script was invoked. It is output to both file (BestPoly) and screen. There are several intermediate files that can be reviewed during and after the run, depending on the variable "keepintfiles" setting. These files include the outputs of size and root optimizations as well as the temporary files used for negating the c# values. The rawset file contains the initial and all subsequent polynomials that were added. The original polynomial file is not changed. The script for polyspin.sh: Code: #/bin/bash/############################################################### # This script is based on work developed by Max0526 on mersenneforum.org. # It is designed to refine polynomials in a manner to increase their # MurphyE score by running them through sizeopt and rootopt procedures. # # To use this script, create a directory within your cado-nfs folder, # e.g. "polyspin" and place this script and your file containing the # polynomials within that folder. You can then use: # bash polyspin.sh # Or, you can simply use: # bash polyspin.sh # and enter the filename and composite when prompted. # # This script searches the cado-nfs/build directory for the folder where # the programs are compiled. If there are more than one folder within # the build directory, unexpected behaviour may me be witnessed. In such # case, the script should be edited in this manner: # bfolder= # # Discussion of this process and script can be found in this thread: # ########################################################################### # filename for original polys inpolys=$1 # composite for polys composite=$2 # finds build directory to use for programs # change this if more than one folder in build directory bfolder=$(ls ../build) # keep final intermediate files # no means remove all intermediate files at end keepintfiles=yes # Initialize several variables MurphyEs="" expEs="" c5="" c6="" SECONDS=0 # Create tempneg file with negated c values function negatecs { rm tempneg 2>/dev/null exec <"temp2neg" while read line do case$line in "n: "*) echo $line >> tempneg ;; "skew: "*) echo$line >> tempneg ;; "Y0: "*) echo $line >> tempneg ;; "Y1: "*) echo$line >> tempneg echo "" >> tempneg ;; "c"*) test=${line:4} if [[$test = -* ]] then echo ${line:0:4}${line:5} >> tempneg else echo ${line:0:4}-${line:4} >> tempneg fi ;; esac done } # Run size optimization at effort 0, 1, 10, 100 function sizeopt { rm soptset 2>/dev/null for s in 0 1 10 100 do ../build/$bfolder/polyselect/sopt -inputpolys rawset -sopteffort$s -v >> soptset done # Filter size optimized polys and add to rawset with negations rm temp2neg 2>/dev/null exec <"soptset" while read line do check=0 case $line in "n: "*) n=$line ;; "Y0: "*) Y0=$line ;; "Y1: "*) Y1=$line ;; "c0: "*) c0=$line ;; "c1: "*) c1=$line ;; "c2: "*) c2=$line ;; "c3: "*) c3=$line ;; "c4: "*) c4=$line ;; "c5: "*) c5=$line ;; "c6: "*) c6=$line ;; "skew: "*) skew=$line ;; "# lognorm "*) expE=${line:23:5} case$expEs in *"$expE"*) check=1 ;; esac if [$check -eq 0 ] then expEs="${expEs}${expE} " echo "$n" >>temp2neg echo "$skew" >>temp2neg echo "$c0" >>temp2neg echo "$c1" >>temp2neg echo "$c2" >>temp2neg echo "$c3" >>temp2neg echo "$c4" >>temp2neg if [${#c5} -gt 0 ] then echo "$c5" >>temp2neg fi if [${#c6} -gt 0 ] then echo "$c6" >>temp2neg fi echo "$Y0" >>temp2neg echo "$Y1" >>temp2neg echo "" >>temp2neg fi ;; esac done echo "Full exp_E list from sopteffort 0, 1, 10, 100:" echo "$expEs" if [ -e temp2neg ] then negatecs cat temp2neg >>rawset cat tempneg >>rawset fi } # Accept input for polyfile and/or composite, # if not provided on command line if [ ${#inpolys} -lt 1 ] then printf "polys file: " read inpolys in fi if [${#composite} -lt 1 ] then printf "composite: " read composite in fi # Create rawset file from polyfile rm rawset 2>/dev/null rm temp2neg 2>/dev/null exec <"$inpolys" while read line do case$line in "skew:"*) echo "n: $composite" >> rawset echo$line >> rawset ;; "c0:"*) echo $line >> rawset ;; "c1:"*) echo$line >> rawset ;; "c2:"*) echo $line >> rawset ;; "c3:"*) echo$line >> rawset ;; "c4:"*) echo $line >> rawset ;; "c5:"*) echo$line >> rawset ;; "c6:"*) echo $line >> rawset ;; "Y0:"*) echo$line >> rawset ;; "Y1:"*) echo $line >> rawset echo "" >> rawset ;; esac done # Create set of polys to negate c values cp rawset temp2neg # negate polys negatecs # Append tempneg to rawset cat tempneg >> rawset # Run initial size optimization sizeopt # Run root optimization on rawset at effort 0, 0.01, 1, 2, 10 for r in 1 2 10 do rm roptset 2>/dev/null ../build/$bfolder/polyselect/polyselect_ropt -t $(nproc) -inputpolys rawset -area 1.00e+16 -Bf 10000000 -Bg 5000000 -v -ropteffort 0 >> roptset 2>/dev/null ../build/$bfolder/polyselect/polyselect_ropt -t $(nproc) -inputpolys rawset -area 1.00e+16 -Bf 10000000 -Bg 5000000 -v -ropteffort 0.01 >> roptset 2>/dev/null ../build/$bfolder/polyselect/polyselect_ropt -t $(nproc) -inputpolys rawset -area 1.00e+16 -Bf 10000000 -Bg 5000000 -v -ropteffort$r >> roptset 2>/dev/null # Filter root optimized polys and add uniques to rawset with negations rm temp2neg 2>/dev/null exec <"roptset" while read line do check=0 case $line in "n: "*) n=$line ;; "Y0: "*) Y0=$line ;; "Y1: "*) Y1=$line ;; "c0: "*) c0=$line ;; "c1: "*) c1=$line ;; "c2: "*) c2=$line ;; "c3: "*) c3=$line ;; "c4: "*) c4=$line ;; "c5: "*) c5=$line ;; "c6: "*) c6=$line ;; "skew: "*) skew=$line ;; "# MurphyE("*) MurphyE=${line##*=} case$MurphyEs in *"$MurphyE"*) check=1 ;; esac if [$check -eq 0 ] then MurphyEs="${MurphyEs}${MurphyE}" echo "$n" >>temp2neg echo "$skew" >>temp2neg echo "$c0" >>temp2neg echo "$c1" >>temp2neg echo "$c2" >>temp2neg echo "$c3" >>temp2neg echo "$c4" >>temp2neg if [${#c5} -gt 0 ] then echo "$c5" >>temp2neg fi if [${#c6} -gt 0 ] then echo "$c6" >>temp2neg fi echo "$Y0" >>temp2neg echo "$Y1" >>temp2neg echo "" >>temp2neg fi ;; esac done echo "As of ropteffort=${r}, Murphy_E scores:" echo $MurphyEs if [ -e temp2neg ] then negatecs cat temp2neg >>rawset cat tempneg >>rawset if [$r -lt 10 ] then sizeopt fi fi done # Extract best polynomial c5="" c6="" rm BestPoly 2>/dev/null exec <"roptset" while read line do case $line in "# n: "*) n=$line ;; "# Y0: "*) Y0=$line ;; "# Y1: "*) Y1=$line ;; "# c0: "*) c0=$line ;; "# c1: "*) c1=$line ;; "# c2: "*) c2=$line ;; "# c3: "*) c3=$line ;; "# c4: "*) c4=$line ;; "# c5: "*) c5=$line ;; "# c6: "*) c6=$line ;; "# skew: "*) skew=$line ;; "# # lognorm "*) lognorm=$line ;; "# # MurphyE("*) MurphyE=$line ;; esac done echo "# Best polynomial found:" echo "${n:2}" >>BestPoly echo "${Y0:2}">>BestPoly echo "${Y1:2}" >>BestPoly echo "${c0:2}" >>BestPoly echo "${c1:2}" >>BestPoly echo "${c2:2}" >>BestPoly echo "${c3:2}" >>BestPoly echo "${c4:2}" >>BestPoly if [ ${#c5} -gt 0 ] then echo "${c5:2}" >>BestPoly fi if [ ${#c6} -gt 0 ] then echo "${c6:2}" >>BestPoly fi echo "${skew:2}" >>BestPoly echo "${lognorm:2}" >>BestPoly echo "${MurphyE:2}" >>BestPoly cat BestPoly # Remove intermediate files if "keep" setting is (n)o case$keepintfiles in "n"*) rm rawset rm roptset rm soptset rm tempneg rm temp2neg ;; esac # print time taken to run entire process let hr=${SECONDS}/3600 let SECONDS=${SECONDS}%3600 let mn=${SECONDS}/60 let se=${SECONDS}%60 printf "Full run time: %d:%02d:%02d\n" $hr$mn \$se Last fiddled with by EdH on 2020-12-03 at 18:49
2020-12-07, 21:36   #3
Branger

Oct 2018

23·3 Posts

Quote:
 Originally Posted by EdH Step 2b: Change the signs for all the c#'s in the new file. Do NOT alter the Y#'s.
At some point I played around with a similar scheme, but instead of multiplying all c# coefficients with -1, I tried a small positive multiplier such as 2-5, before feeding the polynomials to msieve to optimize them. At least for the multiplier of 2 I did find some polynomials that were better than the original one, though never one that ended up at the top. Perhaps this idea may be worth a try?

2020-12-07, 22:30   #4
EdH

"Ed Hall"
Dec 2009

23×3×5×31 Posts

Quote:
 Originally Posted by Branger At some point I played around with a similar scheme, but instead of multiplying all c# coefficients with -1, I tried a small positive multiplier such as 2-5, before feeding the polynomials to msieve to optimize them. At least for the multiplier of 2 I did find some polynomials that were better than the original one, though never one that ended up at the top. Perhaps this idea may be worth a try?
There are some more steps that Max uses, including, I think, some scaling. That may fit in with your multiplication. I don't think Bash can handle that math on its own*, but I'm working on a Python script, that I already am having success with in a Colab session. I'm sure I could get Python to perform the activity. Thanks for bringing it to the discussion!

*I actually could create a Bash function that would step through a string from end to beginning, doing doubling along the way, but that might be involved and probably a bit messy.

 Similar Threads Thread Thread Starter Forum Replies Last Post aein Msieve 2 2017-10-05 01:52 mfeltz Msieve 10 2016-03-16 21:12 Uncwilly Lounge 5 2014-07-07 22:36 ravlyuchenko Msieve 1 2011-08-16 12:12 cipher Prime Sierpinski Project 10 2009-07-01 13:34

All times are UTC. The time now is 23:30.

Mon May 17 23:30:19 UTC 2021 up 39 days, 18:11, 0 users, load averages: 2.09, 2.15, 2.25