[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 10:15:51 +0200 |
User-agent: |
Gnus/5.09 (Gnus v5.9.0) Emacs/21.4 |
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