Re: 4 Gigabytes of RAM are not enough!

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

 ( Humorously untitled << Traveling back in time: If our universe was
sourcecoded in the beginning, then Photons are ruled by C/C++ >> )

Greetings!.

Happily, we might observe that the code becomes faster each time its
look turns more similar to C code.  Therefore we might ask ourselves
for the fastest version we might achieve, without becoming
incompatible with libpari and GP;

The answer, apparently comes by translating everything aiming to keep
everything more properly "code-factorized" inside while loops, and
perform separately compound arithmetic operations for harnessing the C
low-level offered optimization for operators.

Of course these better results shown below are obtained after GP2C compilation:

----[ sample dump starts]-----------------------

parisizemax = 4294967296, primelimit = 1000000
(09:29) gp > p=Ticket2(11);
time = 19,934 ms.
(09:29) gp > sizebyte(p)/(2^20)+.
%3 = 304.54101562500000000000000000000000000

----[ sample dump ends]-----------------------

The same OS, env. and machine than before was used. AMD64 E-300,
Linux. PARI-GP 2.9.2

Cheers,

Remy

P.S.: The key part of the solution is the fortunate existence of
"t_VECSMALL" in GP;
        :-) Thanks pari-dev team for that.

2017-04-22 2:46 GMT-04:00, 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. */

Ticket2(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,r: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;
    u-=i;
    u\=2;
    u++;
    while(u--,
      t=x[i+u];
      x[i+u]=x[1+#x-u];
      x[1+#x-u]=t;
    );
    y=x;
    r=0;
    p=1;
    while(r++<#y, 
      y[r  ]-= x0[r];
      y[r+1]-= x0[r+1];        
      y[r+1]+=  y[r];
      Q[k  ]+=  y[#y-r]*p;
      p*=bb      
    )     
  );
  return(Q);
}