Hi, Frank
Frank Heckenbach wrote:
Toby Ewing wrote:
I've been working with the Mersenne Twister random number generator for a while. I translated it from the original C to Pascal several years ago, and the GPC team incorporated it into the GPC unit. But since then the original authors have found and fixed a bug in their initilization procedures, and other users have suggested various speedups.
I've now updated my original translation, validated it against the authors' test output, performed some other minor tests, and done what small optimizations I know how to do. Source for the unit and a test program are appended below.
I've briefly looked at your code, and it seems there are some off-by-one errors, e.g.:
for kk := mtN-mtM to mtN-1 do begin
(where the C version says `<N-1'). I think there are more.
There are indeed several such differences, but they're not errors as such. I used the Pascal [1..n] convention, rather than staying with the C [0..n-1] convention. The bottom line is that the output is identical, as tested against several test output files on the Mersenne Twister homepage.
Also, if you'd like to have this code included with GPC, it would be good to use the same coding style and interfaces (including function names such as `Default_RandInt' which are called through pointers in the RTS). I don't have the time to do the reformatting myself now.
The basics - initialization from a given random number seed, and the "rand" that returns a real in [0..1) - are currently part of the gpc.pas unit. I'd be happy to have the current code included - that was my purpose in submitting it - but I don't understand the coding and interface conventions you're using. If you can point me to some clear guidelines, I could give it a shot.
The code that I started with, the C++ abyss from which I rescued some civilized Pascal, claims to be faster than what I wrote. It uses the C and C++ directives "inline" and "register", and some arcane C constructions that are better avoided in clear code. In addition, there is assembly code optimized for pentia with MMX. I decided to make my Pascal code platform- and dialect-independent, but there is (theoretically) yet faster code out there, and if you'd rather link that into the GPC unit, that's fine too.
It would also make it easier for me to see what's actually changed. I remember having updated the initalization, apparently corresponding to the "2002/01/09" changes. I don't know if anything significant was changed after that.
I didn't realize that you'd changed the initialization already - that's great!
The other changes are 1) I split the basic number generator into two parts - one that is executed for each number, the other of which is executed only once every 624 calls. In my tests, this resulted in a 20+% speedup, presumably because the memory overhead for the more frequent function call is greatly reduced. 2) I added code for generating several commonly desired variants: reals in [0..1), reals in [0..1], reals in (0..1], doubles with random values throughout their full 53-bit (IEEE) length, numbers drawn from a normal distribution...
regards, Toby