Add truncate methods to `fmpz_mod_poly`

[GiacomoPope]

This PR adds:

• equal_trunc
• add_trunc
• sub_trunc
• mul_low
• mul_high
• mul_mod
• pow_trunc

However, the output from mul_high() doesnt match my expectation... I'm not sure it's worth including, unless I'm being stupid.

The truncate pow is definitely nice, the mul mod seems to not offer much speed up.

In [3]: R = fmpz_mod_poly_ctx(2**127 - 1)

In [4]: f = R.random_element(degree=50)

In [5]: g = R.random_element(degree=50)

In [6]: h = R.random_element(degree=10)

In [7]: 

In [7]: (f * g) % h == f.mul_mod(g, h)
Out[7]: True

In [8]: %timeit (f * g) % h
67.2 μs ± 1.32 μs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

In [9]: %timeit f.mul_mod(g, h)
65 μs ± 1.01 μs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

In [10]: 

In [10]: x = R.gen()

In [11]: mod = x**20

In [12]: %timeit pow(f, 2**20, mod)
217 μs ± 2.27 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

In [13]: %timeit f.pow_trunc(2**20, 20)
82.2 μs ± 853 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

[oscarbenjamin]

the mul mod seems to not offer much speed up.

As far as I can tell all positive characteristic poly types have a mulmod function but in all cases it does literally just compute the multiplication followed by divrem apart from a minor optimisation to not bother with divrem if the degrees are small enough. In python-flint's case that would save a memory allocation over (f * g) % h.

I expect that it is a little faster for very small polynomials by saving the allocation. Probably in the context of python-flint though any saving here really comes from reducing the general Python overhead though:

In [5]: ctx = fmpz_mod_poly_ctx(127)

In [6]: f = ctx([1, 2])

In [7]: g = ctx([3, 4])

In [8]: h = ctx([1, 2, 3])

In [9]: %timeit (f*g)%h
3.11 µs ± 154 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

In [10]: %timeit f.mulmod(g, h)
1.23 µs ± 3.54 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

A more important question is how useful these functions actually are. There are many functions in flint that make a lot of sense for Flint's internal use but are perhaps not so useful to a user of python-flint especially if it they are trivially implemented using the features already provided.

For each of these functions we should consider what it means for all other types like if we have mulmod for fmpz_mod_poly are we going to have it for fmpq_poly as well?

Ideally we add methods to each type in such a way that there is a consistent set of methods across the different types. Currently fmpz_mod_poly has many more methods than the other poly types.

[GiacomoPope]

Currently fmpz_mod_poly has many more methods than the other poly types.

So my plan was to "finish" methods for this type and then use this as a start for fq_default_poly and also updating nmod_poly.

I'm happy to not include some of these methods, but you mentioned about the truncation ones in another PR so I threw them all in

[oscarbenjamin]

my plan was to "finish" methods for this type and then use this as a start for fq_default_poly and also updating nmod_poly

That seems reasonable.

For each operation now we need to consider if it makes sense for the other types though. Also we are probably already beginning to see diminishing returns from adding further methods to fmpz_mod_poly.

The _trunc and _mullow etc methods are actually already exposed in some sense in python-flint because they are used in the series types. That doesn't mean we can't add them to the poly types as well though.

[GiacomoPope]

If you're happy with the methods available for fmpz_mod_poly as presented here in this PR my next contribution will be fq_default_poly which will hopefully have all these features as well

[oscarbenjamin]

This looks good. Thanks

[oscarbenjamin]

my next contribution will be fq_default_poly

Excellent!