I'm taking the liberty of replying to his on-list, since other people here might have some input.
----- Original Message (Off-list) From: "Anurag Garg" <[EMAIL PROTECTED]> To: "Daran" <[EMAIL PROTECTED]> Sent: Tuesday, September 10, 2002 11:11 PM Subject: Re: Cherub faced individuals with shoes that need tying. > > Also, If you have exponents of your own > > needing both P-1 and TF, it should have the P-1 done before the last TF bit. > > Brian Beesley has done extensive testing to verify this. I don't know how much memory he was using, but the more you have available, the earlier you should do it. > Are you absolutely sure about this. Do let me know what the reason for > that might be. Absolutely sure. I pointed this out in the list some time ago, and had a fairly lengthy off-list discussion with him and George about it. The reason is simple. If you do Trial Factorisation first, and it finds a factor, then you save yourself the cost of the P-1. On the other hand, if you do the P-1 first, and it finds a factor, then you save yourself the cost of the TF. Since the probability of finding a factor with the P-1 is about twice that of the last bit of factoring, and the cost is much lower, the expected saving is much higher. The optimal point during TF at which to do the P-1 is when cost(TF)*prob(P-1) = cost(P-1)*prob(TF) This analysis is complicated by the fact that P-1 and TF search overlapping factor spaces, and thus affect each other's conditional probabilities. Currently the client assumes that no further TF will be done when it calculates optimal P-1 limits. In other words it assumes that a successful P-1 will save the cost of 1.03 or 2.03 LLs depending upon whether the assignment is a DC. It does not consider the possibility that a P-1 may only save a small amount of subsequent TF factoring, which would be the case if that factoring also would have found a factor. (Bear in mind that the conditional probability of this is *increased* because the P-1 was successful.) Consequently, if you do a P-1 before you finish TFing, and you set the factored bits to the amount you have already done, the client will choose limits which are too high, while the limits will be (slightly) low if you set the factored bit to the amount you are going to do, but they will be much closer to optimal. When the TF limits were originally decided, it was assumed that a sucessful TF would save 1.03 or 2.03 LLs. I can't remember whether George has ever said whether they have been lowered to take the P-1 step into account. Perhaps he or Brian could remind me. Additional complications arrise when you consider that P-1 and TF might be being done on different machines with different Integer:FP perfomance ratios. I have never been able to get my head around this. :-) Regards Daran G. _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
