public class ALFGenerator extends RandomNumberGenerator {
        // ALFG lag distance choices:  7, 17, 55, 159, 607, 1279
        private final static int UTS_ALFG_L=55;

        // masks
        private final static int POS_MASK = 0x7fffffff;
        private final static int HIGH_BIT = 0x80000000;

        // RNG state
        private int state_size, seed, cbit;
        private int runup,      k,    l;
        private int kp,         lp,   zp;
        private int[]  reg = new int[UTS_ALFG_L];
        private int[] node = new int[UTS_ALFG_L];

        // RNG from seed
        public ALFGenerator(int seedarg) {
                int i,j;
                int[] tmp = new int[861];
                state_size=2*UTS_ALFG_L+9;
                l=UTS_ALFG_L;
                switch (l) {
                        case 7:     k = 4;   cbit = 1;   runup = k*71;   break;
                        case 17:    k = 12;  cbit = 5;   runup = k*65;   break;
                        case 55:    k = 31;  cbit = 18;  runup = k*93;   break;
                        case 159:   k = 128; cbit = 63;  runup = k*179;  break;
                        case 607:   k = 334; cbit = 166; runup = k*628;  break;
                        case 1279:  k = 861; cbit = 233; runup = k*1291; break;
                        default:    System.out.print("\n\n\tinvalid UTS_ALFG_L value: "+l+"\n\n"); System.exit(0);
                }
                seed = seedarg;
                lp = l-1;
                kp = k-1;
                zp = 0;
                for(i=0; i<l-1; i++) node[i] = 0;
                node[0] = 2;
                for(i=0; i<l  ; i++) reg[i] = 0;
                reg[cbit] += 1;
                // adjust initial value of seed up one bit, and xor into reg[0]:
                seed = ((seed << 1) & POS_MASK);
                reg[0] = 2^seed;
                for(j=0; j<runup; j+=k)
                {
                        for(i=0; i<k; i++) tmp[i]  = reg[i+l-k];
                        for(i=k; i<l; i++) reg[i]  = reg[i-k];
                        for(i=0; i<k; i++) reg[i] += tmp[i];
                }

        };

        // RNG from parent
        public ALFGenerator(ALFGenerator parent, int spawnnumber) {
                int j;
                int[] tmp = new int[861];
                // update parent
                if(--parent.zp < 0) parent.zp += (parent.l-1);
                if((parent.node[parent.zp] & HIGH_BIT)!=0) {
                        System.out.println("ALFG Node Limit Reached");
                        System.exit(0);
                }
                parent.node[parent.zp] <<= 1;
                // copy to child
                state_size    = parent.state_size;
                seed          = parent.seed;
                cbit          = parent.cbit;
                runup         = parent.runup;
                k             = parent.k;
                l             = parent.l;
                kp            = parent.kp;
                lp            = parent.lp;
                zp            = parent.zp;
                for (int i=0; i<l; i++) {
                        node[i] = parent.node[i];
                        reg[i]  = parent.reg[i];
                }
                // parent node move
                parent.node[zp] +=2;
                // complete child
                j = zp;
                for(int i=0; i<l-1; i++) {
                        reg[i] = node[j];
                        if(++j == (l-1)) j = 0;
                }
                reg[cbit] += 1;
                reg[0]    ^= seed;
                reg[l-1]   = 0;
                lp         = l - 1;
                kp         = k - 1;
                for(int jt=0; jt<runup; jt+=k) {
                        for(int i=0; i<k; i++) tmp[i]  = reg[i+l-k];
                        for(int i=k; i<l; i++) reg[i]  = reg[i-k];
                        for(int i=0; i<k; i++) reg[i] += tmp[i];
                }
        };

        public int nextrand() {
                int n;
                reg[lp] +=  reg[kp];
                n = (reg[lp] >> 1) & POS_MASK;
                if(--lp < 0) lp = l-1;
                if(--kp < 0) kp = l-1;
                return n;
        };

        public int rand() {
                return (reg[lp] >> 1) & POS_MASK;
        };

        public String showstate() {
                String alfgstate = "ALFG state=";
                alfgstate += "|"+java.lang.Long.toHexString( 0x10000L | l ).substring(1).toUpperCase();
                alfgstate += "|"+java.lang.Long.toHexString( 0x10000L | k ).substring(1).toUpperCase();
                alfgstate += "|"+java.lang.Long.toHexString( 0x10000L | kp).substring(1).toUpperCase();
                alfgstate += "|"+java.lang.Long.toHexString( 0x10000L | lp).substring(1).toUpperCase();
                alfgstate += "|"+java.lang.Long.toHexString( 0x10000L | zp).substring(1).toUpperCase();
                alfgstate += "|";
                return   alfgstate;
        };

        public String showtype() {
                return "ALFG (statesize=" + state_size + ", L=" + UTS_ALFG_L + ")";
        };

        public static void main(String[] args) {
                double et=0.0;
                int i=0;
                int j=0;
                int r=0;
                int NUM_RNG_SPAWNS = 1600;
                ALFGenerator parent = new ALFGenerator(0);
                ALFGenerator[] child = new ALFGenerator[NUM_RNG_SPAWNS];
                for (i=0; i<2000; i++) {
                        r=parent.nextrand();
                }
                for (i=0; i<10; i++) {
                        r=parent.nextrand();
                        System.out.println(parent.showstate()+", NEXT="+r);
                }
                parent = new ALFGenerator(0);
                for (j=1; j<NUM_RNG_SPAWNS; j++) {
                        child[j] = new ALFGenerator(parent,j);
                        for (i=0; i<1000; i++) {
                                r=child[j].nextrand();
                                r=parent.nextrand();
                        }
                }
                parent = new ALFGenerator(0);
                for (j=1; j<20; j++) {
                        child[j] = new ALFGenerator(parent,j);
                        for (i=0; i<NUM_RNG_SPAWNS; i++) {
                                r=child[j].nextrand();
                                r=parent.nextrand();
                        }
                        r=child[j].nextrand();
                        System.out.println(child[j].showstate()+", NEXT="+r);
                }
                System.out.println("Timing "+NUM_RNG_SPAWNS+" RNG spawns ...");
                parent = new ALFGenerator(0);
                et = -(double)System.nanoTime();
                for (i = 1; i < NUM_RNG_SPAWNS; i++) {
                        child[i] = new ALFGenerator(parent,i);
                }
                et += (double)System.nanoTime();
                et *= 1.0e-09;
                System.out.println("Wall clock time = "+et+" sec, "
                                    +et/NUM_RNG_SPAWNS+" sec/spawn, "
                                    +NUM_RNG_SPAWNS/et+" spawns/sec");
                System.out.println("Number of Successful Spawns i="+i);
                et = -(double)System.nanoTime();
                for (i=0; i<1000000; i++) {
				}
                et += (double)System.nanoTime();
                et *= 1.0e-09;
                System.out.println("wall="+et+"   rnd/s="+1000000./et+"   s/rnd="+et/1000000.);
        }
}