documentation for factoring is misleading/unspecific

[tthsqe12]

The documentation for the factoring functions reads something like "Factorises a non-constant polynomial ..." but it does not say what it does with the factorization, and it is unfortunate to find out the actual behaviour is the following only by trial and error

factor_init(f)
factor(f, a)
/* f is now a factorization of a */
factor(f, b)
/* f is now a factorization of a*b !!! */

Furthermore, the nonsense is compounded by the fact that the factors are inserted via a slow quadratic insertion sort.

[wbhart]

The insertion sort is hardly a bottleneck. Feel free to improve it, but there are certainly more pressing optimisation concerns.

The factor functions have to append factors because multiple algorithms are often used, and they need to append their factors to the factors that have already been found.

However, the main factor function, which should be called blah_factor could possibly be made to clear out the factor struct before putting anything in, so long as it does not get called more than once during a factorisation.

[tthsqe12]

Sure, let's fry the bigger fish first. I will leave it open though.

[wbhart]

Let's change the behaviour to always reset the factor struct before factor is run. This will need to be checked for each of the following modules, which can be done a little bit each flint release:

• ulong_extras
• fmpz_factor
• fmpz_poly_factor
• nmod_poly_factor
• fmpz_mod_poly_factor
• fq_poly_factor_templates

In addition, there are places in the mpoly_factor routines where the number of factors is set to zero before calling one of the above. Those lines can be removed once the behaviour has been changed.

Initially, let's just make sure the best-of-breed factor routine does the right thing in each module. Later we can make each individual factor algorithm have this behaviour, if it is considered worthwhile.

[wbhart]

fmpz_factor (ok):

The first thing this function does is call _fmpz_factor_set_length(factor, 0), after running fmpz_factor_si(factor, *n) if appropriate.

The latter does _fmpz_factor_set_length(factor, 0) as its first step.

fmpz_factor is not called anywhere in any of the other fmpz_factor routines.

fmpz_factor_smooth (ok):

The first thing this function does is call _fmpz_factor_set_length(factor, 0) after running fmpz_factor_si(factor, *n) if appropriate. Therefore it has the required behaviour.

fmpz_factor_no_trial (not ok):

It is clear that fmpz_factor_no_trial concatenates factor structs or appends factors. However, this function is not documented.

fmpz_factor_blah (not ok):

I presume all other fmpz_factor_blah functions append and concat factors.

[wbhart]

nmod_poly_factor (ok):

I have changed this function to set fac->num = 0 before starting. The function is not used anywhere. I removed the now unneeded zeroing of this field that was occurring in the nmod_mpoly_factor code.

[wbhart]

fmpz_poly_factor (ok):

This function sets the number of factors to zero before running. It is not used recursively anywhere.

I removed the no longer needed zeroing of factors in the mpoly code.

[wbhart]

fmpz_mod_poly_factor (ok):

This function calls either cantor_zassenhaus or kaltofen_shoup, both of which set the number of factors to zero before beginnning. The function is not called recursively anywhere.

I removed the lines in fmpz_mod_mpoly_factor that were setting the number of local factors to zero.

[wbhart]

n_factor (ok):

I changed this function to set the number of factors to zero before beginning. The function that were calling it were already initialising the factor struct before calling it.

[wbhart]

fq_poly_factor/fq_nmod_poly_factor/fq_zech_poly_factor (ok):

I have changed these to always set the number of factors to zero before beginning. They are not called recursively.

I changed the mpoly_factor code to no longer set the number of factors to zero before calling these.

[wbhart]

What remains on this ticket is to decide if we want all the factoring functions to zero the number of factors before starting. This is a fair bit of work because many factoring functions call others after some factors are already discovered, so this would zero the number of factors at the wrong time.

At the very least, perhaps fmpz_factor_no_trial should zero the number of factors. And if not that, at least it should be documented.