View Single Post
Old 2020-12-03, 18:34   #2
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

5×11×89 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