mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2020-12-03, 18:33   #1
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

3×372 Posts
Default 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: <composite>.

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.
EdH is offline   Reply With Quote
Old 2020-12-03, 18:34   #2
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

3·372 Posts
Default

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 <scriptname> <polynomials filename> <composite>
or, simply:
Code:
$ bash <scriptname>
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 <polysfilename> <composite>
# 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=<folder in build directory to use>
#
# Discussion of this process and script can be found in this thread:
#     <add thread address here>
###########################################################################

# 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
EdH is offline   Reply With Quote
Old 2020-12-07, 21:36   #3
Branger
 
Oct 2018

2×3×5 Posts
Default

Quote:
Originally Posted by EdH View Post
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?
Branger is offline   Reply With Quote
Old 2020-12-07, 22:30   #4
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

3·372 Posts
Default

Quote:
Originally Posted by Branger View Post
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.
EdH is offline   Reply With Quote
Old 2021-10-18, 14:29   #5
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

3·372 Posts
Default

It's been quite some time and I've made a bunch of changes to the script. Most of the change has seemed to make no difference other than taking longer to run. I'm still working on many items.

In testing older poly requests, this script usually finds something better than the original, but rarely ever matches Max0526's spins. As to more current polynomial requests, this script rarely spins anything better than what is posted, but hopefully it will at some point.

A lot of what I've changed is aesthetic. The output looks quite different now. But, I have also added the following:

