Re: 4 Gigabytes of RAM are not enough!

[R J Cano <0xcc00ffffeeee@gmail.com>]

 ( Untitled: << The mighty "t_VECSMALL" >> )

Greetings!,

Partially solved: -1+11! terms for A217626 successfully achieved
without hanging up the OS, by harnessing an smaller representation,
and fully inline code...

( For the used code please see the attachment )

Example running on Linux @ and AMD64 E-300:

------------------------[ Sample dump -- Start ]------------------------

PARI/GP is free software, covered by the GNU General Public License,
and comes WITHOUT ANY WARRANTY WHATSOEVER.

Type ? for help, \q to quit.
Type ?15 for how to get moral (and possibly technical) support.

parisizemax = 4294967296, primelimit = 1000000
(01:47) gp > t=Ticket(11);
time = 2min, 25,509 ms.

(02:14) gp > #t
%12 = 39916799
(02:23) gp > sizebyte(t)/2^20+.
%13 = 304.54101562500000000000000000000000000
(02:23) gp > \\ Just approx. 305 megas of consumption.

------------------------[ Sample dump -- End ]------------------------

Cheers,
Remy.

P.S.: I noticed the (2) error(s) about cross-posting mail lists. Merci!.

 .
 .
 .

2017-04-19 15:13 GMT-04:00, Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>:
> On Wed, Apr 19, 2017 at 05:01:28AM -0400, R J Cano wrote:
>>   Greetings,
>>
>>   This time featuring a problem that seems to be a RAM-memory's pacman
>> monster...
>>
>>   Briefly: If you are looking for arbitrary symmetric/antisymmetric
>> patterns inside the first N!-1 terms of oeis.org A217626, ...for N>6
>> the problem becomes (yet inclusive if having a very simple and
>> efficient script!) intractable due there is no enough RAM to complete
>> the corresponding report...
>>
>>  Attached to this mail comes a PARI/GP script which can be used to
>> appreciate that issue.
>>
>> The usage is simple, load it and set:
>>
>> p=vecDiff(A217626_vec_1(7));
>>
>> then run the following search&report:
>>
>> q=Patterns(p,1,5,1);
>>
>> Which tells Patterns( ) to search for any pattern of size 5, and
>> exclusively (e=1) size 5,
>>
>> For example the pattern [1,9,2,9,1] or the first 3!-1 terms of A217626
>> should be present (7-3+1)! = 120 times; However: The execution crashes
>> before allowing us to verify that!!, giving up due lacking of stack.
>
> The problem is that the output of Patterns is too large to fit
> in the memory, this is not a problem with the algorithm:
>
> ? p=vecDiff(A217626_vec_1(6));
> ? q=Patterns(p,1,5,1);
> ? sizebyte(q)
> %15 = 1998476512
>
> so q is almost 2GB. You need to find a more compact representation for
> the output of Patterns if you want to go farther
>
> Cheers,
> Bill.
>
> PS: please avoid crossposting between pari-dev and pari-users, a lot of
> people are subscribed to both lists and so receive it twice.
>

/* (PARI) R. J. Cano, Apr 22 2017; Note: For a best performance, use this script with GP2C. */

Ticket(n,{B=10})={ /* Computes a "final representation" (by default in decimal) for the first n!-1 terms of A217626, storing them as a "t_VECSMALL" object */

  n=max(2,n);
  my(x0:vecsmall,x:vecsmall,y:vecsmall,i:small,j:small,k:small,u:small,t:small,Q:vecsmall,p:small,bb:small,m:small);
  x=Vecsmall(vector(n,i,i-1));
  m=n!-1;
  Q=Vecsmall(0,m);
  k=0;
  bb=B;

  while(k++<=#Q,

    x0=x;

    i=#x-1;
    while((x[i]>=x[i+1])&&i,i--);
    j=#x;
    while((x[i]>=x[j])&&(j>i),j--);
    t=x[j];
    x[j]=x[i];
    x[i]=t;
    u=#x-i;
    u\=2;
    u++;
    while(u--,
      t=x[i+u];
      x[i+u]=x[1+#x-u];
      x[1+#x-u]=t;
    );

    y=x;
    for( r=1, #y  , y[r  ]-= x0[r] );
    for( r=1, #y-1, y[r+1]+=  y[r] );
    p=1;
    for( r=1, #y-1, Q[k  ]+=  y[#y-r]*p; p*=bb )

  );

  return(Q);

}