mersenneforum.org Sieving with NewPGen
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

2005-09-27, 20:01   #23
paulunderwood

Sep 2002
Database er0rr

64108 Posts

Quote:
 we are really dealing with a steady increase in LLR timings
oops! I missed the word "not" in this phrase.

The shorter the range of "n" you are testing the more FFT jumps are going bias the calculation.

 2005-09-28, 00:29 #24 TTn   A1016 Posts Curtis, I like to impress that fact. RMA.NET is set to do fixed n sieving which is already faster than fixed k. Fixed k mode for RMA.NET does need an optimization for large n, but the sweet spot must be clearer than that, for a revision. Someone has to do the math here.... I will credit any contributions with a mathematical basis. TTn Last fiddled with by TTn on 2005-09-28 at 00:29
 2005-09-28, 01:02 #25 TTn   5×132 Posts Paul, I remember simply averaging the range numbers, to get aprox the same formula. We have discussed this before, but could you please elaborate a little more on your formula. What if a machine sieves ultra slow, but can test fast? I will do some timings, and include this in RMA.NET until the complete definition of the sweet spot is clear.
 2005-09-28, 01:31 #26 paulunderwood     Sep 2002 Database er0rr 23·3·139 Posts An LLR test on a 100k number will take 4 times as long as a 50k number. In general, if a number is twice as long as another it will take 4 times a long with LLR. The approxiamate LLR test time is given by c*n^2 where "n" is the number of bits and "c" is a constant. Imagine the curve n^2 ranging from a minimum "n" to a maximum "n". The x-axis measures "n" and the y-axis measures "n^2". The area under the curve is the total amount of work. Clearly most of the work is for large "n" values -- to the right of the graph. The idea is to get the area to the left of the average test equal to the area on the right. Hence the formula I gave. (See the old thread.) This really needs a piccy As I said before, this is an over-simplification because it does not take into account "FFT jumps". Say you calculated by using my formula on 300k-400k but there was a FFT change at 360k -- more sieving would be needed. It is very complicated to hit "the sweet spot" and is further complicated when you take into account differing hardware resources and particpation levels. If you are using a single machine then my fromula will work to calculate the average. Then get the LLR timing and then sieve to that time limit plus some. This will be the most efficient.
 2005-09-28, 01:50 #27 paulunderwood     Sep 2002 Database er0rr 333610 Posts Here's a diagram Attached Thumbnails
 2005-09-28, 01:55 #28 TTn   2·3·1,471 Posts Ok that sounds clearer to me. I wil include this and then fine tune it. RMA.NET will have to look at the complete working environment, and make aproximate adjustments. SSE2, CPU speed, memory, etc. I have most of the code kickin around, but some evidence will be needed for the guestimation.
2005-09-28, 11:18   #29
fatphil

May 2003

3×7×11 Posts

Quote:
 Originally Posted by TTn Ok that sounds clearer to me.
Unfortunately it's wrong.

Fortunately, getting the balance truly correct
1) a fair bit of hassle, involving comparison of several quantities that can only be approximated.
2) doesn't really save you huge amounts anyway.

You're trying to find the global minimum of a semi-hyperbola, and as long as you're sieving sensibly, you're sitting in a pretty flat section anyway. A little bit to the left or a little bit to the right (sieving depth) and you'll barely notice any change in height (total work factor).

Phil

 2005-09-28, 12:12 #30 TTn   11000101102 Posts Phil, That's what I had orinally thought, and found in practice. You are the most credible here, so I will work on this for awhile.
2005-09-28, 12:43   #31
fatphil

May 2003

3×7×11 Posts

Quote:
 Originally Posted by TTn Phil, That's what I had orinally thought, and found in practice. You are the most credible here, so I will work on this for awhile.

Here's the simplest system (but as I said, it's certainly not hassle-free) that's going to be pretty close to optimal.

1) Try to be sieving a range that's much larger than a single FFT-size band. For fixed-k hunts, that's good advice generally as the sieve time is proportional to square root of the range size, so wider sieving is more efficient than seperate narrow sieves. (common knowledge).
2) Find out where the next FFT speed drop is, and find the average time for testing candidates _before_ the speed drop. (=(slowest+fastest)/2, see below.)
3) Sieve until the average (use a longer moving average than the one in NewPGen, Paul uses a very narrow FIR, but a slow IIR works better in my experience) sieving removal rate is equal to the rate measured in (2).
4) Hack off everything that's below the FFT cutoff, and PRP it.
5) (in parallel with 4) only considering everything above the FFT cutoff go to 2

Eventually, you'll be left with only a single FFT size band. But don't worry - that requires no special treatment.

Within each band, the speed should be linear, so there's no need to take into account the percieved quadratic growth which is a artefact of the FFT growth.

Note that the above protocol will cause the sieving cutoffs to be dependent upon the size of the range you initially decide you're interested in.

Phil

 2005-09-28, 13:13 #32 paulunderwood     Sep 2002 Database er0rr 23·3·139 Posts Phil's approach is better... I did say the model I suggested was an over-simplification but it works well enough on a very large "n" range, spanning many FFT changes... When investigating FFT changes, please note the FFT changes are different for non-SSE2 and SSE2-enabled computers Last fiddled with by paulunderwood on 2005-09-28 at 13:21
 2005-09-30, 18:43 #33 VBCurtis     "Curtis" Feb 2005 Riverside, CA 4,243 Posts Phil's explanation makes a lot of sense to me, but I think the effect I tried to explain without rigorous math is not taken into account. Let me try to use more math: When deciding what sieve depth to split off an FFT-band, we should compare not the average sieve time, but the marginal cost of leaving that band in the sieve. Let's say the band in question comprises 10% of the width of the sieve. Since sieve speed is inversely proportional to the square root of sieve width, a marginal change of 10% of width results in a speed change of sqrt (1.10) per p-value tested. This is approximately 5% faster per p if you remove a band 10% of the original sieve. However, if you leave the band in, you find 10% more factors per p-value checked, with only a 5% reduction in speed per p-value; this is because the sieve has a constant probability of finding a factor per p,k pair checked, so leaving in the 10% k-values means 10% more factors found per p-value. I believe this hidden increase in efficiency on the margin is not lost until average sieve time is double the time to LLR an average member of the band to be split off. I'll try to make a more mathematical argument of this last part next time-- I dont' have time to flesh it out presently. If you see any holes in the initial part of my explanation, please comment-- I've not read this anywhere, and tried empirically to find this relationship with a few powers I had... playing with marginals led me to this half-guess. -Curtis

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post fivemack And now for something completely different 3 2017-05-16 17:55 Cybertronic Factoring 0 2014-03-22 10:07 MooooMoo Riesel Prime Search 16 2008-12-11 11:46 geoff Sierpinski/Riesel Base 5 11 2006-07-10 01:10 jasong Software 18 2005-12-30 20:23

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

Wed Aug 12 07:36:57 UTC 2020 up 26 days, 3:23, 1 user, load averages: 1.23, 1.40, 1.43

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