2020-12-11, 20:33 | #1 |
"Ed Hall"
Dec 2009
Adirondack Mtns
3·1,181 Posts |
How I Create a Colab Session That Improves Some Polynomials
(Note: I expect to keep the first post of each of these "How I..." threads up-to-date with the latest version. Please read the rest of each thread to see what may have led to the current set of instructions.)
I will take the liberty of expecting readers to already be somewhat familiar with Google's Colaboratory sessions. There are several threads already on Colab and these should be reviewed by interested readers: Google Colaboratory Notebook? GPU72 Notebook Integration... Notebook Instance Reverse SSH and HTTP Tunnels. Colab question I do not, as of yet, have a github account, so I have not created an upload of this to github. Others may feel free to do so, if desired. The following is a manner to use CADO-NFS size and root optimization to look for improved polynomials. It is based on this thread in the Factoring forum: Improving Polynomials With CADO-NFS and Msieve Tools Unfortunately, although I'm creating this thread to show how to create this Colab session, it may not be of much interest. In order for this to run, the first time it is invoked, it takes twenty minutes to build CADO-NFS. Then it takes a couple hours to do a full "spin" for a candidate polynomial. Benefits may be experienced, though, and here are some examples: Using the Skew Optimizer at cownoise you can compare the Murphy_E scores for the sample polynomial and its spin: Code:
original : 1.27260067e-15 best spin: 1.32925706e-15 On to the specifics: Open a Google Colaboratory session. Sign in with your Google/Gmail account info. Choose New Python3 notebook: Code:
Menu->File->New notebook Edit title from Untitled... to whatever you like. Paste the following into the Codeblock: Code:
######################################################## ### This Colaboratory session is designed to improve ### ### a polynomial through a process of repeated size ### ### and root optimizations using CADO-NFS. ### ### ### ### Although more than one polynomial can be entered ### ### initially, a single run of one polynomial may ### ### use up the limited time for a Colab session. ### ######################################################## # True runs a shortened session for testing. test = True # Relace the below polynomial with the one to spin. # Be sure to match the formatting exactly: # ( ' at beginning and ', at the end of each line). # Make sure the lines immediately before and after are # undisturbed. polyinit = [ 'n: 105846620118997527795673923816494096564538879551655755948941841181964527982935974672375053674066636955526325748344171237200759216056332103525354574858042635016393534861038293333116405407677018242280598840418822711', 'skew: 15664544.853', 'c0: -626081313147184760199029071786307655596384808000', 'c1: 114155706290582003827015758825221679754150', 'c2: 9698330805779200485429519766575815', 'c3: -1612013188384034013354246592', 'c4: -71413365342160076609', 'c5: 2982285821808', 'c6: 45360', 'Y0: -66175507466676477845668491119429817', 'Y1: 284594098468775320577861', ] polyinit.append('') polyinit.append('') import os import shutil import subprocess import sys import time # This function changes all the signs for all the c# values # in temp2neg, placing the output in tempneg. Then it # appends both temp2neg and tempneg to rawset. def polynegate(): inF = open("/content/cado-nfs/polyspin/temp2neg", "r") outF = open("/content/cado-nfs/polyspin/tempneg", "w") for line in inF: if line[:1] == "c": if line[4:5] == "-": line = line[:4] + line[5:] else: line = line[:4] + "-" + line[4:] outF.write(line) outF.close() inF.close() rawF = open("/content/cado-nfs/polyspin/rawset", "a") tnF = open("/content/cado-nfs/polyspin/tempneg", "r") inF = open("/content/cado-nfs/polyspin/temp2neg", "r") for line in inF: rawF.write(line) for line in tnF: rawF.write(line) inF.close() tnF.close() rawF.close() # This function performs CADO-NFS size optimizations on # the polynomials in rawset def sizeopt(seff): sopttemp = open("/content/cado-nfs/polyspin/sopttemp", "w") for eff in seff: # print("Running sopt at " + str(eff)) p = subprocess.Popen([sopt, "-inputpolys", "/content/cado-nfs/polyspin/rawset", "-sopteffort", str(eff), "-v"], stdout=subprocess.PIPE, stderr=subprocess.STDOUT) for line in iter(p.stdout.readline, b''): linet = line.decode("utf=8") sopttemp.write(linet) sopttemp.close() addnewopt("/content/cado-nfs/polyspin/sopttemp") print("Current exp_E list:") print(*expElist, sep = ", ") polynegate() # This function performs CADO-NFS root optimizations on # the polynomials in rawset def rootopt(reff): ropttemp = open("/content/cado-nfs/polyspin/ropttemp", "w") for eff in reff: # print("Running ropt at" + str(eff)) p = subprocess.Popen([ropt, "-t", "2", "-inputpolys", "/content/cado-nfs/polyspin/rawset", "-area", "1.00e+16", "-Bf", "10000000", "-Bg", "5000000", "-v", "-ropteffort", str(eff)], stdout=subprocess.PIPE, stderr=subprocess.STDOUT) for line in iter(p.stdout.readline, b''): linet = line.decode("utf=8") ropttemp.write(linet) ropttemp.close() addnewopt("/content/cado-nfs/polyspin/ropttemp") print("Current MurphyE list:") print(*MurphyElist, sep = ", ") polynegate() # This function searches for new polynomials from either # the size optimization or root optimization steps. def addnewopt(opt): c5 = "" c6 = "" t2n = open("/content/cado-nfs/polyspin/temp2neg", "w") sF = open(opt, "r") for line in sF: if line[:3] == "n: ": n = line.rstrip() if line[:6] == "skew: ": skew = line.rstrip() if line[:4] == "c0: ": c0 = line.rstrip() if line[:4] == "c1: ": c1 = line.rstrip() if line[:4] == "c2: ": c2 = line.rstrip() if line[:4] == "c3: ": c3 = line.rstrip() if line[:4] == "c4: ": c4 = line.rstrip() if line[:4] == "c5: ": c5 = line.rstrip() if line[:4] == "c6: ": c6 = line.rstrip() if line[:4] == "Y0: ": Y0 = line.rstrip() if line[:4] == "Y1: ": Y1 = line.rstrip() if line[:10] == "# lognorm " and opt[-8:] == "sopttemp": expE = line.rstrip()[23:28] if not expE in expElist: expElist.append(expE) t2n.write(n + "\n") t2n.write(skew + "\n") t2n.write(c0 + "\n") t2n.write(c1 + "\n") t2n.write(c2 + "\n") t2n.write(c3 + "\n") t2n.write(c4 + "\n") if len(c5) > 0: t2n.write(c5 + "\n") if len(c6) > 0: t2n.write(c6 + "\n") t2n.write(Y0 + "\n") t2n.write(Y1 + "\n") t2n.write("\n") if line[:10] == "# MurphyE(" and opt[-8:] == "ropttemp": MurphyE = line.rstrip()[-9:] if not MurphyE in MurphyElist: MurphyElist.append(MurphyE) t2n.write(n + "\n") t2n.write(skew + "\n") t2n.write(c0 + "\n") t2n.write(c1 + "\n") t2n.write(c2 + "\n") t2n.write(c3 + "\n") t2n.write(c4 + "\n") if len(c5) > 0: t2n.write(c5 + "\n") if len(c6) > 0: t2n.write(c6 + "\n") t2n.write(Y0 + "\n") t2n.write(Y1 + "\n") t2n.write("\n") sF.close() t2n.close() # This section determines whether CADO-NFS is already installed. # If CADO-NFS does not yet exist, it is built. The initial # building of CADO-NFS takes about twenty minutes. exists = os.path.isfile('/content/cado-nfs/README.msieve') if exists < 1: fstart = time.time() print("Updating and installing system files (libgmp-dev, cmake, git). . .") subprocess.call(["apt", "update"]) subprocess.call(["apt", "install", "libgmp-dev", "cmake", "git"]) print("Retrieving CADO-NFS. . .") subprocess.call(["git", "clone", "https://gitlab.inria.fr/cado-nfs/cado-nfs.git"]) os.chdir("/content/cado-nfs") print("Building CADO-NFS. This will take about twenty minutes. . .") p = subprocess.Popen(["make"], stdout=subprocess.PIPE, stderr=subprocess.STDOUT) for line in iter(p.stdout.readline, b''): print(line.rstrip().decode("utf=8")) os.mkdir("/content/cado-nfs/polyspin") os.chdir("/content/cado-nfs/polyspin") runtime = time.time() - fstart print("Elapsed time was", int(runtime / 60), "minutes and", int(runtime % 60), "seconds.\n") # This removes the old rawset file for subsequent runs. exists = os.path.isfile('/content/cado-nfs/polyspin/rawset') if exists > 0: os.remove("/content/cado-nfs/polyspin/rawset") # This iniatizes temp2neg with the polynomial from the top # of the page which will eventually create the rawset file. with open("/content/cado-nfs/polyspin/temp2neg", mode="wt", encoding="utf-8") as t2n: t2n.write("\n".join(polyinit)) polynegate() # This constructs the pathnames to use for the CADO-NFS # size and root optimization calls. bpath = os.listdir("/content/cado-nfs/build") sopt = "/content/cado-nfs/build/" + bpath[0] + "/polyselect/sopt" ropt = "/content/cado-nfs/build/" + bpath[0] + "/polyselect/polyselect_ropt" # This inializes some variables. c5 and c6 are initialized # empty here so that degrees 4 and 5 polynomials can be run. c5 = "" c6 = "" expElist = [] MurphyElist = [] # This first run is used to establish the exp_E for the original # polynomial and its negated version, to minimize duplication. seff = [0] sizeopt(seff) outF = open("/content/cado-nfs/polyspin/rawset", "w") with open("/content/cado-nfs/polyspin/temp2neg", "r") as inT2n: for line in inT2n: outF.write(line) with open("/content/cado-nfs/polyspin/tempneg", "r") as inTn: for line in inTn: outF.write(line) outF.close() # This runs various size and root optimizations, # adding all new polynomials to rawset. if test == True: seff = [0, 1, 10] sizeopt(seff) reff = [0, 0.01] rootopt(reff) seff = [0, 1, 10] sizeopt(seff) reff = [0, 0.01] rootopt(reff) else: seff = [0, 1, 10, 100] sizeopt(seff) reff = [0, 0.01, 1] rootopt(reff) seff = [0, 1, 10, 100] sizeopt(seff) reff = [0, 0.01, 2] rootopt(reff) seff = [0, 1, 10, 100] sizeopt(seff) reff = [0, 0.01, 10] rootopt(reff) # This harvests the best polinomial from the latest # root optimization and writes it to the screen. bp = open("/content/cado-nfs/polyspin/ropttemp", "r") for line in bp: if line[:5] == "# n: ": n = line.rstrip()[2:] if line[:8] == "# skew: ": skew = line.rstrip()[2:] if line[:6] == "# c0: ": c0 = line.rstrip()[2:] if line[:6] == "# c1: ": c1 = line.rstrip()[2:] if line[:6] == "# c2: ": c2 = line.rstrip()[2:] if line[:6] == "# c3: ": c3 = line.rstrip()[2:] if line[:6] == "# c4: ": c4 = line.rstrip()[2:] if line[:6] == "# c5: ": c5 = line.rstrip()[2:] if line[:6] == "# c6: ": c6 = line.rstrip()[2:] if line[:6] == "# Y0: ": Y0 = line.rstrip()[2:] if line[:6] == "# Y1: ": Y1 = line.rstrip()[2:] if line[:12] == "# # lognorm ": lnorm = line.rstrip()[2:] if line[:12] == "# # MurphyE(": ME = line.rstrip()[2:] bp.close() print("Best polynomial found:") print(n) print(skew) print(c0) print(c1) print(c2) print(c3) print(c4) if len(c5) > 0: print(c5) if len(c6) > 0: print(c6) print(Y0) print(Y1) print(lnorm) print(ME) # This prints a verification of which run was made. if test == True: print("Finished shortened test run!") else: print("Finished polynomial run!") The first time this is run, CADO-NFS will be built prior to running the "spin" cycles. Subsequent runs within the same session will just do the "spin.". Here's an example spin with the sample polynomial with test = True: Code:
Current exp_E list: 50.04 Current exp_E list: 50.04, 49.74 Current MurphyE list: 1.327e-15, 1.973e-16 Current exp_E list: 50.04, 49.74 Current MurphyE list: 1.327e-15, 1.973e-16 Best polynomial found: n: 105846620118997527795673923816494096564538879551655755948941841181964527982935974672375053674066636955526325748344171237200759216056332103525354574858042635016393534861038293333116405407677018242280598840418822711 skew: 15664544.853 c0: -626081313147184760199029071786307655596384808000 c1: 114155706290582003827015758825221679754150 c2: 9698330805779200485429519766575815 c3: -1612013188384034013354246592 c4: -71413365342160076609 c5: 2982285821808 c6: 45360 Y0: -66175507466676477845668491119429817 Y1: 284594098468775320577861 # 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 Finished shortened test run! Code:
Current exp_E list: 50.04 Current exp_E list: 50.04, 49.74 Current MurphyE list: 1.327e-15, 1.973e-16, 1.243e-15, 1.123e-15 Current exp_E list: 50.04, 49.74, 49.90, 49.83 Current MurphyE list: 1.327e-15, 1.973e-16, 1.243e-15, 1.123e-15, 1.188e-15, 1.134e-15, 1.136e-15 Current exp_E list: 50.04, 49.74, 49.90, 49.83, 49.86 Current MurphyE list: 1.327e-15, 1.973e-16, 1.243e-15, 1.123e-15, 1.188e-15, 1.134e-15, 1.136e-15, 1.224e-15, 1.078e-15, 1.129e-15, 1.110e-15, 1.207e-15, 1.222e-15 Best polynomial found: n: 105846620118997527795673923816494096564538879551655755948941841181964527982935974672375053674066636955526325748344171237200759216056332103525354574858042635016393534861038293333116405407677018242280598840418822711 skew: 15664544.853 c0: -626081313147184760199029071786307655596384808000 c1: 114155706290582003827015758825221679754150 c2: 9698330805779200485429519766575815 c3: -1612013188384034013354246592 c4: -71413365342160076609 c5: 2982285821808 c6: 45360 Y0: -66175507466676477845668491119429817 Y1: 284594098468775320577861 # 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 Finished polynomial run! Last fiddled with by EdH on 2020-12-12 at 20:29 |
Thread Tools | |
Similar Threads | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
How I Create a Colab Session That Factors factordb Small Composites with PARI/GP | EdH | EdH | 0 | 2020-11-21 17:12 |
How I Compile the GPU branch of GMP-ECM in a Colaboratory Session | EdH | EdH | 13 | 2020-06-02 11:05 |
How I Create a Colab Session That Factors factordb Comps with the GPU branch of GMP-ECM and msieve | EdH | EdH | 0 | 2019-12-07 19:51 |
How I Create a Colab Session That Factors factordb Composites with the GPU branch of GMP-ECM | EdH | EdH | 0 | 2019-12-04 01:49 |
How I Create a Colab Session That Factors factordb Composites with YAFU | EdH | EdH | 12 | 2019-11-11 17:44 |