c176 polynomial search - Page 3

bdodson · 2010-09-10, 10:10

Quote:

Originally Posted by henryzz

... it looks to me that bruce is suffering a big reduction in the number of good new polynomials he has found since the first low run.

Perhaps I ought to have agreed, to start with (except that the first run
wasn't from a low range). The flare from c5 = 145080 is still running, and
has dwarfed any of the early flares (and the flairs, too)

Code:

     63 c5:  120480   (early first)
        ...
    139 c5:  123660
    332 c5:  142560
    340 c5:  100020
    354 c5:  240
   2963 c5:  145080

While best-polyn-to-date haven't always come from large flares, and
some that are large consist entirely of polyn that aren't very good,
this one is rather remarkable. Picking up, by arrival time, from the
previous report

Code:

save 2.680206e-17 -8.5782 199960907.66 1.212357e-13 rroots 5
   ---
save 2.761258e-17 -8.8536 238251697.18 1.249638e-13 rroots 5
save 3.103217e-17 -9.2806 258576898.60 1.352726e-13 rroots 5
save 2.706395e-17 -8.8637 259556060.65 1.235436e-13 rroots 5
save 2.839671e-17 -8.9586 253348481.44 1.268833e-13 rroots 5
save 2.753216e-17 -8.9179 261424828.60 1.248925e-13 rroots 5

and by best-to-date

Code:

 grep norm msieve.dat.p | sort -gk7 | tail 
# norm 2.626962e-17 alpha -8.542450 e 1.204e-13 rroots 5
# norm 2.645394e-17 alpha -8.558684 e 1.208e-13 rroots 5
# norm 2.680206e-17 alpha -8.578218 e 1.212e-13 rroots 5
# norm 2.750309e-17 alpha -8.147588 e 1.217e-13 rroots 5  c5=196680

# norm 2.677511e-17 alpha -6.875759 e 1.233e-13 rroots 5  c5=120480
     (best before 145080)

# norm 2.706395e-17 alpha -8.863732 e 1.235e-13 rroots 5
# norm 2.753216e-17 alpha -8.917859 e 1.249e-13 rroots 5
# norm 2.761258e-17 alpha -8.853597 e 1.250e-13 rroots 5
# norm 2.839671e-17 alpha -8.958598 e 1.269e-13 rroots 5
# norm 3.103217e-17 alpha -9.280638 e 1.353e-13 rroots 5

Aside from matching the previous best, 1.353e-13 is in Tom's
"white swan" range; and meets and/or beats Serge's edge of
best possible for this search (1.35, not just 1.3).

On the distribution of CPUtime between Stage1 and Stage2 (to the
extent measured for _very_ small c5's)

Code:

03:38:37 ./msieve_gpu -g 1 -l msieveg1d.log -v -np1 3481,60000

reports 3hrs38min of CPUtime from just short of 22hrs of walltime in which

Code:

line count:  5650 hits

from 

searching leading coefficients from 3481 to 60000
   ...
coeff 3540-5880 2052640438 2257904481 2257904482 2483694930
------- 2052640438-2093693246 2393378749-2438536838
------- 1940678231-1977998966 2632716627-2682390525
coeff 5940-8280 2138478398 2352326237 2352326238 2587558861
------- 2266787099-2309556666 2399372762-2446419286
coeff 8340-10680 2201353983 2421489381 2421489382 2663638320
------- 2377462299-2421489378 2615208530-2663638317

That seems to indicate most of the walltime spent on the card, rather
than the CPU; but -np2 also isn't taking very much CPUtime, so
maybe this is a small c5 anomaly. Processing the first 2000 hits
took just 1hr20min elapsed (wall-) time.

As long as I'm waiting to see what else c5=145080 finds, I may as
well follow this np1/np2 for a while longer; then switch to a larger
gnfs candidate. -Bruce

bdodson · 2010-09-12, 13:18

Quote:

Originally Posted by bdodson

...
On the distribution of CPUtime between Stage1 and Stage2 (to the
extent measured for _very_ small c5's)
...
That seems to indicate most of the walltime spent on the card, rather
than the CPU; but -np2 also isn't taking very much CPUtime, so
maybe this is a small c5 anomaly. Processing the first 2000 hits
took just 1hr20min elapsed (wall-) time.

As long as I'm waiting to see what else c5=145080 finds, I may as
well follow this np1/np2 for a while longer; then switch to a larger
gnfs candidate. -Bruce

With apologies to those already tired of hearing about the local news
here (and a note that the sustained effort out at CalState, Fullerton has
perhaps more interesting polyn search benchmarks from several larger
numbers), the disclaimers about "small c5"'s now appear as though they
ought to read "early results" for small c5's. I submitted "kill -TERM"'s to
the -np1 and to the -np that was/is running c5=145080; but while the
np1 responded promptly, the np appears to be waiting for 145080 to
finish. I'd send a "kill -KILL", but since yesterday morning this c176
was promoted off of the 3- extention and onto the regular Cunningham
list as a 4th hole (presently reserved for Batalov+Dodson; with "thanks!!"
to Sam and to Yoda). So anyway, the gpu is done with its share of polyn
selection, but the gpu binaries are still running two np2's and (apparently)
np is waiting for Stage2 on 145080 to reach a break to respond to signals.

To get to the nominal headline first, three-of-the-top-five rated polyn
now occur with small c5's, under 18000 (where the -TERM hit)

Code:

# norm 2.761258e-17 alpha -8.853597 e 1.250e-13 rroots 5
---
# norm 2.806513e-17 alpha -8.471530 e 1.260e-13 rroots 5   c5 = 7560
# norm 2.790914e-17 alpha -8.648849 e 1.264e-13 rroots 3   c5 = 7560
# norm 2.839671e-17 alpha -8.958598 e 1.269e-13 rroots 5
# norm 2.785574e-17 alpha -7.113239 e 1.270e-13 rroots 5   c5 = 8580
# norm 3.103217e-17 alpha -9.280638 e 1.353e-13 rroots 5

with the other three (of six) previously reported from the c5 = 145080
flare. The line count of c5's in msieve.dat.p is at

Code:

        ...
     12 c5:  13920    <--- location of 2nd np2
        ...
    114 c5:  12960
    137 c5:  8580      <---- from 2nd np2
    139 c5:  123660
    332 c5:  142560
    340 c5:  100020
    354 c5:  240
   5708 c5:  145080  <--- location of remaining np
   6795 c5:  7560     <--- location of 1st np2

We can see that the collection of polyn for 145080 isn't uniquely large;
and that the second best poly was one of only 137 candidates. I fished
out the newly identified highly rated polyns below (so just the one with
1.35 isn't reported yet).
-Bruce

Code:

# norm 2.806513e-17 alpha -8.471530 e 1.260e-13 rroots 5
skew: 553721074.80
c0:  124519509240644820922560373929785496711175492755
c1:  1193499485408666503710797972783373896059
c2: -2646711936488850954171429914901
c3: -26038470450919022082759
c4:  13526011459006
c5:  7560
Y0: -18058238133009811502847081224006734
Y1:  5509079651176805887
---

# norm 2.790914e-17 alpha -8.648849 e 1.264e-13 rroots 3
skew: 611589605.25
c0: -37503781939275569445802751466195314559825228465
c1:  598757070587002724981366566600288600179
c2: -3707876206757612809340301852057
c3: -25278307391597234124775
c4:  14047066163806
c5:  7560
Y0: -18058238057069814905925981645761042
Y1:  5509079651176805887
---

# norm 2.839671e-17 alpha -8.958598 e 1.269e-13 rroots 5
skew: 253348481.44
c0: -20403390107361823709873441289832316809891232064
c1:  886741325515135479165293544651036556648
c2: -4508860255168085764368144453482
c3: -66243854630047838427977
c4:  35022585165222
c5:  145080
Y0: -10001341368940810747067089539658913
Y1:  10429133285414622193
---

# norm 2.785574e-17 alpha -7.113239 e 1.270e-13 rroots 5
skew: 240754423.53
c0:  5814114499023510711456468786269637963650793125
c1:  40070122427445106583426853157070098265
c2: -788541287107650164757284402427
c3: -2937994679201950103173
c4:  17925963781022
c5:  8580
Y0: -17606874120753992130453980142415408
Y1:  6345257025977432263

bdodson · 2010-09-13, 20:06

Quote:

Originally Posted by bdodson

... I submitted "kill -TERM"'s to
the -np1 and to the -np that was/is running c5=145080; but while the
np1 responded promptly, the np appears to be waiting for 145080 to
finish. I'd send a "kill -KILL", but ... So anyway, the gpu is done with its
share of polyn selection, but the gpu binaries are still running two np2's
and (apparently) np is waiting for Stage2 on 145080 to reach a break to
respond to signals.

Some things are clearer today. The -np1 on 1,60000 found c. 13000
stage1 hits before the -TERM. I did the first 2000 as a test; set the
next 3000 as one of the np2's, and the last c. 8000 as the other. This
second one finished, c. 48hrs (all on the CPU), with the above 1.27 as
it's best polyn. That leaves the original -np (both stages) _still_ running
on c5=145080; and the remaining np2 (with "just" 3000 hits to process),
which has been working on c5= 7560 for some days now. Just to rule out
any tenative hypothesis that the good polyn ought to show up early in
these flares, both have just within a day at the office found new 1.28's,
one each; for new 2nd and 3rd best polyn:

Code:

# norm 2.785574e-17 alpha -7.113239 e 1.270e-13 rroots 5
   ---
# norm 2.850602e-17 alpha -9.210061 e 1.280e-13 rroots 5  c5=145080
# norm 2.868109e-17 alpha -8.699197 e 1.286e-13 rroots 5  c5=7560
# norm 3.103217e-17 alpha -9.280638 e 1.353e-13 rroots 5

These were near the end of

Code:

       ...
    332 c5:  142560
    340 c5:  100020
    354 c5:  240
    570 c5:  14760
       ----
   7002 c5:  145080
  10230 c5:  7560

The smaller c5 seems to be producing stage2 hits at about 3-times
the rate of c5=145080.

Just to keep the cards from going idle, I tried some np1's on a larger
gnfs candidate from the 2+ list. They're running nicely, under 1hr/day
on the cpu, with the other 23hrs on the cards. Not sure whether Stage2
makes use of 2+ arithmetic (as gmp-ecm does), but those poly just flew
by np2; and ruined any hope that flares oughtn't to get too large. From
the first 2000 Stage1 hits:

Code:

    1560 c5:  120060
    2023 c5:  5640
    2821 c5:  129600
    3220 c5:  123420
  105677 c5:  120960

with all 100000 polyn with c5=120960 having tiny rating, even relative
to this harder search.

-Bruce

bdodson · 2010-09-15, 15:03

Quote:

Originally Posted by bdodson

...

Well, I finally got an end for c5 = 145080; after a reboot, so far as
I can see, I'd need to start from the beginning --- or maybe this part
of the range might not even show up. Since c5 = 7560 was in a save
file from -np1, I restarted from [2000, 2999] of the c. 13000 stage1 hits,
and confirmed that I was getting polyn that I hadn't seen before. A whole
bunch of new/good polyn, including _two_ new bests.

Code:

# norm 2.709812e-17 alpha -8.222548 e 1.255e-13 rroots 3
# norm 2.719233e-17 alpha -8.144970 e 1.255e-13 rroots 3
# norm 2.743146e-17 alpha -7.766738 e 1.255e-13 rroots 3
# norm 2.733592e-17 alpha -8.285985 e 1.263e-13 rroots 1
# norm 2.754978e-17 alpha -8.255184 e 1.268e-13 rroots 3
# norm 2.764177e-17 alpha -8.330199 e 1.272e-13 rroots 1
# norm 2.780047e-17 alpha -8.081462 e 1.274e-13 rroots 3
# norm 2.840177e-17 alpha -7.892712 e 1.282e-13 rroots 3  (5th best)
# norm 2.870811e-17 alpha -8.708214 e 1.305e-13 rroots 1
# norm 3.170032e-17 alpha -8.709547 e 1.387e-13 rroots 3

That leaves just the three above 1.300e-13 to report

Code:

# norm 3.170032e-17 alpha -8.709547 e 1.387e-13 rroots 3
skew: 520935104.12
c0:  161347649041444902646279140289423928022928671555
c1: -690653788486132004105649845828345247513
c2: -3261346058519917140068978735735
c3:  5465732411856827411801
c4:  9849935368188
c5:  7560
Y0: -18058238642554513946628585892475318
Y1:  5609683928107982551
---

# norm 3.103217e-17 alpha -9.280638 e 1.353e-13 rroots 5
skew: 258576898.60
c0:  5908030774513404799643707422263389157575605576
c1:  863693723853490458118346417728341545188
c2: -1468054763593862381835834684362
c3: -68027025556376964351977
c4:  24079563465222
c5:  145080
Y0: -10001341526269500924189372632160413
Y1:  10429133285414622193
---

# norm 2.870811e-17 alpha -8.708214 e 1.305e-13 rroots 1
skew: 525113637.59
c0:  75543501240353454870499020372978382217716851296
c1:  422641763215625857583088121256778320512
c2: -3547521122184332434884814412474
c3:  4756113253311922535993
c4:  9143818931988
c5:  7560
Y0: -18058238747345255309698047471414597
Y1:  5609683928107982551

-Bruce

Batalov · 2010-09-16, 17:24

Quote:

Code:

# norm 3.103217e-17 alpha -9.280638 e 1.353e-13 rroots

Nice!

bdodson · 2010-09-16, 21:01

Quote:

Originally Posted by Batalov

Quote:

Code:

# norm 3.103217e-17 alpha -9.280638 e 1.353e-13 rroots

Nice!

Nice enough to outweigh the 1.387e-13? I can definitively answer
jrk's cpu bound question for the range

Code:

            ...
        {185, 1.00E+028, 3.12E+026, 1.00E-014},
        {190, 6.00E+028, 1.82E+027, 4.00E-015},

        /* contributed by Serge Batalov */

where -np1 is spending _more_ than (23/24)-hours/day on the c2050 card;
under 1-hour-day on the CPU. -Bruce

jrk · 2010-09-16, 22:59

Quote:

Originally Posted by bdodson

where -np1 is spending _more_ than (23/24)-hours/day on the c2050 card;
under 1-hour-day on the CPU. -Bruce

Thanks Bruce, that answers my question. I guess I was worrying for nothing.

jasonp · 2010-09-17, 12:43

The alpha is quite nice for degree 5 (all of the best polynomials have massive skew, so there is a large search space for the root sieve in stage 2). If the difference in E value is so small then test sieving is the only way to tell which polynomial is better.

bdodson · 2010-09-17, 15:49

Quote:

Originally Posted by jasonp

The alpha is quite nice for degree 5 (all of the best polynomials have massive skew, so there is a large search space for the root sieve in stage 2). If the difference in E value is so small then test sieving is the only way to tell which polynomial is better.

Ah. Thanks; Serge has decided on the poly with large alpha. And
3 LPs. 5,403+ will finish sieving in 2-3 days; and I'll switch to this
c176 gnfs.

I was trying to locate the part of the code where the stage1 search
space gets split into halves; the halves split into 10's, and then a
single pair is actually searched.

Ah; some other things. In the stdout from np1, what are the lines

Code:

coeff 151260-153600 10951738255 12046912080 12046912081 13251603289
------- 11499325165-11608842547 12287850321-12408319441
------- 10553493222-10653054478 14444247579-14576763611
coeff 153660-156000 10968857378 12065743115 12065743116 13272317427
------- 11078545951-11188234524 12186400547-12307057978

saying? I recognize "coeff 151260-153600" in the first line as a range of
c5's (=A5's), and that the 2nd line runs for a while, then the 3rd line runs
until the range finishes and the next range of coeffs starts. But I wasn't
able to locate where the 2nd & 3rd lines are written (and the meaning of
those ranges). Uhm, I do see that the ranges bound p and q; as in

Code:

poly 12 p 11550451993 q 12350885161 coeff 142658306123186575873
poly 14 p 11579846911 q 12396920587 coeff 143554442565284256757

for 

------- 11499325165-11608842547 12287850321-12408319441

So maybe that's the first range searched (one of the 10s), from the first
half; and the second part of the pair is

------- 10553493222-10653054478 14444247579-14576763611

is one of the 10s from the second half? Then p and q determine the coeff;
or that's also being searched?

The other thing I was wondering about is how to predict from the stage1
output that stage2 will be in an extended flare. I can count a5's that
are repeated in the msieve.dat.m triples; for example, over 1000 for
"c5: 7560" in the stage1 reports ... but then each of them (or _some_
of them) gave bunches of stage2 reports. Not clear that repeated
triples with a single c5=a5 (and different p, m's of (a5,p,m)) will correlate
single triples that give multiple stage2 hits. -Bruce

(thanks to the mod for c176 thread!)

jasonp · 2010-09-17, 21:00

For 'coeff A-B C D E F', the min and max value of A5 is A and B, and C/D and E/F give the min and max values of the two groups of factors that could potentially be multiplied to form the leading rational poly coefficient. The lines that start with the dashes give the actual ranges that are searched.

If there is still time left for the coeff batch and an actual range is finished, then E/F is multiplied and C/D is divided by a small scale factor (usually 1.1), one piece of each new range is randomly selected and the search performed again. Every member of the C/D range is coprime to every member of the E/F range, so this has the effect of grinding through more pairs that are guaranteed not to have been search before.

I wish I knew how to predict when a stage 1 hit would predict lots of stage 2 hits. One telltale sign is that the size optimization at the beginning of stage 2 detects an unusually good polynomial size; this means the root sieve will run for a longer time.

bdodson · 2010-09-23, 17:32

Quote:

Originally Posted by jasonp

For 'coeff A-B C D E F', the min and max value of A5 is A and B, and C/D and E/F give the min and max values of the two groups of factors that could potentially be multiplied to form the leading rational poly coefficient. The lines that start with the dashes give the actual ranges that are searched.

So I had

Code:

prospective range for algebraic coef c5 = a5 between 151260-153600

C  D  E=D+1 F  == 10951738255 12046912080 12046912081 13251603289

with actual search range taken as

------- 11499325165-11608842547 12287850321-12408319441

from which a stage1 hit was

"poly 12 p 11550451993 q 12350885161 coeff 142658306123186575873"

in which the triple (a5, p, m) with rational polyn px + m == Y1*x +Y0

has coeff Y1 =  11550451993 * 12350885161,

  where 11550451993 = (106019) * (108947) and
        12350885161 = (23^2) * (97) * (313) * (769).

Quote:

If there is still time left for the coeff batch and an actual range is finished, then E/F is multiplied and C/D is divided by a small scale factor (usually 1.1), one piece of each new range is randomly selected and the search performed again. Every member of the C/D range is coprime to every member of the E/F range, so this has the effect of grinding through more pairs that are guaranteed not to have been search before.

Referring to an extra piece of search space, which in this case was

Code:

------- 10553493222-10653054478 14444247579-14576763611 (actual)

tacked on to fill-out the time for this range of algebraic c5's, with
reports p, q -> Y1 = p*q disjoint from the initial search space. I can
see that this member of the C-to-D range is in fact coprime to the
member of the E-to-F range; and wonder whether that's a condition
on the search? This is where the massively parallel gpu search is
occuring (if I'm reading correctly), and worth hearing some more details.

Quote:

I wish I knew how to predict when a stage 1 hit would predict lots of stage 2 hits. One telltale sign is that the size optimization at the beginning of stage 2 detects an unusually good polynomial size; this means the root sieve will run for a longer time.

Uhm, so this is hoping for stage1 hits with long running root sieves in
stage2; as a good thing. If I recall correctly, I was thinking about an
early abort for long running root sieves, giving many candidates of which
all are uselessly too small. That would leave more time for ones that
have a prospect of finding good candidates. Perhaps I'm just seeing a
need for further parameter adjustment for c187's; and as this is in
stage2, not necessarily specific to fermi. I finally gave-up and kill -KILL'd
a recent one

Code:

grep Y1 2p956/msieve-g01c.dat.p |  uniq -c |  tail -5
    387 Y1:  155444495204609427433
    203 Y1:  115450866939885663641
    208 Y1:  155083341429764095103
    426 Y1:  154618866911625961819
5597766 Y1:  115751738824867352543

grep c5 2p956/msieve-g01c.dat.p |  uniq -c |  tail -5
    387 c5:  168300
    203 c5:  49740
    208 c5:  167460
    426 c5:  168000
5597766 c5:  50160

There were actually three stage1 hits for this c5; three distinct Y1's,
but this was the only Y1 with a stage2 hit (I restarted msieve.dat.m
from just after the triple with the Y1 having 5.6M stage2 hits). An
extreme version of the 100000 hits above from the first day's searching;
all of the polyn were well below the range of interest. Well. Only two
hits that remained in the top10; in the 9th and 10th spot

Code:

# norm 1.707519e-18 alpha -8.446704 e 2.249e-14 rroots 5
# norm 1.713460e-18 alpha -8.583609 e 2.268e-14 rroots 5
# norm 1.782813e-18 alpha -7.635334 e 2.341e-14 rroots 3
# norm 1.806334e-18 alpha -7.963221 e 2.369e-14 rroots 3
# norm 1.816785e-18 alpha -7.979300 e 2.377e-14 rroots 3
# norm 1.837596e-18 alpha -7.623530 e 2.377e-14 rroots 3
# norm 1.824306e-18 alpha -7.984188 e 2.385e-14 rroots 3
# norm 1.996707e-18 alpha -8.511119 e 2.469e-14 rroots 3
# norm 1.945834e-18 alpha -8.285400 e 2.492e-14 rroots 3

This was the last of the results from the pre-official release of 1.47.
By contrast, the first new_best from the binary from the updated
trunk-files

Code:

Msieve v. 1.48
     ---
  36961 c5:  180120
1582750 c5:  182280

This flare started early with interesting polyn

Code:

Sep 19th stage2b/save2.469.txt
  --
Sep 21 21:16 stage2b/save2.268.txt  (w. 2.249) 
  ---
Sep 23 01:40 stage2b/save2.369.txt  (w. 2.341)
Sep 23 07:18 stage2b/save2.377x2.txt
Sep 23 10:40 stage2b/save2.492.txt
 
  after start at:  Sep 22 21:09 msieveg01e.log

Nothing here worth writing about ... a long way from 2.7 ...
-Bruce

2010-09-16, 17:24	#27
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3⁶·13 Posts	Quote: Code: # norm 3.103217e-17 alpha -9.280638 e 1.353e-13 rroots Nice!

2010-09-17, 21:00	#32
jasonp Tribal Bullet Oct 2004 3,541 Posts	For 'coeff A-B C D E F', the min and max value of A5 is A and B, and C/D and E/F give the min and max values of the two groups of factors that could potentially be multiplied to form the leading rational poly coefficient. The lines that start with the dashes give the actual ranges that are searched. If there is still time left for the coeff batch and an actual range is finished, then E/F is multiplied and C/D is divided by a small scale factor (usually 1.1), one piece of each new range is randomly selected and the search performed again. Every member of the C/D range is coprime to every member of the E/F range, so this has the effect of grinding through more pairs that are guaranteed not to have been search before. I wish I knew how to predict when a stage 1 hit would predict lots of stage 2 hits. One telltale sign is that the size optimization at the beginning of stage 2 detects an unusually good polynomial size; this means the root sieve will run for a longer time. Last fiddled with by jasonp on 2010-09-17 at 21:03

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Tweaking polynomial search for C197	fivemack	Msieve	38	2011-07-08 08:12
109!+1 polynomial search	fivemack	Factoring	122	2009-02-24 07:03
5^421-1 polynomial search	fivemack	Factoring	61	2008-07-21 11:16
6^383+1 by GNFS (polynomial search; now complete)	fivemack	Factoring	20	2007-12-26 10:36
GNFS polynomial search tools	JHansen	Factoring	0	2004-11-07 12:15

2010-09-17, 12:43	#30
jasonp Tribal Bullet Oct 2004 110111010101₂ Posts	The alpha is quite nice for degree 5 (all of the best polynomials have massive skew, so there is a large search space for the root sieve in stage 2). If the difference in E value is so small then test sieving is the only way to tell which polynomial is better.