I need some stats

[Moo_the_cow]

I need some stats to confirm my claim that sieving is more efficient than P-1 factoring, and that we should therefore abandon factoring altogether and continue sieving.
Here's what i need:

1.) Time it takes for completing a P-1 factoring test at n=4.1 M
2.) Number of p/sec you can sieve (main sieve)
3.) Time it takes to complete a PRP test at n=4.1 M

Thanks in advance. The reason that I couldn't do this myself is because I lack the patience to do 1 P-1 factoring test.

[Mystwalker]

I don't know if it's feasible to compare sieving to P-1 factoring. Sieving eliminates tests they may be assigned in the future (some of them years away), whereas factoring *can* eliminate current tests. So a prime wouldn't affect the factoring as hard as it does with sieving.

IMHO, we should directly compare the time t it takes to do a factoring divided by the likelihood p a factor is found against the time it takes to do a PRP test (and at least part of the double sieve effort).


My systems (P3-m 1GHz, Duron 900) need ~6 hours for P-1 factoring with an estimated chance of 2.13% of finding a factor (B1=80,000; B2=440,000).
Without double check, a PRP test may take almost 12 days (24/7) to get there. When we fully consider the double test, it'll be ~6 days.

Unfortunately I don't know how long it takes for them to compute a current PRP test, but I guess someone else does.


One further question:
Does the computation time for P-1 factoring increases with bigger n? If yes (which I assume), hwo does it compare to the effort increase of PRP testing?

[Moo_the_cow]

Here's why it's much better to go on with sieving rather than P-1 factoring:

- Since there is about a 2.13% chance of finding a factor, there has to be around 47 tests which need to be completed in order to find one. Also, each test takes about 6 hours on a 1GHZ PC.
Therefore, you would need 282 hours (11.75 days) on average to find just ONE factor with factoring.

- Let's say that we're really lucky, and SB finds 11 primes before reaching n=20M. We would still need to test 1 k at some time with n>20M. Therefore, only 1/12 of our sieve factors are useful.

- At 45T, you can expect that there will be one factor for every 2G, and one useful factor every 24G. My P-3 800MHZ takes about 3 days to sieve 24 G, and would therefore take 3 days to find one "useful" factor.

- So there you have it. 11.75 days per useful factor by factoring vs. 3 days per useful factor by sieving. The result should be obvious.

quote:
___________________________________________
One further question:
Does the computation time for P-1 factoring increases with bigger n? If yes (which I assume), hwo does it compare to the effort increase of PRP testing?
____________________________________________
Yes. Compare a factor test at 3M and a factor test at 5M and you will see the difference.

[MikeH]

- Since there is about a 2.13% chance of finding a factor, there has to be around 47 tests which need to be completed in order to find one. Also, each test takes about 6 hours on a 1GHZ PC.

If those numbers are correct, counldn't a PRP test could be completed on the same PC in less time. So if this PC isn't connected to the net, or for some other reason can't PRP, then that's fine, but if it can PRP test then maybe that would be more productive?

...and yes I know a factor is worth more than a PRP residue, but something feels wrong when it's slower.

P-1 factoring will be good when the bounds are optimised etc., so everyone keep experimenting. By the time we really need P-1 factoring we should have it all figured out.

[Mystwalker]

Yes. Compare a factor test at 3M and a factor test at 5M and you will see the difference.

The question is: Does it take roughly 4 times as long when we double the n value? AFAIR this is the effort increase with PRP.


Concerning the usefulness of P-1 factoring, we have to consider the P4 systems as well. As we all know they basically 'suck' at sieving, but are good performers when it comes to PRPing.
So it is possible that they are far more effective in P-1 factoring than in sieving.
Plus, upcoming systems are likely to enhance PRP computation power a lot, whereas I think it won't increase sieving power the same level. Just a guess, but we'll find out once we know about Athlon64 (or Opteron) systems doing all SoB (sub-)projects.
As this project is going to be active for a long time - we're talking about a lot of years ideally - we should keep all ways open to adapt to the changing conditions of computer technology.

[jjjjL]

the bound guesser may be suboptimal. for now I would advocate setting the double-check flag to 1 instead of 0 so that it will take less time on each P-1 test. It increases the speed of the tests by over 100% and only decreases the chances of finding a factor by around 30%.

the bound guessing code is posted in the factorer thread so anyone is welcome to come up with suggestions or write new code for me.

also, no one is advocating an end to sieving. but the exponential fall-off of potential factors and the questionable value of factors that are obtained by sieving are difficult problems ahead. P-1 factoring faces neither of those.

-Louie