Author |
Topic: Fast PRNG (suitable for games + demos) (Read 392 times) |
|
David Williams
Developer
member is offline
meh
Gender: 
Posts: 452
|
 |
Re: Fast PRNG (suitable for games + demos)
« Reply #10 on: Apr 8th, 2010, 7:32pm » |
|
on Apr 7th, 2010, 10:18pm, Richard Russell wrote:| If all you want is a fast binary decision maker I reckon I could write one significantly faster than either FastRnd or Rnd. |
|
Thanks, that would be interesting to see.
on Apr 7th, 2010, 10:18pm, Richard Russell wrote:| What minimum sequence length do you require? |
|
If for use with gaming (which is what I'd be inclined to use it for), wouldn't a sequence length in the range 2^16 to 2^32 suffice?
David.
|
|
 Logged
|
|
|
|
admin
Administrator
member is offline
Posts: 1145
|
|
Re: Fast PRNG (suitable for games + demos)
« Reply #11 on: Apr 8th, 2010, 11:05pm » |
|
on Apr 8th, 2010, 7:32pm, David Williams wrote:| Thanks, that would be interesting to see. |
|
It may be possible to do better than this, but as a naive first attempt:
Code: mov eax,[esp]
mov ebx,eax
shr ebx,28
adc eax,eax
shr ebx,2
and ebx,1
xor eax,ebx
mov [esp],eax
and eax,1
ret
This returns 0 or 1 on a pseudo-random basis, with a sequence length of 2^31-1. Here the 'state' is stored on the stack, but of course could be anywhere.
Richard.
|
| « Last Edit: Apr 9th, 2010, 02:50am by admin » |
Logged
|
|
|
|
admin
Administrator
member is offline
Posts: 1145
|
|
Re: Fast PRNG (suitable for games + demos)
« Reply #12 on: Apr 9th, 2010, 02:56am » |
|
Further, if you're happy to test the sign of the result as your 'binary decision' then you can eliminate the and eax,1 (effectively you're testing the MSB rather than the LSB):
Code: mov eax,[esp]
mov ebx,eax
shr ebx,28
adc eax,eax
shr ebx,2
and ebx,1
xor eax,ebx
mov [esp],eax
ret
This returns >0 or <0 on a pseudo-random basis, with a sequence length of 2^31-1.
Richard.
|
| « Last Edit: Apr 9th, 2010, 03:03am by admin » |
Logged
|
|
|
|
David Williams
Developer
member is offline
meh
Gender:
Posts: 452
|
|
Re: Fast PRNG (suitable for games + demos)
« Reply #13 on: Apr 9th, 2010, 7:00pm » |
|
on Apr 8th, 2010, 11:05pm, Richard Russell wrote:It may be possible to do better than this, but as a naive first attempt:
Code: mov eax,[esp]
mov ebx,eax
shr ebx,28
adc eax,eax
shr ebx,2
and ebx,1
xor eax,ebx
mov [esp],eax
and eax,1
ret
This returns 0 or 1 on a pseudo-random basis, ... |
|
Thanks very much for that bit of code (which I haven't yet tested but I feel certain will work just fine and is a keeper!).
I'm just trying to figure out how I might turn a pseudo-random 0 or 1 into a random sign (-1 or +1) in an efficient way without resorting to a CMP (or TST) + jump instruction.
David.
|
|
Logged
|
|
|
|
David Williams
Developer
member is offline
meh
Gender:
Posts: 452
|
|
Re: Fast PRNG (suitable for games + demos)
« Reply #14 on: Aug 20th, 2014, 03:09am » |
|
For a current project, I needed fast (but not 'high quality') generation of pseudo-random floats between 0.0 and 1.0. I'm sharing this code here in case it may possibly be of some interest to others.
David.
Code:
REM Fast -- but not high quality -- PRNG (Pseudo-Random Number Generator)
REM Suited to certain game applications, but NOT statistical simulations.
REM It is NOT intended to replace BB4W's RND function (that would be silly),
REM but it is meant to be called from other assembly language routines.
REM Returns a 64-bit float between 0.0 and 1.0 (exclusive, probably!)
REM
REM Calling this RNG from BASIC is slower than simply using RND(1)
REM (which also returns values in the range 0 to 1)
REM
REM Thanks to George Marsaglia for his 'congruent RNG' on which this code is based:
REM
REM x = 69069*x + 362437
REM
REM Obscenely simple, isn't it?
*FLOAT 64
MODE 8 : OFF
DIM code% 2048+128
FOR I% = 0 TO 2 STEP 2
P% = code%
[OPT I%
.rand
sub esp, 12
xor edx, edx
imul eax, DWORD [seed], 69069
mov DWORD [esp+4], edx
add eax, 362437
mov DWORD [esp], eax
fild QWORD [esp]
fmul QWORD [const]
mov DWORD [seed], eax
mov eax, DWORD [esp+16]
fstp QWORD [eax]
add esp, 12
ret 4
;
; aligned 2Kb code/data separation
;
.gap% : ] : P%+=2048 : P%=(P%+15) AND -16 : [OPT I%
.const dd 1048576 : dd 1039138816 ; 64-bit double representation of 1/(2^32 - 1)
.seed dd 1234567897 ; initial seed value
]
NEXT I%
N% = ^n#
F% = rand
FOR I% = 1 TO 1000000
SYSF%,N% : X%=1280*n#
SYSF%,N% : Y%=1024*n#
PLOTX%,Y%
NEXT
CLS
FOR I% = 1 TO 1000000
SYSF%,N% : X%=1280*n#
SYSF%,N% : Y%=1024*n#
SYSF%,N% : GCOL 16*n#
PLOTX%,Y%
NEXT
|
|
|
|
|
