#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) void flipped(int node, 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; } node <<= 1; if( TEST(values,a,b) == coin ) { /* numeric successor: */ flipped(node|1, coin); /* alphabetic successor: flipped(node, 0) tail recursion changed to a loop. */ coin = 0; } else { SET(out,bcount>>5,bcount&31,coin); ++bcount; /* alphabetic successor: flipped(node, 1) tail recursion changed to a loop. */ coin = 1; } } } int get_bit() { while(!bcount) { SET1(exists,0,1); SET(values,0,1,coinflip()); flipped(1,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"); } /* perl: my (\$exists, \$values,\$out); sub flipped { my (\$node,\$coin) = @_; for( ; ; \$node <<= 1 ) { if( vec(\$exists, \$node, 1) ^= 1 ) { vec(\$values, \$node, 1) = \$coin; return; } elsif( vec(\$values, \$node, 1) == \$coin ) { flipped( (\$node<<1)|1, \$coin ); \$coin = 0; } else { \$out .= \$coin; \$coin = 1 } } } sub get_bit { flipped 1, coinflip until length \$out; chop \$out; } */