Waldek Hebisch <[EMAIL PROTECTED]> 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 _______________________________________________ Axiom-developer mailing list Axiom-developer@nongnu.org http://lists.nongnu.org/mailman/listinfo/axiom-developer
