mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Msieve (https://www.mersenneforum.org/forumdisplay.php?f=83)
-   -   New polynomial finder discussion (https://www.mersenneforum.org/showthread.php?t=11023)

jasonp 2008-12-31 13:36

Msieve needs the same target norm that pol51m0b does, along with the first (largest) norm given to pol51opt and the target Murphy E. It also needs a scaling factor from Bernstein's score to Murphy's score, but that obeys a relatively simple power law and I can figure out reasonable values for that myself.

Batalov 2009-01-15 22:17

a good poly by msieve for a gnfs-130
 
...better than the one found by pol51 -- by production value (estimated in -c 1000 over several places in the expected sieving region)
[code]# norm 5.413e+18 alpha -[B]8.45[/B]6950 skew 855181.87 e 1.824e-12
Y0: -11750073960431641866715298
Y1: 208135619003941
c0: -10666801272277680324496112832774045
c1: 27444994430844120930121873117
c2: 18634510035914201518841
c3: -72898361182735245
c4: -9365721948
c5: 32400
n: 11+3,181[/code]
I ain't always negative. :smile:
[spoiler]"We call him Neutron, because he's always so positive!"[/spoiler]

fivemack 2009-02-02 16:24

[QUOTE=jasonp;156019]Msieve needs the same target norm that pol51m0b does, along with the first (largest) norm given to pol51opt and the target Murphy E. It also needs a scaling factor from Bernstein's score to Murphy's score, but that obeys a relatively simple power law and I can figure out reasonable values for that myself.[/QUOTE]

If you don't mind, I'll devote a CPU-month or so to trying to find half-way decent values for say C145 through C190 in five-digit increments. I don't think it's that hard a problem - I've just done it for 109!+1 and it took one CPU-morning - however, the parameters do have to be right to within about a factor two to get sensible speeds and yields, and the present ones are [b]not[/b] right much beyond C140 (they look very much as if someone fitted an exponential to data up to C140 and extrapolated...); I ran 24 hours on four cores on the C159 from 5^403-1 and got nothing.

If I'm doing ten data points I'll have to automate the optimisation anyway, so I can redo it without much effort if the internals change enough to invalidate the parameterisation ... I'll be kludging in something to take the three parameters from the command line, and maybe some attempt to measure them automatically.

jasonp 2009-02-02 16:45

I don't mind at all, since I don't have the time or CPU resources to contemplate doing so myself. The current code will perform linear interpolation between table entries, feel free to suggest alternatives if that wouldn't be good enough.

fivemack 2009-02-02 18:06

[QUOTE=jasonp;161387]I don't mind at all, since I don't have the time or CPU resources to contemplate doing so myself. The current code will perform linear interpolation between table entries, feel free to suggest alternatives if that wouldn't be good enough.[/QUOTE]

I think the behavior is near enough to exponential that linear interpolation between log(e) followed by exponentiation would be better, particularly if I'm only sampling at five-digit intervals.

The 300-hour limit needs to be very much relaxed for these larger N (though I suspect users will generally be splitting the range over many CPUs with the -np lo,hi option)

jrk 2009-06-29 01:31

msieve 1.42 found these two polynomials for a c146:

[code]n: 26189038648693542347544128379203981085928807133100545352808625328304272178273019151767946445367950374936152823381598061806704210499765820991870233
# norm 3.271358e-14 alpha -7.032774 e 8.217e-12
skew: 1232509.71
c0: 854935704823969678446428150388307472
c1: 2628352529802281674541428166656
c2: -2269870450124465525853056
c3: -7665339912013281796
c4: 2647460484669
c5: 544320
Y0: -8638748650791516848363247201
Y1: 45290154778406353
[/code]

[code]n: 26189038648693542347544128379203981085928807133100545352808625328304272178273019151767946445367950374936152823381598061806704210499765820991870233
# norm 3.088359e-14 alpha -4.726567 e 8.244e-12
skew: 224520.44
c0: -330054480572167115879510887000400
c1: 1704252146819274174812063226
c2: 41778842653281650261625
c3: -160170359887451338
c4: -2337770586248
c5: 929460
Y0: -7762093262195482668875676843
Y1: 38587683749133677
[/code]
I searched for about 40 hours, with 7 randomly picked 3K ranges [x, x+2999] between 95K and 950K. And only these two polynomials showed up.

The second one has higher 'e' value but worse alpha, and it showed to sieve about 9% slower, so we used the 8.217e-12 one.

jrk 2009-06-29 01:48

We are using msieve (and pol5*) to search for polynomial for a c157 [url=http://www.mersenneforum.org/showthread.php?t=12099]here[/url]. I don't know what version others are using but I expect 1.41 and earlier won't find anything. 1.42 might find something but I don't know that the values are right for numbers this large.

For pol5*, Tom suggested some values

[QUOTE=fivemack;179047]1.53e+024 is much too large a first-stage norm bound, you'd get unreasonably many outputs. 3e23 seems a bit better (350 seconds to get 126 first-stage outputs for 20M..21M). [/QUOTE]
But msieve 1.42 first stage norm for a c157 is 1.19e24. Is it too high? Or does msieve need higher norms?

[QUOTE=fivemack;179047]For the Murphy parameter, 1.78e-12 feels big, 8.5e-13 will give more plausible candidates, though you might want to update that after an evening's sieving.[/QUOTE]
msieve 1.42's final norm for c157, with Tom's corrections from the 2^1157-1 thread, is 1.51e-12. This is probably OK because axn has found pol5* polys up to 1.63e-12 already, but it could be lowered.

axn 2009-06-29 03:26

[QUOTE=jrk;179207]msieve 1.42's final norm for c157, with Tom's corrections from the 2^1157-1 thread, is 1.51e-12. This is probably OK because axn has found pol5* polys up to 1.63e-12 already, but it could be lowered.[/QUOTE]
I think 1.5 is perfect. I am using that currently and there are a lot of polys being found with it.

jrk 2009-06-29 05:24

[QUOTE=jrk;179207]But msieve 1.42 first stage norm for a c157 is 1.19e24. Is it too high? Or does msieve need higher norms?[/QUOTE]
I mis-interpolated the values I gave earlier, mistakenly using 157 as the digit length instead of 156.338. So the first stage norm msieve uses for this number is actually 1.01e24. Still higher than Tom's suggestion for pol5*.

[QUOTE=jrk;179207]msieve 1.42's final norm for c157, with Tom's corrections from the 2^1157-1 thread, is 1.51e-12. This is probably OK because axn has found pol5* polys up to 1.63e-12 already, but it could be lowered.[/QUOTE]
And that's wrong too. The final norm it is using is [color=red]1.73e-12[/color], which really seems high now. Although axn has now found pol5* polys above 1.84e-12 so maybe not.

Batalov 2009-08-05 01:13

working good for c169, c171
 
I have run a very superficial lazy -np run (only ~50 cpu-hrs each) on a c169 and a c171, and the results were very encouraging. I've put the short story in the [URL="http://www.mersenneforum.org/showthread.php?p=184149#post184149"]other thread[/URL].
With Bruce Dodson, I intend to probably run that c169 some time later by GNFS and with the msieve's polynomial.

bdodson 2009-08-28 22:43

Update
 
[QUOTE=fivemack;161385]If you don't mind, I'll devote a CPU-month or so to trying to find half-way decent values for say C145 through C190 in five-digit increments. ... [/QUOTE]

I've been reading/re-reading this thread, and wondering whether
we could have an update on the present status? As Serge mentions
in the previous post, we've just finished a search using msieve1.43
(Serge's binary) for a C169. We used -np and searched 1,500000,
first 1,300000 then 300001,500000. I was expecting to see the best
polyn from the smaller range; but Serge had it right, and the best
actually came from 450001,500000.

Most of the posts are from Dec '08; and in particular, does the
current/latest version include values from Tom for numbers above
C170? I'd be interested to hear about C174; but sounds like Serge
is thinking c180-c189. The current msieve is very transparent in the
c160's. Sounds like Tom went with ggnfs for 2^877-1 C178. What's
current best practice in c174-c189? -Bruce


All times are UTC. The time now is 04:56.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.