20090507, 06:50  #1 
May 2008
10001000111_{2} Posts 
ggnfs sieving yield wierdness
Has anyone noticed this? Using gnfslasieve4I13e siever*, sieving smaller ranges in separate instances causes the siever to find more relations than if one big range is sieved.
This is confirmed by resieving over a small range at the end of the original range and observing that new relations are found that are missing in the original output. In the case shown in the graph below, this increase is about 25%, but the increase seems to be related to the length of the original range. So what's happening? Is this expected? Does it have anything to do with duplicates being found? * tested with both the regular and "experimental" versions. Last fiddled with by jrk on 20090507 at 07:03 
20090507, 07:08  #2 
"Sander"
Oct 2002
52.345322,5.52471
29×41 Posts 
I think this is because you're probably sieving below the factor base. The siever automatically lowers the factor base for you.
If you're resieving the first part of that range, you probably won't notice any difference. 
20090507, 07:11  #3  
Oct 2004
Austria
2×17×73 Posts 
Quote:
When you do everything in one big range, you will still sieve with alim=3.2M for Q=5M. When you do many small ranges, alim will always be "just below Q", thus yielding more relations. 

20090507, 07:16  #4  
May 2008
3×5×73 Posts 
Quote:
Over a big range like that above, the difference can be significant! Quote:


20090507, 07:21  #5  
May 2008
3·5·73 Posts 
Quote:
I think the alim/rlim should be increased continually with the Q being tested, so that relations are not "lost." Is that possible to do in the program? Serge? A workaround would obviously be to split up all ranges below alim/rlim into smaller chunks and merging them afterward. 

20090507, 07:47  #6 
"Sander"
Oct 2002
52.345322,5.52471
29×41 Posts 
Just wondering. How did you create the graph?

20090507, 08:09  #7 
May 2008
3·5·73 Posts 
cat relations.out  sed e 's/.*,//g'  ./graph1.pl
graph11.pl is just a hackish perl script I put together: Code:
#!/usr/bin/perl $start = 3200000; $end = 5000000; $inc = 5000; $steps = ($end  $start) / $inc; @y = (); while(<STDIN>) { chomp; #input is represented in hexadecimal $x = hex; if($x >= $start && $x <= $end) { $x = int(($x  $start) / $inc); $y[$x]++; } else { } } for($i = 0; $i < $steps; $i++) { $p = $start + $i * $inc; print $p . ' ' . $y[$i] . "\n"; } I made the assumption that the Q value is at the end of the relation line. But actually it is not always. So I throw away the lines where the last value is out of the range, and if the value is in range I assume it is a Q value. Figured it was close enough for my purposes anyway. 
20090507, 09:00  #8 
"Sander"
Oct 2002
52.345322,5.52471
29×41 Posts 
Thanks.
I'm new to Calc and i can't seem to get a nice looking graph in calc. What type of graph do you use? Also, the x and y axes are always the other way around. 
20090507, 09:15  #9 
May 2008
3×5×73 Posts 
I used an "area" graph. And you need to check "first column as label" under "data range".

20090507, 09:54  #10  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2·4,787 Posts 
Quote:
The workaround is indeed what everyone is doing: small ranges. but not too small, because when the siever starts, it spends some time preparing all the above mentioned housekeeping items. This overhead will negate all potential gains, if the intended region is cut too fine. Cut in 10 ranges or so and you will do well. 

20090507, 17:41  #11 
May 2008
3·5·73 Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
CADONFS and GGNFS sieving  ray10may  Msieve  1  20170414 14:19 
SNFS polynomial with very low yield  ryanp  Factoring  9  20130403 06:33 
1870L : Yield Rate  R.D. Silverman  Cunningham Tables  44  20101021 14:32 
Resume sieving in GGNFS  nuggetprime  Factoring  5  20070604 14:42 
Benchmarks wierdness  delta_t  Hardware  3  20040624 13:35 