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.
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). -- Torbjörn
