Re: [Axiom-developer] exact quotient

[Martin Rubey]

Waldek Hebisch <address@hidden> writes:

> > On my machine, I get the following output
> > 
> >    [[10,1],[10,0],[10,1],[10,1],[10,1]]
> >    [[20,2],[20,2],[20,3],[20,2],[20,2]]
> >    [[30,6],[30,6],[30,5],[30,6],[30,6]]
> >    [[40,11],[40,12],[40,12],[40,12],[40,12]]
> >    [[50,19],[50,20],[50,19],[50,20],[50,20]]
> >    [[60,32],[60,32],[60,35],[60,35],[60,35]]
> >    [[70,52],[70,52],[70,52],[70,55],[70,51]]
> >    [[80,77],[80,77],[80,76],[80,76],[80,76]]
> >    [[90,102],[90,102],[90,108],[90,103],[90,103]]
> > 
> > This really looks like complexity between O(k^2.5) and O(k^3.0) for me,
> > where k is the number of monomials of the input.  I expected something like
> > O(k^2) though:
> > 
> > (a1*x1 + a2*x2+...+ak*xk)*(b1*x1 + b2*x2+...+bk*xk)
> > = (a1*x1 + a2*x2+...+ak*xk)*B
> > = a1*B*x1 + a2*B*x2...+ak*B*xk
> > 
> > which makes k^2 coefficient multiplications.  The cost of multiplying
> > variables should really be negligible, I believe.
> 
> Well, naive complexity is k^4: you have k^2 mutiplications of 4-k digit
> numbers.  Naive algorithm multiplication algorithm nees k^2 operations to
> multipy two k-digint numbers...

Why?  k is the number of monomials in A = (a1*x1 + a2*x2+...+ak*xk) and B =
(b1*x1 + b2*x2+...+bk*xk).  a_i is random(10000), b_i is random(10000), so I
think that a1*B should by k multiplications of two random(10000) numbers?  I'd
hope that the cost of multiplying the variable x_i = X^i * Y^(k-i-1) with yi is
negligible.

> There is another factor: your polynomials are homogeneous, so essentially
> behave like one-dimensional ones,

No, the model above is realistic.

Martin