Karim Belabas on Thu, 12 Feb 2004 18:10:01 +0100 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: Partition code |
* 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]