Tuesday, January 26, 2010

The First pseudorandom generator- probably




    1. Pick a 4-digit number x.
    2. Compute y1=x2,
    5. Divide z by 6 and take the remainder.




  1. Edwin's construction sounds more like a hash function than a random number generator.

  2. So what do people use rather than a linear congruential generator? Lagged Fibonacci? Mersenne Twister is way way too hard to remember (though it's free to use, so perhaps you don't need to).

  3. In the one person case, one can use hardness of discrete log: Pick a non-zero number mod 17, and the ~random~ number is then log modulo 3 (or any other generator).

  4. In the two-party case, this is a coin-flipping protocol. In the one-party case, this is more like a deterministic extractor. In any case, none of them is a pseudorandom generator...

  5. How certain are we that this is an historical and not an apocryphal tale? Would a 13-th century monk have even been using arabic numerals? Has anyone looked at the book's references?

  6. The document exists, I described it in modern terms. However, YES I will
    check the refs more carefully later and leave a comment about it.

  7. The author claims to have read the manuscript of Brother Edwin himself. I have found nobody on the web calling him a fraud
    (then again, not much is on the web on his book),
    so I am willing to belive the story.

  8. According to Ekeland, the original manuscript disappeared, a copy of it, however, was sent to him by Jorge Luis Borges, who detected it in the Vatican archives.
    The hint to Borges, best known for his beautiful literary hoaxes and forgeries, proves that there is no manuscript and no Brother Edvin. However: "si non e vero, e ben trovato" if it is not true, it is perfectly invented.

  9. huh?

    You talk about Brother Edvin AFTER discussing dice? Don't dice generate random numbers?