 mersenneforum.org Sieve implementation questions (CADO/lasieve)
 Register FAQ Search Today's Posts Mark Forums Read 2019-11-28, 14:09 #1 olorin   Nov 2019 1 Posts Sieve implementation questions (CADO/lasieve) I'm very interested in implementation of algorithms of computer algebra and am currently studying sieving algorithm. I have read several papers about sieving (including Franke-Kleinjung about vector sieveing), but there is still a question of implementation. More precisely, I'm interesting in the question how does lasieve use such a small amount of RAM (about 400MB for 640-bit modulus with CADO parameters $$I15$$ and factor base bound $$limFB = 1.3 * 10^8$$). As I get some of the sieving algorithm aspects (such like L1-cache hack, etc), the main idea is to sieve firstly medium ideals (i.e. $$(p,r)$$ such that $$I < p < limFB$$) and save their hits into some array (denote it by $$T$$). Simple estimation of $$|T|$$ (number of elements) is given by the formula $$|T| \approx I*J*(log(log(limFB)) - log(log(I)))$$, so for CADO parameters for 640bit modulus ($$I=2^15$$, $$limFB = 1.3 * 10^8$$) we get estimation $$|T| \approx 314 * 10^6$$. If we use 4 Bytes for one hit we get an estimated memory usage of about 1.2 GB of RAM (and here we don't take into account that we also need to store factor bases). My question is: how can we split sieving process for saving RAM? And more precisely how does lasieve use so little memory (about 400MB, as I mentioned earlier)? I didn't find the answer to this question in open source papers. Obvious way, of course, is to split sieving rectangle $$[-I/2, I/2] \times [1, J]$$ geometrically into two $$[-I/2, I/2] \times [1, J/2]$$ and $$[-I/2, I/2] \times [J/2, J]$$ (this approach is mentioned in Franke-Kleinjung "Continued fractions and lattice sieving"). At the same time, I found in lasieve cweb commentaries that there is also an approach to split sieving area by the oddness type (i.e. to consider only points $$(x,y)$$ in the sieving area such that $$x$$ and $$y$$ are not divisible by 2 at the same time). This approach gives reduction of RAM by 2*2=4 times (and probably we also save some time: we sieve only 3 subareas and ignore the 4th where both coordinates are even). My question here is: Am I right that this approach is useful? Is it used, for example, in lasieve or CADO? I am also interested in the following. For the second splitting approach we also need to find a starting point in the sieving area for every medium ideal (and this point must be with the corresponding remainder of dividing by 2). Is there any fast algorithms to find this starting points? What happens if instead of 2 we use 6 = 2 * 3 (and consider only $$(x,y)$$ such that $$x$$ and $$y$$ are coprime mod 6)? It seems like we can reduces RAM by 6*6=36 times (but we also spend more time finding starting points).  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post mklasson Factoring 81 2012-05-06 21:30 abhiiitkgp Homework Help 4 2011-10-31 13:22 fivemack Factoring 8 2010-04-27 18:59 Shaopu Lin Factoring 3 2009-11-18 18:42 nuggetprime Programming 56 2008-10-27 22:45

All times are UTC. The time now is 07:57.

Sun Oct 17 07:57:22 UTC 2021 up 86 days, 2:26, 0 users, load averages: 1.21, 1.48, 1.40