Re: Partition code

[Karim Belabas <Karim.Belabas@math.u-psud.fr>]

* Jon Perry [2004-02-12 15:12]:
> This code generates all the partitions for n. It runs out of stack space
> (4Mb) at about n=25, but only takes ~30secs at 100Mhz to n=20.
> 
> Can anyone suggest any improvements?

Here's a quick hack:

  do(k, n, m) =
  {
    if (n <= 0, P[ip++] = vectorsmall(k-1, i, current[i]); return);
    if (n < m, m = n);
    for (i = 1, m, current[k] = i; do(k+1, n-i, i))
  }
  partitions(n)=
  { 
    ip = 0; P = vector( numbpart(n) );
    current = vector(n); do(1, n, n); P
  }

On my machine, it is 9 times faster than your version at n = 20,
37 times faster for n = 30.

I do not include trailing 0s, and used "small vectors" to save on memory.
You can use vector() instead of vectorsmall() if you don't use the unstable
release: timings are about the same but memory use is 3 times higher.

If you don't want to store them, you can remove the global array P, and do 
something instead of the first statement in do() .


Another (hackish) solution, with unstable: 

1) go to src/modules/galois.c, and remove the "static" keyword in the
definition of the 'partitions' function.

2) install(partitions, L)

3) x = partitions(n)   [ can't use partitions(n) directly since it's not meant
to be publicly accessible, and GP can't handle its output wrt garbage
collecting. Copied into a variable, it's OK... ]

This is about 80 to 85 times faster than the above routines.

    Karim.
-- 
Karim Belabas                     Tel: (+33) (0)1 69 15 57 48
Dep. de Mathematiques, Bat. 425   Fax: (+33) (0)1 69 15 60 19
Universite Paris-Sud              http://www.math.u-psud.fr/~belabas/ 
F-91405 Orsay (France)            http://pari.math.u-bordeaux.fr/  [PARI/GP]