NFS@home challenge

Associate
Joined
12 Dec 2012
Posts
73
Location
Milton Keynes , UK
Okay, enjoy your holiday/work trip :)

Just so you know your audience, I have absolutely no idea what "it is very difficult to get right maximum "q" because we are getting less relations than expected" means :confused:

First sorry for the late reply.
Let me try to explain this in a simple manner :D:

--------------------------------------------------------------------------
2. Sieving for Relations

The sieving step is not the theoretically most complex part of the algorithm of factorization, but it is the most time consuming part because it iterates over a large domain with some expensive calculations like division and modulo, although some of these can be avoided by using logarithms.
In general optimization of the sieving step will give the biggest reduction in actual running time of the algorithm. It is easy to use a large amount of memory in this step, and one should be aware of this and try to reuse arrays and use the smallest possible data types. The factor bases can for record factorizations contain millions of elements, so one should try to obtain the best on-disk/in-memory tradeoff.

The purpose of the sieving step is to find usable relations, i.e. elements (a, b) with the following properties
• gcd(a, b) = 1
• a + bm is smooth over the rational factor base
• b^deg(f)*f(a/b) is smooth over the algebraic factor base

Finding elements with these properties can be done by various sieving methods like the classical line sieving or the faster lattice sieving, the latter being used at NFS@Home.

The lattice sieving was proposed by John Pollard in "Lattice sieving, Lecture Notes in Mathematics 1554 (1991), 43–49.". The factor bases are split into smaller sets and then the elements which are divisible by a large prime q are sieved. The sizes of the factor bases have to be determined empirically, and are dependent on the precision of the sieving code, if all smooth elements are found or if one skips some by using special-q methods.

One advantage the lattice siever has is the following. The yield rate for the line siever decreases over time because the norms get bigger as the sieve region moves away from the origin. The lattice siever brings the sieve region "back to the origin" when special-q's are changed. This might be its biggest advantage (if there is one).
--------------------------------------------------------------------------

So we were finding less elements per region than we were expecting to be able to build the matrix for the post-processing phase.

Carlos
 

PDW

PDW

Associate
Joined
21 Feb 2014
Posts
1,867
Hi Carlos, thanks for the explanation you gave earlier, I did read it and not sure I fully mastered the concept (I'd probably need a second lesson for that) but it did help.

How many wu are left to do now ?
 
Associate
Joined
12 Dec 2012
Posts
73
Location
Milton Keynes , UK
Not sure how much is still left to do regarding G2m1285. Probably we will go up to 3600M (my guess, still awaiting for admin feedback).--->quick wu's: 209,000 wus. My last wu received as now is 3182M.

Normal wu's from G6p490b from q=260M to 1500M (redo work 620,000 wu's).
 

PDW

PDW

Associate
Joined
21 Feb 2014
Posts
1,867
Got the reply.

Greg queued through 3700M, means we have ~239k tasks still to process.
Looks like the majority of the ~239k quicker wu's (G2m1285) have been done as the G6p490b wu's are coming through now.

Once these G6p490b wu's are done is that your 'emergency' over ?
 
Associate
Joined
12 Dec 2012
Posts
73
Location
Milton Keynes , UK
7/10-14/10 Need Faster Ships, Pirates Ahoy part deux NFS@Home Challenge

http://boincstats.com/en/stats/challenge/team/chat/815

Name Need Faster Ships, Pirates Ahoy part deux NFS@Home Challenge
Status Upcoming
Project NFS@Home
Issued by Anguillan Pirates
Start time 2016-10-07 00:00 UTC
End time 2016-10-14 00:00 UTC
Late entrants allowed? Yes
Number of teams participating » 7
Number of users participating 0
 
Back
Top Bottom