| R J Cano on Sun, 23 Apr 2017 08:50:55 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
| Re: 4 Gigabytes of RAM are not enough! |
Untitled << :-) The last try... from Venezuela with love. >>
Greetings!,
A typo induced bug was fixed.
And the correct way of groping together instructions inside a single
while( ) was found and implemented...
Some documentation-purpose comments added.
Some old code from my entire design and authorship archives
was retrieved and inserted as an aid for illustrating some facts
(possibly research challenges);
-------------------------------[Sample output]-------------------------(Start)
parisizemax = 4294967296, primelimit = 1000000
(00:13) gp > a=Ticket3(11);
time = 1min, 27,632 ms.
\\ After all: The try was worth.
\\ Timers reduced to a half and less than a half inclusively...
(00:40) gp > a=Ticket3(10);
time = 6,454 ms.
(00:40) gp > a=Ticket3(9);
time = 579 ms.
(00:40) gp > a=Ticket3(8);s
time = 60 ms.
(00:41) gp > a=Ticket3(7);
time = 8 ms.
(00:41) gp > a=Ticket3(6);
time = 1 ms.
(00:41) gp > a=Ticket3(11);
time = 1min, 27,093 ms.
(00:42) gp > b=Ticket3(11);
time = 1min, 34,282 ms.
(00:48) gp > a==b
time = 928 ms.
%9 = 1
(00:50) gp > !sum(k=1,#a,a[k]!=b[k])
time = 23,818 ms.
%10 = 1
(00:51) gp > {for(k=1,#a,if(a[k]!=b[k],print("differs!");break))}
time = 27,324 ms.
(00:54) gp > c=Ticket3(10);
time = 8,282 ms.
(00:58) gp > for(i=1,#10,if(c[i]!=a[1+#a-i],print("Error! something
went wrong.")))
(00:59) gp > quit
Goodbye!
(End)--------------------------------------------------------------------------------
Apparently, "Ticket3_gp.txt" is flawless. It was tested against
two different slower ways of performing the same kind of
computations. They do agree.
Cheers,
Remy
P.S.: My apologizes for erroneous preceding codes "Ticket..."
...&... Beware with overflows when using w=1 option for Ticket3.
Notice if 2<=m<n, how the first m!-1 terms given by Ticket3(m,B,1) are
the same corresponding values for Ticket3(n,B,1), but multiplied/divided
by B^(n-m);
\\ PARI/GP Sourcecode, plain-text file; A000225(7) lines.
\\ Hint: For a best performance, use this script with GP2C.
Ticket3(n,{B=10},{w=0})={ /* Computes (storing them as a "t_VECSMALL" object) the arithmetic (numerical,
decimal by default) for the first n!-1 terms of the sequence A217626
if selector w=0 is used; Otherwise (for a nonzero w) computes a different
analogous sequence obtained by replacing the lexicographic order for
permutations (its underlying algorithm) with an specific alternative.
It is noticed that such different order also induces the observed property
known as "autosimilarity", but scaling particular-case subsequences by a
predictable common factor which is a function of the used base.
Yet another possibility (not implemented here) consists of replacing any of
the mentioned algorithms by the "least adjacent changes" algorithm also known
as the Steinhaus-Johnson-Trotter algorithm, which induces a quite more
complicated pattern whose explanation escapes from the illustrative
purpose of this file.
*/
my(x0:vecsmall,x:vecsmall,y:vecsmall,i:small,j:small,k:small,u:small,t:small,Q:vecsmall,bb:small,m:small,z:vecsmall);
if(n<2,n=2);
bb=B;
z=Vecsmall(0,n-1);
i=#z;
z[#z]=1;
while(1<=i--,
z[i]=z[i+1];
z[i]*=bb);
x=Vecsmall(0,n);
i=0;
while(i++<=#x,
x[i]=i;
x[i]--);
m=1;
i=1;
while(i++<=n,m*=i);
m--;
Q=Vecsmall(0,m);
k=0;
while(k++<=#Q,
x0=x;
if(w, \\ Implements Shmuel Zaks's algorithm;
u=1;
r=k;
while(u++<k+1,if(r%u,break,r\=u)); \\ These 3 initial lines are an adaptation from the Charles Greathouse IV 's A055881 program;
j=u;
j\=2;
i=0;
while(i++<=j,
t=x[i];
x[i]=x[1+u-i];
x[1+u-i]=t)
, \\ Else: Implements Narayana Pandit's lexicographic order algorithm
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) \\ Permutation algorithms implementation ends here.
);
y=x; \\ Computes the kth term for the selected sequence
r=1;
y[1]-=x0[1];
u=y[1];
u*=z[1];
Q[k]+=u;
while(r++<#y,
y[r]-= x0[r];
y[r]+= y[r-1];
u=y[r];
u*=z[r];
Q[k]+=u
)
);
return(Q)}
\\ ============================
\\ bOnUs TraCks (Appendix)
\\ ===========================
vecDiff1(v)=vector(#v-1,i,v[i+1]-v[i]);
vecDiff(v,k=1)={my(w=vector(#v-k,j,((-1)^(k%2))*sum(i=0,k,((-1)^(i%2))*binomial(k,i)*v[j+i])));w}
/*The following routine implements recursively the Steinhaus-Jhonson-Trotter algorithm trough a sieve based on modular arithmetic. Usage: Initial "d"iagonal: 0 "/" (default) or 1 "\"; "w"aving diagonals? 1 "yes" (default), or 0 "no"; Output "format" 1 "A vector of vectors" (default), or 0 "A huge vector" */
anSlowSJT_impl(n,d=0,w=1,format=1)={ /* Note: As it might be expected, the result is the n! permutations for all the digits (0..n-1) in base n */
if(n<1,return([]));
if(n==1,return([0]));
if(n==2,if(d,if(format,return([[1,0],[0,1]]),return([1,0,0,1])),if(format,return([[0,1],[1,0]]),return([0,1,1,0]))));
my(u=anSlowSJT_impl(n-1,d,w,0)); /* Internally we use only the output format zero. */
my(c=1,sqr_n=n*n);
d=!d;
my(v=vector(n!*n,i,0*if(w&&!((i-1)%sqr_n),d=!d)+(n-1)*(!d*(((i%sqr_n)%(n-1)==1)&&(1!=(i%sqr_n)))+!!d*((!(i%sqr_n))||(1==((i%sqr_n)%n-(i%sqr_n)\n))))));
for(k=0,(n-1)!-1,
for(j=1,n,
for(i=1,n-1,
if(c<=#v,
while(v[c],c++);
v[c]=u[k*(n-1)+i];
c++
)
)
)
);
c*=0;
if(format,return(vector(n!,y,vector(n,x,v[c++]))),return(v))
}
/* Note(s): 1) Here the usage of divrem() was avoided intentionally.
2) This is an experimental implementation: Probably much more slower than other choices. */
/* Examples (in the hope of waking your curiosity): Perform the following assignations, then print them...
1) X=vecDiff1(apply(fromdigits,anSlowSJT_impl(3)))/9;
2) Y=vecDiff1(apply(fromdigits,anSlowSJT_impl(4)))/9;
3) Z=vecDiff1(apply(fromdigits,anSlowSJT_impl(5)))/9;
*/
\\ (End) By: R. J. Cano; On: Apr 23 2017; Version: "Pi" (3.141592...);