FactorsInt in library

[hulpke]

This is prompted by a forum question which claimed that AbelianInvariantscan be held back by using FactorsInt instead of Factors.

[BTW: I have not found where AbelianInvariants calls FactorsInt, only calls to Factors, but that is not a disproof.]

There are about 2 dozen places in the library in which FactorsInt is called. This being a global function, it cannot be overridden by a package.

While there might be borderline cases that really need the Rho factorization, it seems to me that the main difference is a minor speedup in that FactorsInt does not need to construct the default ring and redispatch (as Factors(n) would), but that could be resolved by another method installation for condition IsInt.

Is this really time critical? Is there any reason to not replace the FactorsInt calls in the library (short of the factorization routine) with Factors? (I can do so)

[fingolfin]

The library method in lib/grp.gi:631 does so:

InstallMethod( AbelianInvariants,
    "generic method for groups",
    [ IsGroup ],
    function ( G )
...
    # the parent of this will be G
    cmm := DerivedSubgroup(G);
    for p  in Set( FactorsInt( Size( G ) ) )  do
...
            if r <> 1  then
                Add( ranks, Length(FactorsInt(r)) );
            fi;
...

Many other functions also do, e.g. this one for Exponent:

InstallMethod( Exponent,
    "generic method for finite groups",
    [ IsGroup and IsFinite ],
function(G)
  local exp, primes, p;
  exp := 1;
  primes := Set(FactorsInt(Size(G)));
  for p in primes do
    exp := exp * Exponent(SylowSubgroup(G, p));
  od;
  return exp;
end);

[fingolfin]

Also note that there used to be (and perhaps still are) places in our that called Factors or FactorsInt and shouldn't have called either -- e.g. to test whether a number is a primer power, it is not necessary to compute a full factorization, and IsPrimePowerInt resp. SmallestRootInt are much faster for this (and get even faster with PR #2061 resp. #2086).

[fingolfin]

This is of course somewhat off-topic, but I just confirmed that there is still library code computing a full prime factorization of an integer, when it just needs one prime divisor. We have a function for that, though (SmallestPrimeDivisor, which in turn could be improved further). A list of places which look like they should perhaps use it (or SmallestRootInt, or PrimePGroup) can easily be found via grep, say via git grep Factors | fgrep ")[1]".

[hulpke]

@fingolfin
Can I interpret your remarks as in favor of such a change? Unless someone objects I'll do it in a few days.

[fingolfin]

Yes, sorry, I am in favor

[frankluebeck]

Changing calls like FactorsInt(x) to Factors(Integers, x) sounds sensible, because this way the method selection can decide the best available method. (Currently, FactorsInt contains an explicit hook to call Factors if the FactInt package is loaded, but maybe other packages will provide better methods in the future.)
A call of Factors(Integers, x) instead of just Factors(x) can give a significant speedup if this is called frequently with small x.

[stevelinton]

@fingolfin Looking at your examples above, is there a case for an attribute PrimesGroup or PrimesDividingGroupOrder or some such. It's not likely that these factorisations take very long, but equally the primes would not be bulky to store. In a few weird cases the primes might be known by construction even when the group order wasn't.

[fingolfin]

@stevelinton ironically, the manual contains PrimesDividingSize as an example for declaring a custom attribute. As to whether it would be useful: not sure, I am neutral for now. It would generalize the existing PrimePGroup attribute, I guess.

[fingolfin]

fun: I just learned from issue #2099 that the permut package actually provides a PrimesDividingSize attribute...

[Stefan-Kohl]

As far as it concerns overheads when factoring small integers -- the following is what I observe (with FactInt loaded):

gap> for i in [1..1000] do for j in [1..1000] do FactorsInt(j); od; od; time;  
4656
gap> for i in [1..1000] do for j in [1..1000] do Factors(j); od; od; time;
1348
gap> for i in [1..1000] do for j in [1..1000] do Factors(Integers,j); od; od; $
1008

[fingolfin]

This issues was actually resolved by PR #2057, we almost always use Factors(Integers,j) now