A Random Number Generator by Mihailo Despotovic, February 1997

My term project for “Statističke metode u veštačkoj inteligenciji” (Statistical Methods in Artificial Intelligence) class, during my MSc studies at the University of Belgrade: a 16-bit “random” number made by starting with random bits, each 1 with probability p, and applying the rule A(i) = A(i−1) OR A(i+1) n times. It runs here as it did in DOS, in Serbian, with the English translation of the screen beside it. Click the screen and type, or use the buttons: U enters p, n and how many numbers; O makes them.

How random is it?

The rule turns a bit on unless both its neighbors are off, so the 1s spread, and the vector soon stops changing: within about 8 iterations when fixed, and about 16 as written, where the bit that is always 0 slows the spreading. It ends up all 1s, which is 65535 fixed and 65534 as written. If the 1s started only on every other bit, it ends up with 1s on every other bit, alternating between 43690 and 21845 (21844 as written). With no 1s at all, it stays 0. So beyond that, only these four numbers can come out: with p = 0.5, about 99% of them are the same one, and with a small p, 0 is the most common. Only a small n gives more variety.

The bugs, and the fixes

• The new last bit was computed into novi[7], which the loop then overwrote, instead of novi[15]. So novi[15] was never set and held whatever happened to be on the stack. That was almost surely not exactly 1, so the last bit of every new vector was 0, and the number was 65534 where it should have been 65535. As written, the page takes the garbage to be “not 1”.
• The starting vector could never have its top bit set: postavi() starts from 16384, while its comment says binary 1000000000000000, which is 32768. Oddly, the task statement says 0 ≤ X ≤ 32767, which only 15 bits give, but the iterations then set the top bit anyway.
• init() cleared niz[0] to niz[1000] in an array of 1000, and n = 1000 was accepted, writing past the end of the array. n = 0 was accepted too, though the requirement says 0 < n < 1000.
• “Ne postoje podaci !” (there is no data), for O before U, was printed and at once cleared by the menu, so it was never seen.

The port was checked against the original C++, compiled with 16-bit numbers as in Borland C and fed the same keys and random numbers: every screen is the same, as written and fixed.