Re: [Axiom-developer] exact quotient

[William Sit]

Hi Martin:

Thanks, Martin, for catching the missing Expand (I caught
the one in mon, but not the one in the loop!). Yes, it takes
much longer now and the results are, using your revised
version of mon:
mon3[n_,k_]:= Module[{},
  coefs = Table[Random[Integer, k],{i,0,n}];
  exps = Table[i,{i,0,n}];
  Apply[Plus, MapThread[#1 x^#2 y^(n-#2) &,{coefs,exps}]]]

{{10, 0.3125000}, {10, 0.2812500}, {10, 0.2812500}, {10,
0.2656250}, {10, 0.2812500},
{20, 0.7968750}, {20, 0.7812500}, {20, 0.8281250}, {20,
0.8750000}, {20, 0.7968750},
{30, 1.6406250}, {30, 1.6093750}, {30, 1.6718750}, {30,
1.6250000}, {30, 1.6250000},
{40, 2.9687500}, {40, 2.9375000}, {40, 2.9218750}, {40,
2.8750000}, {40, 2.9531250},
{50, 4.4843750}, {50, 4.3593750}, {50, 4.2968750}, {50,
4.5000000}, {50, 4.6250000},
{60, 6.0625000}, {60, 6.0625000}, {60, 6.1093750}, {60,
6.1093750}, {60, 5.9687500},
{70, 12.1875000}, {70, 8.9843750}, {70, 8.9062500}, {70,
9.3125000}, {70, 9.2031250},
{80, 24.0000000}, {80, 24.4375000}, {80, 24.5937500}, {80,
24.5781250}, {80, 24.6718750},
{90, 30.6875000}, {90, 29.8125000}, {90, 30.3593750}, {90,
30.2968750}, {90, 30.6562500},
{100, 36.2500000}, {100, 36.1250000}, {100, 36.1875000},
{100, 36.1250000}, {100, 35.9531250}}

On the same machine on Axiom, using:
mon(n,k) == reduce(+, [(random k *
x^i*y^(n-i))::DMP([x,y],Integer) for i in 0..n])
reduce(append, [test(kappa, 500, 5) for kappa in 10..100 by
10])

   Compiling function mon with type
(PositiveInteger,PositiveInteger)
       -> DistributedMultivariatePolynomial([x,y],Integer)
   Compiling function l with type
(PositiveInteger,PositiveInteger) ->
      List DistributedMultivariatePolynomial([x,y],Integer)
   Compiling function test with type
(PositiveInteger,PositiveInteger,
      PositiveInteger) -> List List Integer
 [[10,1], [10,0], [10,0], [10,0], [10,1], [20,0], [20,1],
[20,1], [20,1],
  [20,1], [30,2], [30,2], [30,2], [30,2], [30,2], [40,3],
[40,3], [40,3],
  [40,3], [40,3], [50,5], [50,5], [50,5], [50,6], [50,5],
[60,6], [60,7],
  [60,7], [60,7], [60,7], [70,9], [70,9], [70,9], [70,9],
[70,9], [80,12],
  [80,12], [80,12], [80,12], [80,12], [90,16], [90,15],
[90,16], [90,17],
  [90,17], [100,18], [100,19], [100,18], [100,18], [100,19]]

This is much faster than both Mathematica and using default
(which timing is compatible with Mathematica):
(12) -> mon(n,k) == reduce(+, [random k * x^i*y^(n-i) for i
in 0..n])
   Compiled code for mon has been cleared.
   Compiled code for l has been cleared.
   Compiled code for test has been cleared.
   1 old definition(s) deleted for function or rule mon

Type: Void
(13) -> reduce(append, [test(kappa, 500, 5) for kappa in
10..100 by 10])
   Compiling function mon with type
(PositiveInteger,PositiveInteger)
       -> Fraction Polynomial Integer
   Compiling function l with type
(PositiveInteger,PositiveInteger) ->
      List Fraction Polynomial Integer
   Compiling function test with type
(PositiveInteger,PositiveInteger,
      PositiveInteger) -> List List Integer
[[10,1], [10,1], [10,0], [10,0], [10,1], [20,2], [20,2],
[20,2], [20,2],
   [20,3], [30,5], [30,5], [30,5], [30,5], [30,5], [40,9],
[40,9], [40,9],
   [40,9], [40,9], [50,15], [50,14], [50,15], [50,14],
[50,14], [60,20],
   [60,20], [60,21], [60,20], [60,21], [70,30], [70,28],
[70,29], [70,28],
   [70,29], [80,19], [80,23], [80,21], [80,20], [80,21],
[90,28], [90,25],
   [90,29], [90,27], [90,25], [100,33], [100,34], [100,35],
[100,36],
  [100,31]]

I also noted that the function mon was compiled differently,
where using default  the function mon compiles to FRAC POLY
INT, not POLY INT, even though the times for kappa >= 80 are
about the same in both cases:

(14) -> mon(n,k) == reduce(+, [(random k *
x^i*y^(n-i))::POLY INT for i in 0..n]
)
   Compiled code for mon has been cleared.
   Compiled code for l has been cleared.
   Compiled code for test has been cleared.
   1 old definition(s) deleted for function or rule mon

Type: Void
(15) -> reduce(append, [test(kappa, 500, 5) for kappa in
10..100 by 10])
   Compiling function mon with type
(PositiveInteger,PositiveInteger)
       -> Polynomial Integer
   Compiling function l with type
(PositiveInteger,PositiveInteger) ->
      List Polynomial Integer
   Compiling function test with type
(PositiveInteger,PositiveInteger,
      PositiveInteger) -> List List Integer
    (15)
   [[10,0], [10,0], [10,0], [10,0], [10,1], [20,1], [20,1],
[20,1], [20,1],
    [20,1], [30,2], [30,3], [30,3], [30,3], [30,3], [40,5],
[40,6], [40,4],
    [40,4], [40,4], [50,8], [50,8], [50,8], [50,8], [50,7],
[60,11], [60,11],
    [60,12], [60,11], [60,11], [70,15], [70,15], [70,15],
[70,16], [70,15],
    [80,21], [80,20], [80,20], [80,20], [80,20], [90,26],
[90,25], [90,26],
    [90,26], [90,26], [100,32], [100,33], [100,32],
[100,32], [100,32]]

So the data-structure comes into play. Not sure if
converting your computation to DMP and back would save time.

William








--
William Sit
Department of Mathematics..Email: address@hidden
City College of New York................Tel: 212-650-5179
New York, NY 10031, USA.................Fax: 212-862-0004
Home page: .......http://scisun.sci.ccny.cuny.edu/~wyscc/