Well, heres another little tid-bit i hacked out :)
I remember a while back someone was looking for such and i happened to need one, so here is my code for a 31 bit random number generator.
The mehtod is the 'Park, Miller generator' (taken from my statistics text. I followed it to a 'T' and it is designed for numbers up to 7FFFFFF hex.
Anywho, here it is
RAND32 MACRO base:REQ
; Random number generator based on the Real time clock
; and the Park, Miller random number algorithm
;
; Coded by NaN for WIN32ASM
; May 5, 2001
; rev 2.
push ecx
push edx
ifndef __RAND_BY_NAN__
__RAND_BY_NAN__ equ 1
.data?
NaNRand dd ?
.code
db 0fh,31h
shr eax, 2
add eax, 1
mov NaNRand, eax
endif
mov eax, NaNRand
mov edx,0
mov ecx, 127773 ;q
div ecx ; eax == floor( seed / q)
; edx == remainder
SWAP eax, edx
push edx
mov ecx, 16807
mul ecx ; eax = mul of remainder * a
pop edx ; edx == floor of seed/q
SWAP eax, edx
push edx
mov ecx, 2836
mul ecx
pop edx ; edx == mull of rem * a
; eax == mull of seed/q * r
sub edx, eax
mov eax, edx
mov NaNRand, eax ; save next seed
mov ecx, base
mov edx, 0
div ecx
mov eax, edx
pop edx
pop ecx
ENDM
Very nice work NaN :).
Thanks for this snippet... :)
I have a question.
What is the SWAP function you used ?
When i compile your macro, i have errors about this line.
When i delete these lines, this works well (but i think it hurts the randomness).
I think that there's no instruction or function named like that. Didn't you forget to give a little macro/proc with the main one ?
Thank you very much.
Doh!!!!!!
Sorry, i use alot of macros :)
Here it is:
SWAP MACRO M1:REQ, M2:REQ
xor M1, M2
xor M2, M1
xor M1, M2
ENDM
No problem :)
Thank for the macro :)
I tested your RAND32 macro (without the SWAP macro) to compute number between 0->550
I made a little program to test the randomness of it (to know after how many loops the generated number will be the same as the "original")
I generated 10 numbers, and did an average value.
1°)333
2°)153
3°)172
4°)16
5°)814
6°)595
7°)1815
8°)501
9°)495
10°)494
Average : 538,8 :)
Not bad :).
Now you gave me the swap macro, i retested the rand32 with it :)
1°)515
2°)1002
3°)759
4°)242
5°)3157
6°)159
7°)160
8°)27
9°)576
10°)292
Average : 688.9 :)
It's far better :)
I know that kind of tests are not the best to test the randomness of that kind of algos... but it stills an easy way to know if the algo is good enough to use it or not :) : and, amha, it's good :).
Wa can see very small repetitions values sometimes :(
like 16 and 27...
Does someone know why ?
A last question, NaN : What's this please ? db 0fh,31h
INT ? Something else ?
Just curiosity :).
Thank you again for this cool macro :).
I personally tested it with DirectDraw. I had it plot random pixels on a 640 x 480 surface (with 256 random colors). If the generator is crap, you will see very distinct patterns or lines, if not, you will get a gray blob that looks kinda shifty at random. The one i posted is just that, and its moderately fast. Definitely needs work to speed it up (not my forte tho).
The "db 0fh,31h" is a special code to retrieve the real time clock in edx:eax. I use it to randomly form the initial seed, such that no two times will have the same intervals unless eax == eax on two separate instances of you program (possible, but unlikely (1 in 2^32 chance).
I devised another random generator that makes 'ok' blobs, it was to try and make it faster. Here it is, if you want to to more tests on it:
RAND MACRO base:REQ
; Fast Random number generator base on SHIFT->XOR
;
; Coded by NaN for WIN32ASM
; May 5, 2001
ifndef __FRAND_BY_NAN
__FRAND_BY_NAN equ 1
.data?
FRand dd ?
.code
db 0fh,31h
shl eax, 1
mov FRand, eax
endif
mov eax, FRand
rol eax, 11 ; Play with this for effectivenes (7-13 is best i find)
xor eax, FRand
mov FRand, eax
mov ecx, base
mov edx, 0
div ecx
mov eax, edx
ENDM
Many thanks for your explainations :)
I recommend you to post this macro to the Algorithm forum... maybe The Svin (an optimizatio guru) will optimize it :).
Thank again for your great macro and happy coding :).
Well done NaN, it's nice to have a good random number generator. Btw, you can use RDTSC instead of the hexadecimal representation (0F 31) of this opcode. Masm knows this opcode and it's easier to see what it means than db 0Fh, 31h.
Thomas
Thanx, im glad people like it :)
As for the post, ya, i kinda realized it after i posted that it would be better suited for the Algorithms section, my Error. Perhaps one of the Moderators would be so kind to redirect the post to Algorithms.
NaN