Re: [Axiom-developer] exact quotient

[William Sit]

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]