Probabilistic optimization of P-1 efforsts?

[R.D. Silverman]

Note further that if what you want to ask for is:

"reduce the time without reducing the probability of success"

this is IMPOSSIBLE.

[bgbeuning]

Originally Posted by chris2be8

He probably meant "scrape primenet". If so that's a question for George to answer (it probably depends how much load it'll put on the server).

Chris

I scraped the Mersenne factors from the web site (with George's permission) in August 2015.
The file is 53 MB (compressed 22 MB) for p to 42,549,973 .
Let me know how I can send it to you.

[ATH]

I "scraped" primenet for all factors back on Sep 3rd 2014: http://www.mersenneforum.org/showthread.php?t=19662 (the link in that thread is not valid now)

I got 35,504,331 factors from 28,300,589 different exponent between p=11 and p=999,999,893.

gimpsfactors.zip (291 Mb)
This is actually a 7-zip file, but the site does not permit .7z files, so rename it back to .7z and use 7-zip to exact the 902 Mb .txt file.
You should use something like Textpad or Notepad++ to open that large file.

[ewmayer]

Originally Posted by R.D. Silverman

Note further that if what you want to ask for is:

"reduce the time without reducing the probability of success"

this is IMPOSSIBLE.

Pardon me if I missed some key portion of your as-usual-overlong multipostal flaming-of-newbie-into-submission, but isn't that pretty much the definition of probabilistic-algorithm optimization? I can think of many ways to fiddle the parameters of p-1 (or ecm) in a way which increases the runtime without improving the overall odds of success - I expect the above was referring to the converse. Given the usual way (described by fivemack) in post #4 of processing the small prime powers in p-1, further improvement here is unlikely to be had, but in a general sense the OP's remark was not off base.

To the OP and anyone late to this thread: fivemack's brief note in post #4 tells you pretty much all you need to know about optimizing the aspect of p-1 the OP is asking about. Further posts which contribute no meaningful S to S/N will be disappeared with extreme prejudice.

[R.D. Silverman]

Originally Posted by ewmayer

Pardon me if I missed some key portion of your as-usual-overlong multipostal flaming-of-newbie-into-submission,

You must have been reading a different thread from the rest of us.
Nothing, repeat nothing that I said could even remotely be considered a flame.
The entire discussion was either about the technical issues, or requests for
clarification and questions about the meaning of what the OP said.

but isn't that pretty much the definition of probabilistic-algorithm optimization? I can think of many ways to fiddle the parameters of p-1 (or ecm) in a way which increases the runtime without improving the overall odds of success - I expect the above was referring to the converse.

As was I. But this is NOT the "definition of probabilistic-algorithm optimization". One needs to specify an
objective other than just "reduce the run time". One must specify how much cost (i.e. reduction in probability)
one is willing to tolerate in return for a given reduction in run time. Nowhere in this thread do I see such
a specification. One can also turn it into a constrained optimization: reduce run time by as much as possible
with a lower bound given on the probability. The title of the thread did ask about an OPTIMIZATION.

Are you willing to accept a 90% drop in probability for (say) a 2-fold improvement in run time?
No? What about a 75% drop? etc. The relationship is very non-linear.

One can also express this problem in terms of an economic UTILITY function, but I did not want to
go down that path. It is just a different formulation of the same problem.

Given the usual way (described by fivemack) in post #4 of processing the small prime powers in p-1, further improvement here is unlikely to be had, but in a general sense the OP's remark was not off base.

Improvement? Improvement in what? You have again failed to specify an objective function.
Do you mean improvement in run-time? What fivemack gave CAN be improved in terms of run time.

To the OP and anyone late to this thread: fivemack's brief note in post #4 tells you pretty much all you need to know about optimizing the aspect of p-1 the OP is asking about. .

This claim is not correct.

[chalsall]

Originally Posted by R.D. Silverman

This claim is not correct.

Why?

[R.D. Silverman]

Originally Posted by chalsall

Why?

It shows one method/choice of parameters for implementing the method,
but performs no optimization.

If you believe otherwise, please state what optimization is being performed.
What is the objective function being minimized or maximized. What are the
constraints?

[chalsall]

Originally Posted by R.D. Silverman

It shows one method/choice of parameters for implementing the method,
but performs no optimization.

If you believe otherwise, please state what optimization is being performed.
What is the objective function being minimized or maximized. What are the
constraints?

I would like to ask you another question...

What would you advise works better?

[R.D. Silverman]

Originally Posted by chalsall

I would like to ask you another question...

What would you advise works better?

What does it mean (in your view) for one method to work better than another?
One can choose parameters to give a higher probability of success. But it will run slower....
Is this better? The probability will not increase linearly with the run time.

This is the heart of the whole discussion. Specify an objective function (or other metric)
that let's us decide what "works better" means.

[chalsall]

Originally Posted by R.D. Silverman

What does it mean (in your view) for one method to work better than another?

Thank you for this.

In my view, results are better than insults. But sometimes, insults are useful as motivation.

Believe it or not, I appreciate your methodology.

Many others are scared away....

[ewmayer]

Originally Posted by R.D. Silverman

What does it mean (in your view) for one method to work better than another?
One can choose parameters to give a higher probability of success. But it will run slower....
Is this better? The probability will not increase linearly with the run time.

This is the heart of the whole discussion. Specify an objective function (or other metric)
that let's us decide what "works better" means.

Most common objective function is 'for a given compute effort, maximize our odds of success.' Effort can be measured in various ways, either raw CPU-cycles, wall-clock time or - for the enviro-conscious crowd - watt-hours, but once those considerations have been turned into compute hardware, it all boils down to the same thing, getting maximum utitlity ('successes') out of same. For GIMPS p-1 work, our success metric is 'given a large set of moduli M(p) and a given compute effort, maximize the % of M(p) for which p-1 finds a factor.' That of course needs to be balanced against the other work types (TF, LL, also ECM for smaller moduli), but within the p-1 effort we want to simply want to maximize our odds of finding a factor for a given compute effort.

For p-1 stage 1 the compute effort is linear in the bitlength of the stage 1 small-primes product, thus we want our product of primes <= B1 to maximize the odds of capturing the primes <= B1 in one or more of the factors of the modulus in question. As you point out in post #2 (for N of no special form), "The probability that an integer N is divisible by p^k, is very nearly 1/p^k", thus the kind of small-prime-powers scheme Tom Womack laid out in #4 is optimal, or as close as we are likely to get given the granularity of the powers involved. If you have a nontrivially-better scheme for constructing a stage 1 primes product, by all means shout it from the rooftops! Do you?

For moduli with factors of special form like our beloved M(p) we may need to make slight modifications to the above schema - M(p) have factors of form 2.k.p+1, so p-1 guaranteed to be divisible by the prime exponent, thus we make sure to 'salt' the stage 1 primes product with p if our overall stage 1 bound B1 is less than p.

But you know all this already, thus I assert you are simply being a trollish, argumentative twit because such is your nature, as demonstrated in-depth in literally hundreds of threads on this forum. You appear to be the only one who thinks your behavior in this (and similar) threads is perfectly reasonable. Luckily you are not the arbiter of what constitues acceptable standards of discourse here.