On Sat, Nov 14, 2009 at 4:31 PM, gerrob <robert.gerb...@gmail.com> wrote: > > I've uploaded a new code on google group. It is using remainder tree > to speedup the sieving, and now it is sieving up to about log2(n)^2. > It means a speedup by a factor of two for large "random" input (here > random means that nextprime(n) isn't very close to n). For totally > random inputs it is faster than the currently code from approximately > 1300 bits numbers.
Quick naive question -- is this command finding the next pseudoprime, or is it really the next prime (provably correctly)? A time of 131 seconds for finding the next prime (not pseudoprime) after 10^2000 would I think be very, very impressive to me. William > > Just two inputs, on my PC: (the input numbers are special, but neither > of codes recognize/use this) > > N=10^2000 > mpir's time=229 sec. > my method's time=131 sec. > diff=0,nextprime(N)-N=4561 > > N=10^4000 > mpir's time=4551 sec. > my method's time=2281 sec. > diff=0,nextprime(N)-N=16483 > > > -- William Stein Associate Professor of Mathematics University of Washington http://wstein.org --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "mpir-devel" group. To post to this group, send email to mpir-devel@googlegroups.com To unsubscribe from this group, send email to mpir-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/mpir-devel?hl=en -~----------~----~----~----~------~----~------~--~---