|
From: Bill H. <goo...@go...> - 2009-03-21 21:13:21
|
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. > |