[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Wesnoth-wiki-changes] PseudoRandomNumberGeneration
From: |
wiki |
Subject: |
[Wesnoth-wiki-changes] PseudoRandomNumberGeneration |
Date: |
Sun, 14 Nov 2004 12:19 +0100 |
UserAgent: Mozilla/5.0 (Macintosh; U; PPC Mac OS X; en) AppleWebKit/125.4
(KHTML, like Gecko) Safari/125.9
IP: 66.189.14.56
URI: http://wesnoth.slack.it/?PseudoRandomNumberGeneration
- - - - -
Index: PseudoRandomNumberGeneration
===================================================================
RCS file: /home/wesnoth/cvsroot/wikiroot/PseudoRandomNumberGeneration,v
retrieving revision 1.6
diff -u -r1.6 PseudoRandomNumberGeneration
--- PseudoRandomNumberGeneration 14 Nov 2004 10:07:47 -0000 1.6
+++ PseudoRandomNumberGeneration 14 Nov 2004 11:19:04 -0000
@@ -131,6 +131,36 @@
[/while]
#enddef
+ -----
+ (It's been quite a bit of space and time, but this is still EP)
+ The Story (It isn't told in order or completely, but it's still the story)
+
+ I got my pseudorandom number generation (to be referred to as PRNG) formula
from a book by Knuth. It is as follows:
+ Xn+1=(aXn + c) mod m
+ That was difficult to do in code. I don't have multiplication[1] OR modulus
in my arsenal, so I had to imitate them using while loops.
+ Then, I had to choose good values for a, c, and m. Since the 'random'
sequence always loops eventually, the duration of the loop is called the
period. In
+ order to have a period of length m, the maximum, the numbers had to fill
several conditions.
+ That wasn't hard, but the numbers were at first way too small. I increased
them. They did not fulfill my worries that the the process would be too slow,
+ fortunately, though it's much MUCH slower than doing these operations in a
standalone C application or whatever. Something like that could go through
+ all 32768 possible values in less than a second.
+ Anyway, I at first made the mistake of extracting values by regenerating the
randomseed until it was below the requested value. (that was incredibly
+ stupid. It means that there are only so many possible values, thus it wrecks
the randomseed.) After that I used modulus extraction, which is still not the
+ best, but at least it works.
+ At one point, I ran across a strange problem: Generating pairs of values, I
kept getting the same pairs! There was something wrong with my PRNG. It turns
+ out that each number easily predicts the next number, until it hits the
modulus. Therefore, I increased a and c so that it hit the modulus almost every
time,
+ while still conforming to the required conditions.
+ Another problem was more frustrating but easier to solve once I found it: The
values kept incrementing steadily instead of being random! I spent a long
+ time puzzling over this before I realized that changing the multiplier wasn't
having any effect. I investigated, and found a missing $.
+ The last problem I encountered was a bug in Wesnoth. That bug is that
variables remain in existence and retain their values between multiplayer
games. I
+ circumvented this by clearing all my variables at the start of the game.
+
+ Throughout most of this, I had a bugtester on the multiplayer server called
Jammet. I thank you, Jammet, for your patience while I fixed incomprehensible
+ bug after incomprehensible bug. Your help was very helpful.
+
+
+ [1] there is also a bug in multiplication; apperently floating-point
multiplication and subsequently casting floats to ints throws off their values
on some
+ operating systems.
+
||See Also||
* UserForum
- [Wesnoth-wiki-changes] PseudoRandomNumberGeneration, wiki, 2004/11/13
- [Wesnoth-wiki-changes] PseudoRandomNumberGeneration, wiki, 2004/11/13
- [Wesnoth-wiki-changes] PseudoRandomNumberGeneration, wiki, 2004/11/13
- [Wesnoth-wiki-changes] PseudoRandomNumberGeneration, wiki, 2004/11/13
- [Wesnoth-wiki-changes] PseudoRandomNumberGeneration, wiki, 2004/11/13
- [Wesnoth-wiki-changes] PseudoRandomNumberGeneration, wiki, 2004/11/13
- [Wesnoth-wiki-changes] PseudoRandomNumberGeneration, wiki, 2004/11/14
- [Wesnoth-wiki-changes] PseudoRandomNumberGeneration,
wiki <=
- [Wesnoth-wiki-changes] PseudoRandomNumberGeneration, wiki, 2004/11/14
- [Wesnoth-wiki-changes] PseudoRandomNumberGeneration, wiki, 2004/11/14
- [Wesnoth-wiki-changes] PseudoRandomNumberGeneration, wiki, 2004/11/14
- [Wesnoth-wiki-changes] PseudoRandomNumberGeneration, wiki, 2004/11/14
- [Wesnoth-wiki-changes] PseudoRandomNumberGeneration, wiki, 2004/11/14
- [Wesnoth-wiki-changes] PseudoRandomNumberGeneration, wiki, 2004/11/15
- [Wesnoth-wiki-changes] PseudoRandomNumberGeneration, wiki, 2004/11/15
- [Wesnoth-wiki-changes] PseudoRandomNumberGeneration, wiki, 2004/11/15
- [Wesnoth-wiki-changes] PseudoRandomNumberGeneration, wiki, 2004/11/16
- [Wesnoth-wiki-changes] PseudoRandomNumberGeneration, wiki, 2004/11/16