On 07/22/2013 04:01 PM, Sami Kerola wrote: > Hello, > > I were curious how quickly factor will process prime numbers, and > found something rather strange. For example these five can be computed > quite quickly. > > time factor 10333147966386144929666651337523199999999 > time factor 371993326789901217467999448150835199999999 > time factor 13763753091226345046315979581580902399999999 > time factor 523022617466601111760007224100074291199999999 > time factor 20397882081197443358640281739902897356799999999 > > But much smaller numbers will take ages to give results (to be honest > I gave up). > > time factor 8683317618811886495518194401279999999 > time factor 295232799039604140847618609643519999999 > > Any idea what is going on?
Quantifying... $ time factor-8.10 10333147966386144929666651337523199999999 10333147966386144929666651337523199999999: 37 71 3933440413546305645095794190149676437 real 0m0.014s $ time factor-8.10 8683317618811886495518194401279999999 8683317618811886495518194401279999999: 8683317618811886495518194401279999999 real 0m0.006s $ time factor-8.21 10333147966386144929666651337523199999999 10333147966386144929666651337523199999999: 37 71 3933440413546305645095794190149676437 real 0m0.356s $ time factor-8.21 8683317618811886495518194401279999999 8683317618811886495518194401279999999: 8683317618811886495518194401279999999 real 1m44.693s So the new factor is slower in both cases. The difference between the two numbers in factor-8.21 is due to different code paths (GMP and not). Note GMP is unexpectedly faster in this case. Now I previously asked about slowdowns in the new factor code. http://lists.gnu.org/archive/html/coreutils/2012-10/msg00030.html There it was mentioned that factor now enables prime proving by default. This sometimes takes a lot of time as it needs to factor p-1 for each factor p found. Each factor of p-1 is also proven prime, recursively. If I compile with "prime proving" disabled we get: $ time factor 10333147966386144929666651337523199999999 10333147966386144929666651337523199999999: 37 71 3933440413546305645095794190149676437 real 0m0.004s $ time factor 8683317618811886495518194401279999999 8683317618811886495518194401279999999: 8683317618811886495518194401279999999 real 0m0.004s So nice and fast. So I have questions too at this stage. 1. I get that prime proving takes longer, though is the above 1m44s reasonable/expected? 2. "Proving" is done in the GMP case too. Why is that faster? Is it a weaker check? thanks, Pádraig.
