On 07/22/2013 05:14 PM, Torbjorn Granlund wrote: > Pádraig Brady <[email protected]> writes: > > 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. > > I dont think this is related to the use of GMP for the larger number.
Oh right of course. If I force GMP with the smaller number, we get a longer time: $ time factor 8683317618811886495518194401279999999 8683317618811886495518194401279999999: 8683317618811886495518194401279999999 real 5m51.967s > 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? > > The time difference is due to the time to (recursively) factor n-1 for > each assumed prime number n and assumed prime factor n. For the slower > number above, n-1 has two huge factors (of 61 and 62 bits each). Right 8683317618811886495518194401279999998 is the issue here specifically. Using that in isolation with the older factor takes an even longer time: $ time factor-8.10 8683317618811886495518194401279999998 8683317618811886495518194401279999998: 2 1570143494597312303 2765135049341098033 real 6m36.754s thanks for the clarifications, Pádraig.
