mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Aliquot Sequences

Reply
 
Thread Tools
Old 2009-03-27, 07:11   #1
mdettweiler
A Sunny Moo
 
mdettweiler's Avatar
 
Aug 2007
USA (GMT-5)

141518 Posts
Default Team sieve #1: c132 from 4788:2369

Hi all,

We are now ready to begin sieving reservations for the C132 from line 2369! The polynomial is as follows
Code:
n: 237474238144581942013743962592681110466868743637301019199392364875573239625256029804412406254660594889970612890759306708620321670791
m: 
c0: -886453156259166466411223244168048
c1: 10417433936461703190962680232
c2: -8539973826610045881734
c3: -61842799874609791
c4: 5295772908
c5: 46260
Y0: -21982750207447868725446881
Y1: 331523414532167
skew: 637739.23
rlim: 5400000
alim: 5400000
lpbr: 27
lpba: 27
mfbr: 54
mfba: 54
rlambda: 2.5
alambda: 2.5
We will be using the gnfs-lasieve4I13e siever for this project, and will start reservations at q=2.5M. (Note: my experience with GNFS parameterization is extremely limited, so anyone else can feel free to correct me on anything you feel may be suboptimal. I just had factMsieve.pl fill in all the blanks on the polynomial that weren't already provided by msieve, and for the starting q-value, it suggested 2.7M, but I've noticed that sometimes it's more optimal to go a bit lower than the 1/2*alim that factMsieve does.)

If you're not already familiar with how to run the GGNFS lattice sievers, you can follow these steps:

-Download and unpack GGNFS. Precompiled Windows binaries can be found at http://gilchrist.ca/jeff/factoring/index.html; I can provide 32-bit Linux binaries on request. If you're looking for 64-bit Linux binaries, ask around--last I remember there are a number of copies that have been floated around on the forums.

-In your GGNFS folder, create a new text file called "4788-2369.poly". Open it with a text editor and copy/paste the above polynomial data into it.

-Now open a command prompt to your GGNFS folder and run the following command:
Code:
gnfs-lasieve4I13e -a 4788-2369.poly -f start-of-range -c length-of-range -o output-file
Replace "start-of-range" with the q value at the beginning of your reservation, "length-of-range" with the length of your range (for example, if you reserved 2.5M to 3.0M, you'd set this as "-f 2500000 -c 500000"), and "output-file" with the name of a file to output to.

-The siever will run until it completes the range, updating progress every few seconds along the way. If the job is interrupted (either with Ctrl-C or forcibly), don't worry--you can still resume from where you left off. Open your results file (warning: it will be a huge file. If you're on Linux/Unix or have access to the Linux/Unix tool "tail", I'd recommend using that) and skip to the end of the file. You'll notice that the last few lines will look something like this:
Code:
12571943595,90442:da66c29,648802f,17455,55543,7,2B,47,3,3,B,B:11c54b27,84f9ac1,2A2D7,34565,67553,12B7B9,19CF,148D,5,5,1F,1F3,2,2,34DFF65
-11386617209,23426:72c380b,4371
In the example above, the second-to-last line is the last truly finished line, and the one after that is incomplete. Ignore any incomplete lines; take the last complete line, and find the last group of hexadecimal digits (highlighted above in bold--note that your line will of course be different than the example, but the info you want will still be in the same place on the line). Convert that to decimal, and that's the last q-value that the siever completed before being shut down. Use that as your -f value when restarting, and to get the -c value, subtract it from the end of your range. Make sure you specify a new output file name so that the old one isn't overwritten--multiple files are fine since I'll be combining them all anyway for the postprocessing. Tip: if you're having trouble converting the hex value to decimal, try googling for "hexadecimal calculator". Something useful should come up within the first few results.

-When your range is complete, hang on to the results file(s). We currently do not have an upload system in place but I'm hoping to get an FTP server set up within the next few days. Note: once we do get an upload system going, it is recommended that you compress your files (zip, rar, gzip, bz2, 7z, etc.--my computer can read most any compression format) before uploading them since they're HUGE.

-Rinse, lather, and repeat!

I'll reserve 2.5M to 3.0M to start with. It's not too big a range, but I figured I'd start small and work my way up once I get a better feel for how long these ranges take.

Sieving complete
----------------------------------------------------
Reservations table:

* 0.1M- 2.0M mdettweiler (done, 1517843 relns)
* 2.0M- 2.4M Andi47 (done, 606500 relns)
* 2.4M- 2.5M Andi47 (done, 125505 relns)
* 2.5M- 3.0M mdettweiler (done, 769372 relns)
* 3.0M- 3.5M henryzz (done, 584500 relns)
* 3.5M- 3.6M Andi47 (done, 125040 relns)
* 3.6M- 3.8M Andi47 (done, 251483 relns)
* 3.8M- 4.0M Joshua2 (done, 247253 relns)
4.0M- 4.5M henryzz
* 4.5M- 5.0M Joshua2 (done, 615223 relns)
* 5.0M- 6.0M Joshua2 (done, 1388790 relns)
* 6.0M- 8.0M mdettweiler (done, 2861122 relns)
* 8.0M-10.0M Joshua2 (done, 2596094 relns)
* 10.0M-10.3M Andi47 (done, 289706 relns)
* 10.3M-11.0M mdettweiler (done, 852580 relns)
* 11.0M-12.0M Andi47 (done, 1173056 relns)
12.0M-14.0M Joshua2 (done, 2237643 relns)

Total rels received = 17794627 = 118.6% of 15M relns
----------------------------------------------------

As we progress I'll post updated reservation tables as we go along. (Mods: feel free to consolidate things periodically by updating my table in this post from the ones I'll be posting later.)

I'm not sure how many relations we'll need, but I'm guessing it will be somewhere in the ballpark of 15-20 million. I'll try a matrix run with msieve once we reach 15 million, and keep trying after that (if necessary) as more relations come in.

Max

====================================================

In other news: I am pleased to announce that we now have a working FTP server set up for relations uploads! Instructions as follows will show how to use it with the built-in "ftp" command line program that comes with all Windows and Linux systems; feel free to adapt them as necessary for use with other FTP programs.

---------------------------------------------------
-Open a command prompt/terminal window and type the following command:
ftp nplb-gb1.no-ip.org

-ftp will ask for a username. Type "aliquot" (capitals as shown, no quotes) and press Enter.

-ftp will ask for a password. Type "aqupload-4788" (capitals as shown, no quotes) and press Enter.

-ftp will now output the following:
230 Login successful.
ftp>


-Type "cd c132-relations" and press Enter.

-Type "binary" and press Enter.

-Now type the following command:
put relations.gz
...replacing "relations.gz" with the name (and, if necessary, pathname) of the compressed relations file you're uploading. Tip: navigate to the directory your relations file(s) are in *before* starting the FTP command, so you don't have to type long and clumsy file paths in your "put" commands for each file you upload.

-Wait until the file's finished uploading. Depending on the size of the file, it may take a while; please note that ftp doesn't show any progress or status info until the upload has completed, so it can appear to be "frozen" if you haven't used ftp before.

-Verify that your file's made it to the server by typing the command "ls" and seeing if your file shows up in the directory listing that results. If you see, it, you're all set!

-Type "quit" and press Enter. Close the command prompt/terminal window.
---------------------------------------------------

Some of you may have your own personal favorite GUI-based FTP program that you'd rather use than the command-line "ftp" application that I've used in my above instructions. In that case, simply tell your program to connect to server nplb-gb1.no-ip.org (port 21, the default) and log in as user aliquot with password aqupload-4788, and upload your relations files to the c132-relations directory.

Max

Last fiddled with by schickel on 2009-04-03 at 22:22 Reason: Final status
mdettweiler is offline   Reply With Quote
Old 2009-03-28, 18:48   #2
mdettweiler
A Sunny Moo
 
mdettweiler's Avatar
 
Aug 2007
USA (GMT-5)

3·2,083 Posts
Default

Quote:
Originally Posted by mdettweiler View Post
Hmm....interesting. I do have 2 GB of RAM available, and I know for sure that swap is enabled (with OS managed size and plenty of disk space), so I can't imagine why that would be a problem. However, yes, that does seem to be the most likely explanation. I'll check Google to see if it has anything to weigh in on this.
Okay--after Googling around a bit, I found that on 32-bit Windows, there is a limit of 2 GB of memory that can be allocated per process, and anything above that will either a) produce an error (probably this is what I'm seeing now) or b) force everything >2GB to go into the page file (even if you have more than 2GB of total memory in the system). However....this limit is often cut down to closer to 1.5-1.7 GB in most circumstances because of Windows' own overhead.

Fortunately my system is configured to dualboot Ubuntu Linux so I'll give it a try from there. If the problem is indeed caused by the limit described above, then that should fix it.

Last fiddled with by schickel on 2009-03-29 at 07:34
mdettweiler is offline   Reply With Quote
Old 2009-03-28, 19:47   #3
mdettweiler
A Sunny Moo
 
mdettweiler's Avatar
 
Aug 2007
USA (GMT-5)

3×2,083 Posts
Default

Quote:
Originally Posted by henryzz View Post
i used the same setting as Joshua2 thinking about it
i had a smaller file and i did it on 32-bit vista

bad spelling was my problem earlier
Yes, that fits my theory about running up against Windows per-process memory limits. From the looks of it, Joshua2's file was just a wee bit above the limit, so thus it makes sense that yours would work OK.
mdettweiler is offline   Reply With Quote
Old 2009-03-28, 23:34   #4
mdettweiler
A Sunny Moo
 
mdettweiler's Avatar
 
Aug 2007
USA (GMT-5)

3×2,083 Posts
Default

Quote:
Originally Posted by Joshua2 View Post
Ok, so you might want to make a note that the best compression ratio settings are 7z, ultra, ppmd, 512mb dictionary, 32 wordsize, solid, and putting all files into the same archive. Goes pretty fast, and will save upload and download time, and only needs 512mb which is reasonable.
Well, actually I could probably handle anything up to 1GB of memory for decompression--from what I could tell this one was just over the limit.

Last fiddled with by schickel on 2009-03-29 at 07:38
mdettweiler is offline   Reply With Quote
Old 2009-03-29, 00:38   #5
mdettweiler
A Sunny Moo
 
mdettweiler's Avatar
 
Aug 2007
USA (GMT-5)

3×2,083 Posts
Default

Meanwhile, the FTP server is still down. And, of course, that means that I *still* don't have the second half of Joshua2's 5M-6M results. Joshua2, do you by chance still have the 5-6.7z file still sitting around? If yes, hang on to it--I'm not sure yet, but there's a chance that the server may be down for up to 5 days or so since Gary's currently out of town.

Last fiddled with by schickel on 2009-03-29 at 07:44
mdettweiler is offline   Reply With Quote
Old 2009-03-29, 16:18   #6
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3,529 Posts
Default

Quote:
Originally Posted by mdettweiler View Post
Okay--after Googling around a bit, I found that on 32-bit Windows, there is a limit of 2 GB of memory that can be allocated per process, and anything above that will either a) produce an error (probably this is what I'm seeing now) or b) force everything >2GB to go into the page file (even if you have more than 2GB of total memory in the system).
Option 'a' will always happen. On a 32-bit system, pointers for virtual addresses are 32 bits in size, and half of the available range is reserved for the OS. That means your program gets 2GB of virtual memory to fit everything: application code, runtime library code, static data, allocated memory, stack space, everything. 2GB is a hard limit no matter how much swap space you have, because even stuff sitting in the swap file on disk is addressed with those same 32-bit addresses. There's nowhere for extra address bits to go. Linux has the same limitation, but in linux the OS gets the top 1GB of each process' virtual memory, so linux processes can allocate up to 3GB of VM. There's a trivial kernel patch that changes that to 3.5GB by changing one number in the source, but it's not safe to push that any higher because the OS needs memory space too.

The situation is different when you have a 64-bit OS but are running 32-bit programs. In that case your programs still get a 32-bit address space, but the OS can take virtual memory with addresses above 2^32 (= 4GB). So 32-bit programs in 64-bit XP/Vista or 64-bit linux can allocate a bit less than 4GB of memory, i.e. they can use an entire 32-bit address space for user stuff.

Different processor architectures will do things differently, but I'm pretty sure x86 and powerPC behave this way.
Quote:
Regarding why we started at 2.5M: lattice sieving q-values tend to have a certain "sweet spot" range where they produce the highest yield of relations. The yield drops off somewhat quickly above and below the optimal range.
Just a nitpick, but the number of relations found for a given special-q only drops off gradually as the size of the special-q increases. However the number of relations found over and over again (i.e. the duplicate rate) increases drastically as you burn through more and more special-q, and at some point it becomes impractical to keep sieving because the high duplicate rate means most of the work is wasted. The objective is not to find every relation you're entitled to, but to maximize the number of non-duplicate relations found per second.
jasonp is offline   Reply With Quote
Old 2009-03-29, 18:40   #7
mdettweiler
A Sunny Moo
 
mdettweiler's Avatar
 
Aug 2007
USA (GMT-5)

3×2,083 Posts
Default

Quote:
Originally Posted by jasonp View Post
Option 'a' will always happen. On a 32-bit system, pointers for virtual addresses are 32 bits in size, and half of the available range is reserved for the OS. That means your program gets 2GB of virtual memory to fit everything: application code, runtime library code, static data, allocated memory, stack space, everything. 2GB is a hard limit no matter how much swap space you have, because even stuff sitting in the swap file on disk is addressed with those same 32-bit addresses. There's nowhere for extra address bits to go. Linux has the same limitation, but in linux the OS gets the top 1GB of each process' virtual memory, so linux processes can allocate up to 3GB of VM. There's a trivial kernel patch that changes that to 3.5GB by changing one number in the source, but it's not safe to push that any higher because the OS needs memory space too.

The situation is different when you have a 64-bit OS but are running 32-bit programs. In that case your programs still get a 32-bit address space, but the OS can take virtual memory with addresses above 2^32 (= 4GB). So 32-bit programs in 64-bit XP/Vista or 64-bit linux can allocate a bit less than 4GB of memory, i.e. they can use an entire 32-bit address space for user stuff.

Different processor architectures will do things differently, but I'm pretty sure x86 and powerPC behave this way.
Thanks for the very detailed and helpful explanation! Now this stuff makes a lot more sense

Quote:
Just a nitpick, but the number of relations found for a given special-q only drops off gradually as the size of the special-q increases. However the number of relations found over and over again (i.e. the duplicate rate) increases drastically as you burn through more and more special-q, and at some point it becomes impractical to keep sieving because the high duplicate rate means most of the work is wasted. The objective is not to find every relation you're entitled to, but to maximize the number of non-duplicate relations found per second.
Ah, thanks for clarifying there. I had a vague idea of how it worked before, but wasn't entirely clear on the how and why of relation yield.

Last fiddled with by mdettweiler on 2009-03-29 at 18:41
mdettweiler is offline   Reply With Quote
Old 2009-03-30, 16:25   #8
mdettweiler
A Sunny Moo
 
mdettweiler's Avatar
 
Aug 2007
USA (GMT-5)

3×2,083 Posts
Default

Quote:
Originally Posted by schickel View Post
No, actually it won't; since the sieving is deterministic, two runs with the same parameters will result in the same relations.
Ah, I see. In that case, 10metreh, don't worry about uploading the relations from your b=1-100 line sieving run, since I've already got everything covered up to b=300.
mdettweiler is offline   Reply With Quote
Old 2009-04-01, 14:58   #10
mdettweiler
A Sunny Moo
 
mdettweiler's Avatar
 
Aug 2007
USA (GMT-5)

141518 Posts
Default

Quote:
Originally Posted by mdettweiler View Post
Hmm...I was able to download the .7z file okay, but then when I tried to extract them 7-Zip gave a "data error" and the files apparently were only partially extracted (one was 3 MB, the other two were 0 MB).

It's possible something got messed up/corrupted during the download. I'll try it again tomorrow (don't have time tonight).
Hmm...okay, this time I tried again and I still got the same error. I checked online with Google and found that a "data error" in 7-Zip generally indicates that the archive is incomplete. This is supported by the fact that two of the files in the archive are somewhat significantly smaller than the third.

Joshua, could you by chance try re-compressing those three relations files and uploading them again to megaupload?

(P.S.: still working on downloading Andi47's. Rapidshare has some kind of limit that doesn't let you download more than one file within a 15-minute time frame, so I'm currently on hold waiting for the second one.)

Last fiddled with by mdettweiler on 2009-04-01 at 14:59
mdettweiler is offline   Reply With Quote
Old 2009-04-01, 15:40   #11
Andi47
 
Andi47's Avatar
 
Oct 2004
Austria

2×17×73 Posts
Default

Quote:
Originally Posted by mdettweiler View Post
(P.S.: still working on downloading Andi47's. Rapidshare has some kind of limit that doesn't let you download more than one file within a 15-minute time frame, so I'm currently on hold waiting for the second one.)
Ooops, sorry, I did not know that. Next time (if we need more sieving, or we do a team sieve on a new number) I will concatenate the files before uploading.
Andi47 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Team sieve #24: c155 from 4788:2618 schickel Aliquot Sequences 26 2011-02-24 23:19
Team sieve #23: c172 from 4788:i2617 schickel Aliquot Sequences 64 2011-02-19 02:28
Team sieve #21: c162 from 4788:2602 jrk Aliquot Sequences 31 2010-12-30 21:33
Team sieve #11: c132 from 4788.2441 10metreh Aliquot Sequences 20 2009-08-28 09:49
Team sieve #5: c140 from 4788:2407 10metreh Aliquot Sequences 77 2009-05-27 20:39

All times are UTC. The time now is 13:07.

Sat Sep 19 13:07:32 UTC 2020 up 9 days, 10:18, 1 user, load averages: 1.90, 1.62, 1.51

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.