R J Cano on Sat, 22 Apr 2017 08:47:06 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: 4 Gigabytes of RAM are not enough! |
( 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); }