CoCoA » CoCoALib

The current implementation of FactorMultiplicity makes it hard to use inside SmoothFactor (because it returns only the multiplicity, and not N/p^k).

I now think that the interface to FactorMultiplicity should change, or there should be a new function.
The advantage of adding a new function is that it is backwards-compatible.

What should the new function do, and what should it be called?
I see two possible sensible signatures:

• (A) args (N,p) returns a factorization with fields myFactors=[p], myMultiplicities=[k] and myRemainingFactor=N/p^k
• (B) args (ref N,p) and changes value of N

(B) feels "simpler", but does change the value of a parameter (so there could be a question about exception safety)
(A) is possibly more consistent with other "factorization" functions, but its return value is new object (implying possible copying of some values).

Another question with (A) is what happens if the multiplicity is zero?
Currently the impl for factorization requires multiplicities to be positive (even though the error message seems to prohibit only negative multiplicities).

I have made a reasonable impl more or less following (B).
There is a new non-exported fn which computes multiplicity and modifies one of its args. Should this be made public?

Checked in. No new tests were added; maybe I should (e.g. for negative args?)

Now I think it is better not to make DivideOutMaxPower public; we can wait until there is actual demand for it.

I have tried the following test:

n := factorial(10^6);
b := 3^41;
FactorMultiplicity(b,n); --> takes about 23s
FactorMultiplicity(3,n); --> takes about 13s

So I have added a CheckForInterrupt in the main loop of DivideOutMaxPower for BigInt,BigInt.
Perhaps the loop should be changed to mimic that for long,BigInt? It is unexpected that the second call to FactorMultiplicity is faster than the first!

PS if I increase n to factorial(2000000) the times become 99s and 57s which is about the same ratio as before --- huh???