Re: [Axiom-developer] exact quotient

[Martin Rubey]

Martin Rubey <address@hidden> writes:

> 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.

Oh, I think I made a stupid mistake.  I defined 

mon(n,k) == (random k * x + random k * y)^n

which makes the coefficients not of size log k, but rather of size 

log(binomial(n,j)* k^j).  Stupid me.

Martin