[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Axiom-developer] exact quotient
From: |
William Sit |
Subject: |
Re: [Axiom-developer] exact quotient |
Date: |
Thu, 21 Jun 2007 04:05:38 -0400 |
Martin:
Regarding your test for multivariate polynomial
multiplication:
On my machine (Windows), I got:
[[10,1], [10,0], [10,1], [10,0], [10,1],
[20,2], [20,2], [20,1], [20,1],[20,2],
[30,4], [30,4], [30,3], [30,4], [30,4],
[40,8], [40,7], [40,7],[40,8], [40,7],
[50,12], [50,12], [50,13], [50,13], [50,12],
[60,22],[60,21], [60,21], [60,22], [60,22],
[70,33], [70,33], [70,33], [70,34],[70,34],
[80,47], [80,47], [80,48], [80,48], [80,48],
[90,67], [90,67], [90,67], [90,67], [90,67],
[100,90], [100,90], [100,92], [100,94],[100,93]]
which is painfully slow. Using DMP instead of POLY INT is
slightly faster:
[[10,1], [10,0], [10,0], [10,0], [10,0],
[20,1], [20,1], [20,1], [20,1],[20,1],
[30,2], [30,3], [30,2], [30,3], [30,3],
[40,5], [40,6], [40,5], [40,5], [40,5],
[50,9], [50,9], [50,9], [50,9], [50,10],
[60,16], [60,16], [60,17], [60,16], [60,16],
[70,25], [70,25], [70,25], [70,26], [70,25],
[80,37], [80,37], [80,38], [80,38], [80,38],
[90,55], [90,55], [90,55], [90,55], [90,55],
[100,76], [100,75], [100,75], [100,77], [100,78]]
Compare this with Mathematica 5.2 (output reformatted; 0
timing means less than 10^(-7)):
{{10, 0. }, {10, 0. }, {10, 0. }, {10, 0. }, {10,
0.0156250},
{20, 0. }, {20, 0. }, {20, 0. }, {20, 0.0156250}, {20, 0. },
{30, 0. }, {30, 0.0156250}, {30, 0. }, {30, 0. }, {30,
0.0156250},
{40, 0.0156250}, {40, 0. }, {40, 0. }, {40, 0.0156250}, {40,
0.0312500},
{50, 0.0156250}, {50, 0. }, {50, 0. }, {50, 0. }, {50,
0.0312500},
{60, 0. }, {60, 0.0156250}, {60, 0. 10 }, {60, 0. }, {60,
0.0468750},
{70, 0. }, {70, 0. }, {70, 0.0156250}, {70, 0. }, {70,
0.0468750},
{80, 0. }, {80, 0.0156250}, {80, 0. }, {80, 0. }, {80,
0.0625000},
{90, 0. }, {90, 0. }, {90, 0.0156250}, {90, 0. }, {90,
0.0625000},
{100, 0.0156250}, {100, 0. }, {100, 0. }, {100, 0. },
{100, 0.0781250}}
I even changed the polynomials to use n+1 random
coefficients and random exponents. The result is similar to
above. See the code below.
{{10, 0. }, {10, 0.0156250}, {10, 0. }, {10, 0.0156250},
{10, 0.},
{20, 0.0156250}, {20, 0.0156250}, {20, 0.0156250}, {20,
0.0156250}, {20,0.0156250},
{30, 0.0156250}, {30, 0.0156250}, {30, 0.0312500},
{30,0.0156250}, {30, 0.0156250},
{40, 0.0312500}, {40, 0.0312500}, {40,0.0156250}, {40,
0.0312500}, {40, 0.0312500},
{50, 0.0468750}, {50,0.0468750}, {50, 0.0312500}, {50,
0.0468750}, {50, 0.0312500},
{60,0.0312500}, {60, 0.0468750}, {60, 0.0312500}, {60,
0.0312500}, {60,0.0312500},
{70, 0.0625000}, {70, 0.0468750}, {70, 0.0312500},
{70,0.0468750}, {70, 0.0312500},
{80, 0.0468750}, {80, 0.0468750}, {80,0.0468750}, {80,
0.0625000}, {80, 0.0312500},
{90, 0.0625000}, {90, 0.0468750}, {90, 0.0468750}, {90,
0.0625000}, {90, 0.0468750},
{100, 0.0625000}, {100, 0.0625000}, {100, 0.0781250}, {100,
0.0625000}, {100, 0.0625000}}
This is three orders of magnitude faster than Axiom.
William
---
In[1]:=
mon[n_,k_]:= Expand[(Random[Integer,k] x + Random[Integer,
k]y)^n]
In[2]:=
list[kappa_,m_]:=Table[mon[kappa, 10000], {i,1,m}]
In[3]:=
test[kappa_,m_,n_]:=Module[{list1, list2, t1, t2, res},
list1=list[kappa, m];
list2=list[kappa,m];
res = {};
Do[t1 = AbsoluteTime[];
Do[list1[[i]] list2[[i]], {i,m}];
t2 = AbsoluteTime[];
res = Join[{{kappa, t2-t1}}, res],
{n}]; res]
In[4]:=
Flatten[Table[test[10 kappa, 500,5], {kappa, 1,10}],1]
In[5]:=
mon2[n_,k_]:= Module[{},
coefs = Table[Random[Integer, k],{i,0,n}];
exps = Table[{Random[Integer,n], Random[Integer, n]},
{i,0,n}];
Apply[Plus, MapThread[#1 x^First[#2] y^#2[[2]]
&,{coefs,exps}]]]
In[6]:=
listTwo[kappa_,m_]:=Table[mon2[kappa,10000],{i,1,m}]
In[7]:=
test2[kappa_,m_,n_]:=Module[{list1, list2, t1, t2, res},
list1=listTwo[kappa, m];
list2=listTwo[kappa,m];
res = {};
Do[t1 = AbsoluteTime[];
Do[list1[[i]] list2[[i]], {i,m}];
t2 = AbsoluteTime[];
res = Join[{{kappa, t2-t1}}, res],
{n}]; res]
In[8]:=
Flatten[Table[test2[10 kappa, 500,5], {kappa, 1,10}],1]
- Re: [Axiom-developer] exact quotient, (continued)
- Re: [Axiom-developer] exact quotient, Ralf Hemmecke, 2007/06/19
- Re: [Axiom-developer] exact quotient, Waldek Hebisch, 2007/06/19
- Re: [Axiom-developer] exact quotient, Martin Rubey, 2007/06/20
- Re: [Axiom-developer] exact quotient, Waldek Hebisch, 2007/06/20
- Re: [Axiom-developer] exact quotient, Martin Rubey, 2007/06/21
- Re: [Axiom-developer] exact quotient, Martin Rubey, 2007/06/21
- Re: [Axiom-developer] exact quotient, Martin Rubey, 2007/06/21
- Re: [Axiom-developer] exact quotient, William Sit, 2007/06/21
- Re: [Axiom-developer] exact quotient,
William Sit <=
- Re: [Axiom-developer] exact quotient, Martin Rubey, 2007/06/21