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