🚀 go-pugleaf

In article <1992Nov1.002124.8318@news.media.mit.edu> elwin@maidavale.media.mit.edu (Lee W Campbell) writes:
>In article <BwyFuK.Hn5@mentor.cc.purdue.edu>, hrubin@pop.stat.purdue.edu (Herman Rubin) writes:
>|> In article <1992Oct30.182002.11907@netcom.com> tjm@netcom.com (Thomas J. Merritt) writes:
>|> >In article <BwxsF6.3DF@mentor.cc.purdue.edu> hrubin@pop.stat.purdue.edu (Herman Rubin) writes:

			..................

>|> I HAVE posted the real code.  Let me state the problem:  It is desired to

>[rest deleted]

>   No, not really, Herman. You posted a fragment, but with some globals and/or
>macros referenced but never defined. With those undefined items, compilers
>can't compile it, optimizers can't optimize it, and humans can only guess at
>what it's supposed to do.

>   Thank you for taking the trouble to post what you did. Since you went to
>that much trouble, I am going to request that you go to a little more trouble.
>Plese take the piece of code you did post. Wrap it into a function definition.
>Write a little test routine to call the random number subroutine and verify
>correct behavior (e.g. print out randoms, compute statistics, make a histogram,
>whatever).

I will do partly as you say.  The proof of correctness of this program is
simple enough for someone who looks at the commented version, not the program,
that I will not do the testing.  However, I will embellish the program, and
put it as part of a loop to generate an array, which is as it should be used.
For SOME parts I will use macros, and it is these specific places where much
time can be saved by improved hardware.  This will be done in such a way 
that there is valid code.

What I am criticizing is the claim that the present HLL's, without goto's,
can do a good job of handling this situation.  This can be judged by 
inspection of the assembler code, as I believe the inefficiencies will
stand out.  As I stated, I am not opposed to the use of switch statements,

While writing this out, I have come up with some changes which improve the
performance, but do not change the essential ideas.  One of the biggest such
changes is a code rearrangement, which may not be easy to carry out.  The
key pieces of information for this are:

	For each g, the probability that g=i is 2^-i
	The expected number of times start is reached is 3.08
	The expected number of times add is reached is 1.54

	label1 is always reached.  The proportion of times
	label2, label3, label4, label5, and labelh are reached
	are approximately .21, .032, .004, .0004, and .000034.
	label1 is directly reached from the if(g==2) statement
	with probability .77.

-------------------------------------------------------------------------
There are two macros in this code, and to avoid errors, I will here give
possible ways of doing them.  The code should be improved to reduce the 
number of tests greatly.  

GEOM
	if(gp > gend){grefill();gp=gptr[0];gend=gptr[1];}
	g = *gp++;

BIT
	if(ct == 0){ if(up > uend){urefill();up=uptr[0];uend=uptr[1];}
			ib = *up++;
			ct = WORD_LENGTH;}
	bit = ib&i;
	ct -= 1;
	ib >>= 1;
----------------------------------------
extern usigned int B;
expskeleton(nar,mar,length,gptr,uptr)
int nar[],mar[],length,*gptr[],*uptr[];
{static int ct, avbits;
int n,m,b,g,j,g4,g16,j,i;
register int *gp,*gend,*up,*uend,ic,ib,iB;
iB = B;
gp = gptr[0]; gend=gptr[1]; up=uptr[0]; uend=uptr[1]; ic=ct; ib=avbits;
for(l=0;l<length;l++){
n = 0; m = 0; b = iB;
goto start;
add:	n += 1;
start:	GEOM;
	if(g==1)goto add;
	if(g==2)goto label1;
	if(g==3)goto start;
	if(g==4)goto label2;
	if(g==5||g==6)goto start;
	if(g==7){g4=1; goto label3;};
	if(g==8){GEOM; g4=g>>1;
		if(g&1){g4+=2; goto label3}
		goto label4;}
	if(g > 8 && g <= 12) goto start;
	g16 = (g-9)>>4;
	g &= 3;
		if(g==1)goto label5;
		if(g==2 || g==3)goto start;
		GEOM;
		g4 = (g+1)>>1;
		if(g&1){j=6; goto labelh;};
			j = 7;
			GEOM;
			if(g%3 != 2)goto start;
loop:				BIT; if(bit) goto labelh;
				j += 1;
				GEOM;
				if((2<<(g-1)/j)&1 == 0)goto start;
				goto loop;

labelh:	i = C(j); b >>= 1;
	if(i==j || i==0)goto labelh:
	m |= b;
	if(i==1)goto label1;
	if(i==2)goto label2;
	if(i==3)goto label3;
	if(i==4)goto label4;
label5: b >>= g16; m |= b; GEOM;
	BIT; if(bit){if(g&1)goto label2; goto label1;}
		g4 = (g+1)>>1;
		if(g&1)goto label3;
label4: GEOM;
	if(g4 < g){m |= (b>>g4 | b>>g); goto label1;}
		m |= b>>g;
		BIT; if(bit)goto label1;
			b >>= 1;
label3: b >>= g4: m |= b; b <<= 1;
label2: GEOM; m |= (b>>g);
label1: nar[l] = n; mar[l]=m;
}
gp = gptr[0]; gend=gptr[1]; up=uptr[0]; uend=uptr[1]; ic=ct; ib=avbits;
gptr[0] = gp; gptr[1]=gent; uptr[0]=up; uptr[1]=uend; ct=ic; avbits=ib;
return;
}



-- 
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399
Phone: (317)494-6054
hrubin@pop.stat.purdue.edu (Internet, bitnet)  
{purdue,pur-ee}!pop.stat!hrubin(UUCP)