What was the first pseudorandom number generator? Who did it? While these type of questions are hard to really answer, the book The Broken Dice by Ivar Ekeland gives a very good candidate.
Brother Edvin (a monk), sometime between 1240 and 1250 AD, was preparing a case for the sainthood of King Olaf Haraldsson, who had been the King of Norway. There was a well documented story (that could still be false) that King Olaf and the King of Sweden needed to determine which country owned the Island the Hising. They agreed to determine this by chance. They were using normal 6sided dice. The King of Sweden rolled two dice and got a 12. Then King Olaf rolled and got a 12 AND one of the dice broke (hence the name of the book) and he got an additional 1 for a 13. Some attributed this event to divine intervention, which strengthened his case for sainthood.
Brother Edvin got interested in the general question of how you can generate a random number so that nobody could manipulate it. He may have phrased it as a way to know what was divine intervention as opposed to human intervention.
 There are two players and they want to pick a random number between 0 and 5. They want the process to be such that neither player can bias the outcome. Each picks a natural number in secret. They are revealed, added, and then the remainder upon division by 6 is taken. Brother Edvin noted that the players really only need pick numbers between 0 and 5; however, he thought it best not to tell the players this since they will think they have more choice then they do.

What if its only one person. It is too easy to bias things.
But Brother Edwin proposed the following in modern notation.
 Pick a 4digit number x.
 Compute y_{1}=x^{2},
 y_{1} will be 7 or 8 digits. Remove the two leftmost digits and one or two rightmost digits to obtain a 4digit number z_{1}.
 Repeat this process four times to obtain z=z_{4}.
 Divide z by 6 and take the remainder.
The method was rediscovered by von Neumann in a different context. He wanted to generate long randomlooking sequences of numbers. His idea was to take a 4digit number x_{1}, square it, and take the middle 4 digits, repeat some number of times (say 4) to obtain x_{2} then repeat to get more and more numbers. It was abandoned since the periods weren't that large. People used linear congruential generators instead. (Are they still used?)
However, Brother Edvin does deserve LOTS OF credit. Given the math known in his day it is impressive that he asked these questions and got some reasonable answers.
Edwin's construction sounds more like a hash function than a random number generator.
ReplyDeleteSo 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).
ReplyDeleteIn the one person case, one can use hardness of discrete log: Pick a nonzero number mod 17, and the ~random~ number is then log modulo 3 (or any other generator).
ReplyDeleteIn the twoparty case, this is a coinflipping protocol. In the oneparty case, this is more like a deterministic extractor. In any case, none of them is a pseudorandom generator...
ReplyDeleteHow certain are we that this is an historical and not an apocryphal tale? Would a 13th century monk have even been using arabic numerals? Has anyone looked at the book's references?
ReplyDeleteThe document exists, I described it in modern terms. However, YES I will
ReplyDeletecheck the refs more carefully later and leave a comment about it.
The author claims to have read the manuscript of Brother Edwin himself. I have found nobody on the web calling him a fraud
ReplyDelete(then again, not much is on the web on his book),
so I am willing to belive the story.
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.
ReplyDeleteThe 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.
huh?
ReplyDeleteYou talk about Brother Edvin AFTER discussing dice? Don't dice generate random numbers?