This work is licensed under a
Creative Commons License.
|
Tuesday, January 26, 2010
The First pseudorandom generator- probably
Posted by GASARCH
(The following was told to be by Ilan Newman at Dagstuhl 2009. His source was the book The Broken Dice and other mathematical tales of chance.)
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 6-sided 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.The hope is that it is very hard for a human to bias the results by picking a particular original 4-digit number. Brother Edvin did note that some choices for x make the final choice choice obvious and hence not random (e.g., 1001). Brother Edvin proposed some solution: make sure the initial x has no 0's and no repeated digits. He also suggesting taking more initial digits or more times that you iterate the process. But he does realize that this might not work.
- 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 4-digit number x.
- Compute y1=x2,
- y1 will be 7 or 8 digits. Remove the two leftmost digits and one or two rightmost digits to obtain a 4-digit number z1.
- Repeat this process four times to obtain z=z4.
- Divide z by 6 and take the remainder.
The method was rediscovered by von Neumann in a different context. He wanted to generate long random-looking sequences of numbers. His idea was to take a 4-digit number x1, square it, and take the middle 4 digits, repeat some number of times (say 4) to obtain x2 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.10:33 AM
# 7 comments
-
Edwin's construction sounds more like a hash function than a random number generator.
-
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).
-
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).
-
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...
-
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?
-
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.
-
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.
Links to this post:
Weblog Home
Archives
