mersenneforum.org Distribution of relations over the sieving interval in SIQS
 Register FAQ Search Today's Posts Mark Forums Read

 2014-05-20, 13:47 #1 mickfrancis   Apr 2014 Marlow, UK 5610 Posts Distribution of relations over the sieving interval in SIQS I was wondering whether anyone might know why the distribution, over the sieving interval, of relations found by SIQS seems to have 2 narrow spikes round about 0.7M either side of 0 (though not quite symmetrical, presumably due to asymmetrical parabolas?) See attachment. The peaks are around 3 times the general level. This is true of full relations, 1-partials and 2-partials. Is this a well-known phenomena? Could it be used in any way to tune the QS algorithms? Cheers, Mick. Attached Thumbnails
2014-05-20, 15:22   #2
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

2×72×109 Posts

Quote:
 Originally Posted by mickfrancis I was wondering whether anyone might know why the distribution, over the sieving interval, of relations found by SIQS seems to have 2 narrow spikes round about 0.7M either side of 0 (though not quite symmetrical, presumably due to asymmetrical parabolas?) See attachment. The peaks are around 3 times the general level. This is true of full relations, 1-partials and 2-partials. Is this a well-known phenomena? Could it be used in any way to tune the QS algorithms? Cheers, Mick.
Hint: how many real roots does a quadratic have?

The term "chicken feet" is also relevant, though it may not appear so at first!

Last fiddled with by xilman on 2014-05-20 at 15:22

2014-05-20, 15:26   #3
bsquared

"Ben"
Feb 2007

7×491 Posts

Quote:
 Originally Posted by mickfrancis I was wondering whether anyone might know why the distribution, over the sieving interval, of relations found by SIQS seems to have 2 narrow spikes round about 0.7M either side of 0 (though not quite symmetrical, presumably due to asymmetrical parabolas?) See attachment. The peaks are around 3 times the general level. This is true of full relations, 1-partials and 2-partials. Is this a well-known phenomena? Could it be used in any way to tune the QS algorithms? Cheers, Mick.
It is well known and has a simple origin as Xilman points out. Klechibar talks about it in "The Quadratic Sieve - introduction to theory with regard to implementation issues".

Early versions of YAFU tried to take advantage of it, but I don't believe the improvement (if any) amounted to much. It is too expensive to check every 'x' to see if you are close to a root or not. As a compromise I think I put a little more effort into all sieve hits within the block containing the root, but the gain at the root offsets the loss away from the root within the block...

Last fiddled with by bsquared on 2014-05-20 at 15:32

 2014-05-20, 15:45 #4 mickfrancis   Apr 2014 Marlow, UK 23·7 Posts Thanks for the replies, guys - interesting. Mick.

 Similar Threads Thread Thread Starter Forum Replies Last Post cgy606 Factoring 1 2016-10-21 13:37 Xyzzy PrimeNet 4 2010-12-11 20:24 CRGreathouse Math 10 2010-04-09 06:23 ThiloHarich Factoring 6 2007-12-03 18:48 fivemack Factoring 7 2007-08-04 17:32

All times are UTC. The time now is 01:39.

Tue May 11 01:39:02 UTC 2021 up 32 days, 20:19, 1 user, load averages: 3.18, 3.02, 2.65