divexact/divides and sqrt/issquare

[wbhart]

This ticket is for discussion of the various issues related to divexact/divides and sqrt/issquare. @thofma @tthsqe12

We will not discuss the Euclidean division operator div and friends here. There is already a ticket for that issue, which is largely orthogonal.

Lets also not discuss whether 0 divides 0, which is also an orthogonal issue.

We will also not discuss square root mod composite moduli, which is beyond the scope of the current discussion.

Divexact

1. In Flint, for performance reasons, divexact does an exact division without checking or raising an exception if the division is not exact. Originally in AbstractAlgebra/Nemo divexact had the same meaning, however we eventually decided this is not good behaviour in the first instance for a CAS. This became most obvious when implementing interpolation where integer divexact must fail to indicate the interpolation has failed.

2. In AbstractAlgebra/Nemo we started implementing divides, which returns a tuple (flag, q) of a boolean to indicate whether the division was exact and a/the quotient in the case that it is and usually zero if not. We started implementing divides in Flint for the same purpose, though it isn't clear how far the rollout has gotten in C or Julia.

Square root

1. In Flint, sqrt computes the square root, usually returning 0/1 to indicate success/failure (an exception is integer sqrt and sqrt of integers mod small p, where for performance/interface reasons this is not done - Fredrik has done some work on an integer square root which tries to do a heuristic test to fail early before trying a sqrtrem). We also have the function is_square which is a simple predicate.

2. In AbstractAlgebra/Nemo we have sqrt which tries to return the square root, but raises an exception if the input is not square. We also have issquare, which is a simple predicate.

Issues

1. Integer sqrt and exact division and multivariate sqrt and exact division can be done faster/much faster if exactness is assumed but not tested.

2. Nemo uses Flint's scalar_div(exact) functions, which assume exactness, to implement ad hoc division of a polynomial/matrix by a coefficient. No test of exactness is performed.

3. There is no counterpart of divides for sqrt in AbstractAlgebra/Nemo though in some cases the underlying square root functions are implemented to support such an operation, in both Flint and AbstractAlgebra/Nemo.

4. divides does not start with the word "is", so one does not expect it to be a simple predicate returning true/false only. But it is hard to come up with a name for issquare that doesn't start with "is". Therefore one expects a simple predicate.

5. Some proposed names in AbstractAlgebra/Nemo include: sqrt_exact, issquare_with_sqrt, divexact -> div_exact, isdivisible (for the simple predicate).

6. There is a performance issue in returning a tuple (flag, q), from divides and the sqrt analogue, if one only needs the simple predicate, as an object q must always be created to hold the quotient/sqrt. This is particularly bad in cases where it is expected that exactness is unlikely and a fast heuristic test will reject negatives quickly.

7. Many of our divides functions do not do a fast heuristic test, but should.

Discussion

Mostly this ticket is about agreeing on an interface and rolling out the changes. I don't know of any cases where we don't know an algorithm, or how to implement whatever we decide on.

Note that in the worst case we end up with four functions in each case:

div_exact, divides, isdivisible, div_exact_unchecked

sqrt, ??, issquare, sqrt_unchecked

Of course div_exact could take an optional flag which allows checking to be turned off:

div_exact, divides, isdivisible

sqrt, ??, issquare