mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2014-05-20, 13:47   #1
mickfrancis
 
Apr 2014
Marlow, UK

5610 Posts
Default 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
Click image for larger version

Name:	sieveHist.JPG
Views:	108
Size:	34.9 KB
ID:	11201  
mickfrancis is offline   Reply With Quote
Old 2014-05-20, 15:22   #2
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

52·7·61 Posts
Default

Quote:
Originally Posted by mickfrancis View Post
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
xilman is offline   Reply With Quote
Old 2014-05-20, 15:26   #3
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

22·859 Posts
Default

Quote:
Originally Posted by mickfrancis View Post
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
bsquared is offline   Reply With Quote
Old 2014-05-20, 15:45   #4
mickfrancis
 
Apr 2014
Marlow, UK

23·7 Posts
Default

Thanks for the replies, guys - interesting.

Mick.
mickfrancis is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
SIQS on GPU cgy606 Factoring 1 2016-10-21 13:37
PrimeNet logout interval? Xyzzy PrimeNet 4 2010-12-11 20:24
Interval calculations with a given alpha CRGreathouse Math 10 2010-04-09 06:23
partial relations in SIQS ThiloHarich Factoring 6 2007-12-03 18:48
More relations mean many more relations wanted fivemack Factoring 7 2007-08-04 17:32

All times are UTC. The time now is 14:15.

Fri May 7 14:15:43 UTC 2021 up 29 days, 8:56, 0 users, load averages: 3.61, 3.10, 2.84

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