|Bill Allombert on Wed, 05 Jun 2013 20:47:10 +0200|
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
|Re: new GP loop: forpart()|
On Wed, Jun 05, 2013 at 10:43:01AM +0200, Joerg Arndt wrote: > * Bill Allombert <Bill.Allombert@math.u-bordeaux1.fr> [May 30. 2013 14:06]: > > Dear PARI developers, > > > > I have commited a patch by Pascal and myself that adds GP function > > to loop over partitions: > > > > forpart(v=5,print(v)) > > Vecsmall([1,1,1,1,1]) > > Vecsmall([1,1,1,2]) > > Vecsmall([1,2,2]) > > Vecsmall([1,1,3]) > > Vecsmall([2,3]) > > Vecsmall([1,4]) > > Vecsmall() > > > > Documentation issue: > This (as least as displayed) is not lex order, but colex. > Should also add representation: > "The partitions are vectors (of type Vecsmall) containing a > weakly increasing list of parts." > (or some prettier wording). For reference: the old partition function says: /* the partitions are generated in Abramowitz-Stegun order: * first the partitions with 1 element, then those with 2, then * those with 3 until 1+1+1+..+1=n, the longest, is created. p is the * length of these partitions. */ This is the numeric order : 11111 > 1112 > 122 > 113 > 23 > 14 > 5 I agree with your clarification, though. > Are the partitions _internally_ represented as > weakly decreasing lists? No, we use weakly increasing lists, as returned. > Looking at the forpart_next() code in the > snapshot pari-2.6.0-68-g63d35a5 I expected > a not so great performance. > However, I get > forpart(p=90,) > time = 3,140 ms. You have to substract the time for the empty loop: On my laptop: ? forpart(p=90,) ? ## *** last result computed in 4,237 ms. ? for(i=1,56634173,) ? ## *** last result computed in 2,965 ms. so we get ~ 1,272 ms. > That's quite OK (166 cycles per update), > cf. my partitions into exactly m parts > takes 18 cycles per update (and 10 cycles > would already be excellent in practice). Yes, you have to compare that to the time of any meaningful computation: eg. ? for(i=1,56634173,1+1) ? ## *** last result computed in 6,496 ms. Cheers, Bill.