mersenneforum.org Team sieve #1: c132 from 4788:2369
 Register FAQ Search Today's Posts Mark Forums Read

 2009-03-27, 07:11 #1 mdettweiler A Sunny Moo     Aug 2007 USA (GMT-5) 624910 Posts 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
2009-03-28, 18:48   #2
mdettweiler
A Sunny Moo

Aug 2007
USA (GMT-5)

3·2,083 Posts

Quote:
 Originally Posted by mdettweiler 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

2009-03-28, 19:47   #3
mdettweiler
A Sunny Moo

Aug 2007
USA (GMT-5)

3×2,083 Posts

Quote:
 Originally Posted by henryzz 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.

2009-03-28, 23:34   #4
mdettweiler
A Sunny Moo

Aug 2007
USA (GMT-5)

11000011010012 Posts

Quote:
 Originally Posted by Joshua2 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

 2009-03-29, 00:38 #5 mdettweiler A Sunny Moo     Aug 2007 USA (GMT-5) 3·2,083 Posts 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
2009-03-29, 16:18   #6
jasonp
Tribal Bullet

Oct 2004

24·13·17 Posts

Quote:
 Originally Posted by mdettweiler 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.

2009-03-29, 18:40   #7
mdettweiler
A Sunny Moo

Aug 2007
USA (GMT-5)

3×2,083 Posts

Quote:
 Originally Posted by jasonp 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

2009-03-30, 16:25   #8
mdettweiler
A Sunny Moo

Aug 2007
USA (GMT-5)

3·2,083 Posts

Quote:
 Originally Posted by schickel 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.

 2009-04-01, 07:45 #9 Andi47     Oct 2004 Austria 1001101100102 Posts I uploaded the rest of my files to RapidShare doday in the morning: http://rapidshare.com/files/21601685..._20.21.out.bz2 http://rapidshare.com/files/21601769..._21.22.out.bz2 http://rapidshare.com/files/21601858..._22.23.out.bz2 http://rapidshare.com/files/21601932..._23-24.out.bz2 http://rapidshare.com/files/21602258...10.112.out.bz2
2009-04-01, 14:58   #10
mdettweiler
A Sunny Moo

Aug 2007
USA (GMT-5)

3·2,083 Posts

Quote:
 Originally Posted by mdettweiler 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

2009-04-01, 15:40   #11
Andi47

Oct 2004
Austria

46628 Posts

Quote:
 Originally Posted by mdettweiler (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.

 Similar Threads Thread Thread Starter Forum Replies Last Post schickel Aliquot Sequences 26 2011-02-24 23:19 schickel Aliquot Sequences 64 2011-02-19 02:28 jrk Aliquot Sequences 31 2010-12-30 21:33 10metreh Aliquot Sequences 20 2009-08-28 09:49 10metreh Aliquot Sequences 77 2009-05-27 20:39

All times are UTC. The time now is 05:11.

Wed Apr 14 05:11:10 UTC 2021 up 5 days, 23:52, 0 users, load averages: 2.53, 2.38, 2.50