- Lots of options to set in the beginning of the script.
- - Most of these are whether to run the following
- - - CADO-NFS ropt 100 the first time through
- - - Msieve size optimization **Not currently working but code exists**
- - - Msieve root optimization
- - - Add multiplied coefficients (c's) prior to optimizations for CADO and/or Msieve
- - - - Values to multiply by, if adding the above
- - - CADO-NFS size and root optimization a second time
- - - Note that for the Msieve portion, msieve must be available.
- - - Note that for the add multipliers operation, Pari-gp must be installed.
- Duplicate removal of polys in intermediate file.
- Reads all formats (R0, Y0, A0, etc.) of input polynomials that I have found. You can mix and match within the polynomial file.
- The only input is the poly file, which can contain multiple polynomials. Its name can be added to the command line or supplied at a prompt.
- - The composite (n:) must exist within the first poly.
- Works with quartics through octics. (Not fully tested.)
- Culls number of intermediate polys to a user set number. (This number is a base which is added to fequently.)
- Logs all Best Polynomials in unique list for further review.
- - Second, third best, etc. polys can be found within this list.
- - The list is named BestPoly#####.list, where ##### are the first five digits of the composite.
- Checks with cownoise.com for skew and Murphy_E comparisons
- - Note that an Internet connection and wget are necessary for cownoise data.
- Added stderr.list which catches all stderr output for review. (keepintfiles=no does not remove it at the end of a run, but it is overwritten in any subsequent runs.)

There is a very visible bug! I haven't been able to figure out exactly why, but even if you supply the best poly from the beginning, the CADO-NFS lower effort operations "lose" the higher Murphy_E scores. And, the first CADO-NFS ropt operation after Msieve, definitely displays this behaviour. (Actually, depending on the culling done, other top scoring polys are lost, also.) Fortunately, this is resolved in the subsequent runs and doesn't affect the returned Best Poly in the end (as far as I have seen).. (Actually, depending on the culling done, other top scoring polys are lost, also.)

There is still much more to do. The script is very redundant and portions make no difference. Some functions exist that are not yet implemented and the functions are in total disorder. But, if I wait until everything is working just right, I'll never post anything.

The script has grown too large to fit within a single post, so I'll attach versions to this and subsequent posts.

Please provide all feedback to this thread and remember to thank Max0526 for sharing his spin procedure. I hope to understand more of it and improve upon what is provided.

Below is a good example of a successful run for an earlier polynomial request. It shows an escalating Best Poly score and most of the operations. (The ropt 100 is omitted for the initial CADO-NFS runs.)

A brief description:
- polys is entered as the original polynomial source - this filename can alternately be added to the command line
- original poly(s) is(are) read (and converted, if necessary) to Y/c format and written to a file called rawset
- original c's are manipulated by mutipliers (if option is chosen) and new polys are added to rawset
- negated versions of the rawset polynomials are generated and added back to rawset
- initial CADO-NFS size optimization is performed at 0, 1, 10 and 100 and new polys (and their negated forms) are added to rawset
- CADO-NFS root opt at 0 is performed
- rawset is culled by duplicate removal and trimming to number of top scoring polys - count based on score - multiple polys with same score are kept
- all polys with the top selected scores are added (with their negative forms) to rawset
- the top score is returned and a best poly is copied to the log
- the three preceding steps are repeated at ropt 0.01 and 1
- the same steps are performed at ropt 2 and 10 with more size opts added in
- in the example, the first opportunity for ropt at 100 was skipped
- a file (.ms) is written for Msieve and multiplied values are added as directed in the settings
- Msieve root optimization is performed
- the Msieve returned polynomial choice is added to rawset with its negated version
- CADO-NFS size and root optimizations are performed again (as above), as chosen in the settings
- in the second run root opt is also run at 100

In the example, it is shown that a progression of scores is encountered up through root opt 1. After that no improvement is seen

Unfortunately, after the Msieve operation, there is a temporary loss of the best poly. But, the final best poly is equivalent to the previous. In this case the best poly was found early on, and it may just suffice to only run the initial phase at this point.

Original polynomial:
Code:
n: 201916700580745604776027022665471186255107062245932082076863383752096343903385041484073267281054478199044604641397575671739630499971150912819790916215008125554106571022882316742647109864486081319721103021177161
Y0: -32507823573507006198240834416613396620026
Y1: 764359993484535911177455197
c0: 7422876104398390129123665707218326214456678976313
c1: -647890060642992949061373452059821094979964
c2: -2396631357068296334601221348652323
c3: -33828674440462622647996
c4: -14210375486953290
c5: 50058540
skew: 335007570.06
# size 1.234e-20, alpha -7.743, combined = 1.120e-15 rroots = 3
# MurphyE = 1.18869319e-15
Example run (24 threads):
Code:
$ bash polyspin.sh
polys file: polys
Running initial CADO-NFS size optimizations:
Current exp_E list from sopteffort 0, 1, 10, 100:       57.23 57.24 57.25 57.34 57.65 58.01 58.21
Running initial CADO-NFS root optimizations:
rootopt 0 took 1:52
  Current list of Murphy_E scores:      9.773e-16 9.806e-16 1.006e-15 1.050e-15 1.075e-15
    Best Murphy_E found so far:   1.075e-15
rootopt 0.01 took 54 seconds
  Current list of Murphy_E scores:      1.006e-15 1.039e-15 1.050e-15 1.075e-15 1.085e-15
    Best Murphy_E found so far:   1.085e-15
rootopt 1 took 1:17
  Current list of Murphy_E scores:      1.039e-15 1.075e-15 1.085e-15 1.183e-15
    Best Murphy_E found so far:   1.183e-15
Current exp_E list from sopteffort 0, 1, 10, 100:       57.22 57.23 57.24 57.25 57.26 57.30 57.53
rootopt 2 took 5:03
  Current list of Murphy_E scores:      1.070e-15 1.075e-15 1.085e-15 1.113e-15 1.183e-15
    Best Murphy_E found so far:   1.183e-15
Current exp_E list from sopteffort 0, 1, 10, 100:       57.23 57.24 57.25 57.26 57.27 57.30 57.34 57.53
rootopt 10 took 43:26
  Current list of Murphy_E scores:      1.085e-15 1.088e-15 1.113e-15 1.120e-15 1.183e-15
    Best Murphy_E found so far:   1.183e-15
Msieve root optimization took 52:51
Running CADO-NFS size optimizations:
Current exp_E list from sopteffort 0, 1, 10, 100:       57.23 57.24 57.25 57.27 57.30 57.53
Running final CADO-NFS root optimizations:
rootopt 0 took 11:43
  Current list of Murphy_E scores:      1.046e-15 1.050e-15 1.063e-15 1.075e-15 1.085e-15
    Best Murphy_E found so far:   1.085e-15
rootopt 0.01 took 2:43
  Current list of Murphy_E scores:      1.050e-15 1.063e-15 1.075e-15 1.085e-15 1.113e-15
    Best Murphy_E found so far:   1.113e-15
rootopt 1 took 3:35
  Current list of Murphy_E scores:      1.075e-15 1.085e-15 1.183e-15
    Best Murphy_E found so far:   1.183e-15
Current exp_E list from sopteffort 0, 1, 10, 100:       57.23 57.24 57.25 57.26 57.30 57.53
rootopt 2 took 11:36
  Current list of Murphy_E scores:      1.050e-15 1.075e-15 1.082e-15 1.085e-15 1.183e-15
    Best Murphy_E found so far:   1.183e-15
Current exp_E list from sopteffort 0, 1, 10, 100:       57.23 57.24 57.25 57.26 57.27 57.30 57.53
rootopt 10 took 1:05:18
  Current list of Murphy_E scores:      1.085e-15 1.088e-15 1.113e-15 1.120e-15 1.183e-15
    Best Murphy_E found so far:   1.183e-15
rootopt 100 took 3:53:36
  Current list of Murphy_E scores:      1.085e-15 1.113e-15 1.183e-15
    Best Murphy_E found so far:   1.183e-15
  Best poly found:
n: 201916700580745604776027022665471186255107062245932082076863383752096343903385041484073267281054478199044604641397575671739630499971150912819790916215008125554106571022882316742647109864486081319721103021177161
Y0: -32507833225041661567808073522870118923979
Y1: 764359993484535911177455197
c0: 29987438134706356646028532815412089975470608383960
c1: -587261506700262395105621651359625947436598
c2: -2409951896201592634142513541908051
c3: 763719328345225161226244
c4: -17370808644925590
c5: 50058540
skew: 254090649.422
# lognorm 65.54, E 57.50, alpha -8.04 (proj -2.48), 3 real roots
# MurphyE(Bf=1.000e+07,Bg=5.000e+06,area=1.000e+16)=1.183e-15

Best poly cownoise values: 332566833.11894      1.18869319e-15
Full run time: 7:26:38
Attached Files
File Type: txt polyspin.sh.txt (29.2 KB, 11 views)

Last fiddled with by EdH on 2021-10-20 at 23:51 Reason: bugfix in polyspin.sh - reattachment
EdH is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
use msieve linear algebra after CADO-NFS filtering aein Msieve 2 2017-10-05 01:52
Combining Msieve with CADO NFS mfeltz Msieve 10 2016-03-16 21:12
Murphy's Law and other tools Uncwilly Lounge 5 2014-07-07 22:36
how to run msieve or cado-nfs on mpi-cluster? ravlyuchenko Msieve 1 2011-08-16 12:12
Improving Sieving by 18%. cipher Prime Sierpinski Project 10 2009-07-01 13:34

All times are UTC. The time now is 03:34.


Sat Nov 27 03:34:35 UTC 2021 up 126 days, 22:03, 0 users, load averages: 1.56, 1.25, 1.19

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.