Re: new GP loop: forpart()

[Bill Allombert <Bill.Allombert@math.u-bordeaux1.fr>]

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([5])
> > 
> 
> 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.