Nethack

From Kenny Root

This page describes the Nethack RNG hack I have planned.

I plan on using an FPGA to simulate running billions of transactions across the UNIX random() implementation to determine when is a good time to #dip or quaff from a fountain to get a wish.

Currently the PC version of this takes about 3 hours to run.

Notes on the UNIX pseudo-random number generator: http://www.mscs.dal.ca/~selinger/random/

Notes from Ben Jackson:

Ben says, "if you have a '*16807%2^n-1' engine it only runs 31 out of 
 340+clocks"
Ben says, "so you should find a way to share that"
Ben says, "so yeah, your process should look like:  something that takes a 
 seed and every 31 clocks produces 32 state registers"
Ben says, "the output of that should go to random number generators"
Ben says, "no, the seeding round makes the 32x 32 bit state words"
Ben says, "then to finish the 'srandom' seeding you have to generate 310 
 random numbers"
Ben says, "there are ~10 rand engines per seed engine" (31 clocks x 10 = 310 random numbers)
Ben says, "now the seed engine may take longer than 31 clocks"
Ben says, "the big divide might be a killer"
Ben says, "shame it's not %2^31"

Broken Verilog:

//------------------------------------
//
// Initialize random number pool
//
//------------------------------------								
module srandom(
seed, // integer seed
pool
);
 
// constants
parameter WIDTH = 32;
parameter LENGTH = 31;
 
// Ports
input [WIDTH-1:0] seed;
output [WIDTH-1:0] pool [LENGTH-1:0];
 
// Internal
integer i;
time tmp;
 
pool[0] = seed;
for (i = 1; i < 31; i = i + 1) begin
  tmp = 16807 * pool[i - 1];
  pool[i] = tmp % 2147483647;
  if (pool[i] < 0) begin
    pool[i] = pool[i] + 2147483647;
  end
end
 
for (i = 31; i < 34; i = i + 1) begin
  pool[i] = pool[i - 31];
end
 
for (i = 34; i < 344; i = i + 1) begin
  pool[i % POOL_SIZE] = pool[(i - 31) % POOL_SIZE] + pool[(i - 3) % POOL_SIZE];
end
 
initial begin
  $display("seed = %h", seed);
end
endmodule
 
 
//------------------------------------
//
// Actual random number output module
//
//------------------------------------
module random(
a, // i - 31
b, // i - 3
out // next random number
);
 
input a, b;
output out;
 
wire a, b;
wire out;
 
out <= (a + b) >> 1;
 
endmodule