#include int bits_used = 0; unsigned int coinflip() { static unsigned long y = 123; y=1664525L*y+1013904223L; ++bits_used; printf("%d", y>>31); return y >> 31; } unsigned long exists[32]={0}, values[32], out[1], bcount=0; #define TEST(x,a,b) ( (x[a]>>(b)) & 1 ) #define SET1(x,a,b) (x[a] |= (1uL<<(b))) #define SET0(x,a,b) (x[a] &=~(1uL<<(b))) #define SET(x,a,b,c) ((c)?SET1(x,a,b):SET0(x,a,b)) #define FLP(x,a,b) (x[a] ^= (1uL<<(b))) #define FLIP(x,a,b) ((FLP(x,a,b)>>(b))&1) /* this uses bits 1% more efficiently than a naive selection of node indices for the tree structure. */ void flipped(int node, int len, int plen, int coin) { while( node < sizeof(exists)*8 ) { int a = node>>5, b = node&31; if( FLIP(exists,a,b) ) { SET(values,a,b,coin); return; } if( TEST(values,a,b) == coin ) { int x = len+plen; /* numeric successor */ flipped(node+len+x+x, len+x, x, coin); /* alphabetic successor: flipped(node+len, len+plen, len, 0) tail recursion changed to a loop. */ coin = 0; } else { SET(out,bcount>>5,bcount&31,coin); ++bcount; /* alphabetic successor: flipped(node+len, len+plen, len, 1) tail recursion changed to a loop. */ coin = 1; } node += len; len += plen; plen = len-plen; } } int get_bit() { while(bcount<=0) { SET1(exists,0,0); SET(values,0,0,coinflip()); flipped(0,1,0,coinflip()); } --bcount; return TEST(out,bcount>>5, bcount&31); } void test() { int i, first=1; for( i = 0; (i < 8) || bcount>0; ++i) { printf("%c", get_bit() ? '+' : '-'); } printf("\n"); } /* The flipped() subroutine uses an array to keep track of the state of a finite number of the infinite number of rows in Mitzenmacher's AMLS algorithm. [Actually two arrays, but since they're of the same length, considering one is sufficient.] As you keep flipping coins, each row gets coin flips from its predecessor at a certain rate and produces output bits at a certain rate. Ideally, we'd like to capture all the output bits from all the rows. Inefficiency is caused by the fact that we don't get the output bits that would have been produced by the rows represented in array elements beyond the end of the array. The algorithm would be most efficient if it kept the most productive rows, in terms of number of output bits produced. In flipped2n2n1(), the row represented in array element [n] has its alphabetic successor row at array element [2n] and its numeric successor row at array element [2n+1]. But the alphabetic successor is more productive than the numeric successor. For example, when the bits from coinflip() are unbiased, the alphabetic successor row is twice as productive as the numeric successor row. We'd like to keep more alphabetic successor rows in the array than numeric successor rows. Rather than storing both successor rows near [2n], it would be better to put the alphabetic successor at [1.5n] and the numeric successor at [3n]. Well, that doesn't work, but... Something similar can be done. Regard the rows as being in lines. Put all the alphabetic successors of the rows in a given line in the next line and all the numeric successors in the line after that. 1st line: O, Original row. 2nd line: A, Alphabetic successor of original row. 3rd line: AN, Alpha successor of 2nd line, numeric of 1st line. 4th line: AAN, Alpha successors of 3rd line, numerics of 2nd line. 5th line: AAANN, Alphas of 4th line, numerics of 3rd line. 6th line: AAAAANN, Alphas of 5th line, numerics of 4th line. ... The order in which the rows appear above is the order in which they are represented in the array used by the Fibonacci version of flipped(). For example, the 3 rows in the 4th line are in array elements [4..6], just before the 5 rows in the 5th line which are in array elements [7..11]. When the bits from coinflip() are unbiased, all the rows in a given line are approximately equally productive, and approximately twice as productive as the rows in the next line. Since the rows are in non-increasing order of productivity, the rows in the array are all at least as productive as any of the rows lost beyond the end of the array, minimizing the output bits lost because of the finite size of the array. When there's bias, the As in a line are somewhat more productive than the Ns in that line, so I put them first. The number of rows in a line forms a Fibonacci series. --Mike Amling Note to self, the lines could more reasonable be labeled as: 1st line: O 2nd line: A 3rd line: AA, N 4th line: AAA,NA, AN, 5th line: AAAA,NAA,ANA, AAN,NN 6th line: AAAAA,NAAA,ANAA,AANA,NNA, AAAN,NAN,ANN But this doesn't show the fibbonnacci nature of the length clearly. The initial form used for this was: func( base, across, lineLen, prevLineLen ) { thisNode = base+across; // alphabetic: func( base+lineLen, across, lineLen+prevLineLen, lineLen ); // numeric: func( base+lineLen+prevLineLen, across+lineLen, lineLen+prevLineLen*2, lineLen+prevLineLen ); } But base+across can be combined to one term as follows: func( thisNode, lineLen, prevLineLen ) { // alphabetic: func( thisNode+lineLen, lineLen+prevLineLen, lineLen ); // numeric: func( thisNode+lineLen+prevLineLen+lineLen, lineLen+prevLineLen*2, lineLen+prevLineLen ); } */