MathGroup Archive 2008

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: Compile

  • To: mathgroup at smc.vnet.net
  • Subject: [mg86120] Re: Compile
  • From: Peter Pein <petsie at dordos.net>
  • Date: Sun, 2 Mar 2008 13:57:20 -0500 (EST)
  • References: <fqb8pg$n2l$1@smc.vnet.net>

Hi Michael,

I've got no explanation but if you are interested in a version of multiset
which needs uncompiled less time than multisetC, here it is:

Clear[mulset];
mulset[0] = {{}};
mulset[n_Integer] := (mulset[n] = Block[{ms = mulset[n - 1], k},
  Union[Join[Flatten[
    (ReplaceList[#1, {s___, {x_Integer, y_}, e___} :>
      Flatten[(Table[Insert[#1, {y, n}, k], {k, n}] & ) /@
        Table[Insert[{s, e}, {x, n}, k], {k, n - 1}], 1]] & ) /@ ms
   , 2],
    Flatten[(Table[Insert[#1, {n, n}, k], {k, n}] & ) /@ ms, 1]
  ]]
]) /; n >= 1

For easyer coding this function uses lists of pairs instead of flat lists.
If you want flat lists, use Flatten /@ mulset[n].

On my linux-box Mathematica 5.2 takes 2.06s for multiset[5], multisetC uses
0.285s and mulset[5] uses 0.115s (mulset[6] finishes after 5.3s).

If you are just interested in the lengths of these lists,
a[n_] = Sum[2^(i - 2*n)*Binomial[n, i]^2*(2*(n - i))!*i!, {i, 0, n}]
--> (Gamma[1 + 2*n]*Hypergeometric1F1[-n, 1/2 - n, 1/2])/2^(2*n)
is a lot faster (see http://www.research.att.com/~njas/sequences/A000681).

Regards,
Peter

P.S.: an almost uncommented notebook can be found at
http://freenet-homepage.de/Peter_Berlin/Mathe/A000681.nb

Michael Weyrauch schrieb:
> Hello,
> 
> in Mathematica V6.0.1 I define the following two functions
> 
> 
> multiset[n_] := Module[{ro, re, ms}, ro = Range[1, 2*n, 2];
> re = Range[2, 2*n, 2]; ms = Flatten[Table[{i, i}, {i, n}]];
> Select[Permutations[ms], ! MemberQ[Sign[#1[[re]] - #1[[ro]]], -1] & ]]
> 
> multisetC = Compile[{{n, _Integer}}, Module[{ro, re, ms},
> ro = Range[1, 2*n, 2]; re = Range[2, 2*n, 2];
> ms = Flatten[Table[{i, i}, {i, n}]]; Select[Permutations[ms], ! MemberQ[Sign[#1[[re]] - #1[[ro]]], -1] & ]]];
> 
> Obviously,  multisetC  ist just the compiled version of multiset.
> 
> 
> Now, I evaluate
> 
> 
> Timing[Length[multiset[5]]]
> Timing[Length[multisetC[5]]]
> 
> and obtain
> 
> {2.7339999999999995, 6210}
> {0.3440000000000003, 6210}
> so Compile was really useful.
> 
> However, if I evaluate
> 
> Timing[Length[multiset[6]]]
> Timing[Length[multisetC[6]]]
> 
>  {189.109, 202410}
> 
> 
> No more memory available.
> Mathematica kernel has shut down.
> 
> So, the compiled version fails badly and crashes the kernel. This also happens if I evaluate this statement seperately in a 
> completely fresh kernel. Enough memory is definitly available, since the uncompiled version runs smoothly. (Surprisingly the crash 
> is immediate, not after some time of working along in the program, and it happens on Windows with 2GB of memory and on Linux with 32 
> GB of memory.]
> 
> It would be nice if some could explain this unpleasant behaviour. Is there a fix or is it a bug?
> 
> Michael Weyrauch
> 
> 
> 
> 


  • Prev by Date: Re: How do twice Working Precision in square operation
  • Next by Date: Re: Mathematica 6 obtains imaginary eigenvalues for a Hermitian
  • Previous by thread: Compile
  • Next by thread: Re: Mathematica 6.0.2 update