[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 11:59:09 +0200 |
User-agent: |
Gnus/5.09 (Gnus v5.9.0) Emacs/21.4 |
Dear Waldek,
just to make sure:
> 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.
I just ran the test with
mon(n,k) == reduce(+, [random k * x^i*y^(n-i) for i in 0..n])
instead, and get the "expected" O(k^2) output:
(6) -> [test(kappa, 500, 5) for kappa in 10..100 by 10]
[[10,1],[10,0],[10,1],[10,0],[10,1]]
[[20,2],[20,2],[20,2],[20,2],[20,2]]
[[30,4],[30,4],[30,3],[30,3],[30,5]]
[[40,7],[40,7],[40,7],[40,7],[40,6]]
[[50,11],[50,10],[50,11],[50,10],[50,11]]
[[60,18],[60,15],[60,14],[60,15],[60,15]]
[[70,19],[70,20],[70,20],[70,20],[70,22]]
I also modified William Sit's test (using Expand), and obtained
Out[11]= {{10, 0.272878}, {10, 0.273776}, {10, 0.273362}, {20, 0.902124},
> {20, 0.899902}, {20, 0.899222}, {30, 1.920647}, {30, 1.922753},
> {30, 1.916153}, {40, 3.617779}, {40, 3.708420}, {40, 3.608447},
> {50, 6.507658}, {50, 6.525488}, {50, 6.509765}, {60, 10.755069},
> {60, 10.809554}, {60, 10.868204}, {70, 16.384399}, {70, 16.461227},
> {70, 16.337861}}
(on a much faster machine) which corresponds to Axiom's performance.
So, it remains to check, what situation is realistic for my problem, and
whether I can do anything about it...
Many thanks,
Martin