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