Re: [flint-devel] Poly division over Z

[Bill H. <goo...@go...>]

I coded up a simple fmpz_poly_divexact to match Magma's Exact
Quotient. It uses the modular algorithm for polys with small
coefficients.

Here is the new graph:

http://sage.math.washington.edu/home/wbhart/div2.png

I've no idea what the remaining red patch is. It is right into the
modular region, which relies on division in Z/pZ[x], which we know
runs as fast or faster than Magma. So who knows. Perhaps their
crossover from the usual algorithm to the modular algorithm (if that
is what they use) is higher and their usual algorithm faster than
FLINT's at that point.

I guess I'll figure it out eventually.

Bill.

2009/3/21 Bill Hart <goo...@go...>:
> Here is a profile for polynomial division over Z:
>
> http://sage.math.washington.edu/home/wbhart/div.png
>
> I'm guessing Magma uses either a modular algorithm or some kind of
> Kronecker-Segmentation type algorithm in the red region. I'll
> eventually get around to implementing this.
>
> Note I used Magma's ExactQuotient function. Here Magma definitely has
> an advantage.
>
> Bill.
>