[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Axiom-developer] exact quotient
From: |
Martin Rubey |
Subject: |
Re: [Axiom-developer] exact quotient |
Date: |
21 Jun 2007 06:50:26 +0200 |
User-agent: |
Gnus/5.09 (Gnus v5.9.0) Emacs/21.4 |
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