I liked the simplicity of the random algo that vecna posted so I have played with it for a while to make its distribution less uniform. The form I have it in is suitable for simple stuff like games or in the case of the example, a static star field plotted with random X/Y co-ordinates.

There are far more powerful versions available, Agner Fog's collection are very sophisticated and with a secondary random seeding for the algorithm, they are probably powerful enough to use with encryption but they are a more complex algos that are based on floating point and are probably a bit complex to use for simple tasks.

Any comments or improvements will be welcome, the idea is to retain a simple integer random algorithm.

Regards,

hutch@movsd.com
Posted on 2002-03-29 19:08:42 by hutch--
I like Yawns Random Number Generator.


RandomNumGen PROC min:DWORD, max:DWORD

mov ebx, max
sub ebx, min
inc ebx
xor edx, edx
mov eax, RandSeed
div ebx
add RandSeed, eax
add edx, min
mov eax, edx
ret

RandomNumGen ENDP
All you have to do is call GetTickCount to get the seed and your ready to go. You can even specify a range of values like from 1 to 500... :)
Posted on 2002-03-29 23:00:24 by stryker
Well it *looks* like a good randomizing algo on the surface, but its still quite repetitive.... However, the trade off is speed! Im impressed on the size for what it *can* do.

I took that algo, and placed it in a Direct Draw app with a main section as follows:



RAND32 640
mov lx, eax
RAND32 480
mov ecx, ddsd.lPitch
mul ecx
add eax, lx
mov ly, eax
RAND32 3 ; <<<< COLORS

mov ebx, lpBUF
add ebx, ly
mov [ebx], al


All it does is get 3 random #'s (0-640, 0-480, 0-3).

With your algo, and the colors brought up high (256) it looks exactly like my version based on the Park, Miller random number algorithm (chaotic!).

But when the # is brough down to smaller values, its does become quite repetative! I start to get line patters forming that looks *very* symetrical!

The smaller the #, the worse it gets! And what i mean by patterning is, there is areas that *always* get the same color number, and it happens with constant repitition:
Posted on 2002-03-30 00:17:03 by NaN
Nice! example :alright: I actually use Yawns RNG for my data structures homeworks/projects.

It really bogs down when it comes to smaller range of numbers. I tried to apply it on a slot machine game on of my friends code and yes it becomes repetitive on smaller ranges. But its great on larger ranges and look at the size and less opcodes used, very straightforward too and easy to follow. :grin:
Posted on 2002-03-30 00:26:46 by stryker
Nan,

The test you are using looks interesting, I tested this modified version of the algo that Vecna posted with 3 grey shades with the range sized to the existing window size and after some thousands of iterations, the pattern still looked very RANDOM in its distribution.

The reason why I modified it was to avoid the nearly exact distribution of the different numbers in the range. I would be interested to see what this algo looked like with your test.

Regards,

hutch@movsd.com
Posted on 2002-03-30 00:37:17 by hutch--
Sure thing Hutch...

Here is the Files I used:

The Ex2 is just example 2 (for D Draw piddling)
_Macros_.inc Has the Random # Gen's near the bottom... (and a ton of other crap ?? (( I rarely use this file anymore))

In Ex2: Near the bottom in "Game Main" i do the work of placing pixels at 'random' :) . The two types are there, but uncomment and re-compile to try the other...

Enjoy.. (sorry, but the code is *real* shoddy ~ wrote the DirectX framework almost a year ago... but this doesnt matter, cause the random gen macro's are in _Macros_.inc anyways...)

:alright:
NaN
Posted on 2002-03-30 00:49:19 by NaN
I took a screenshot from that one and here's the output. I cut a small portion of the image(the rest are the same as the one here) since I'm running at 1024x768 and the image file is large in dimensions...
Posted on 2002-03-30 00:56:28 by stryker
Looks like a good generator hutch. Easy to remember. But what is the following line included for:
and eax, 0FFFFFFFFh
doesn't that just give back eax...?
Posted on 2002-03-30 02:31:08 by grv575
If you are looking for simple pseudorandom number generators, there's no simpler than the Lehmer algorithm (the linear congruential method):
mov   eax, Seed

mul Value
inc eax
mov Seed, eax
mov ecx, Range
xor edx, edx
div ecx
You initialize Seed with GetTickCount, and that's all!
You must select an initial value for 'Value' according to Knuth rules:
1. not too small or too large compared to 'Range'
2. 1 less decimal digit than 'Range' is a good choice (if 'Range' is a decimal number of 5 digits, 'Value' should have 4 digits)
3. should end with ...n21, where n is even (7621, 2308546021, etc)
Posted on 2002-03-30 03:35:30 by micmic
If anyone cares, here is the Park, Miller Algo:
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
; ( Optomized by bitRake )
;
; May 5, 2001
; rev 2.

; push ecx ; not used
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
else
mov eax, NaNRand
endif

xor edx,edx
push 127773 ;q
div DWORD PTR [esp] ; eax == floor( seed / q)
; edx == remainder
push eax
mov eax, 16807
mul edx ; eax = mul of remainder * a
pop edx ; edx == floor of seed/q

push eax
mov eax, 2836
mul edx
pop edx ; edx == mull of rem * a
; eax == mull of seed/q * r
sub edx, eax
mov eax, edx
mov NaNRand, edx ; save next seed
push base
mov edx, 0
div DWORD PTR [esp]
add esp,8
mov eax, edx
pop edx
; pop ecx
EXITM <eax>
ENDM


This can also be easily cleaned up into a function...

Enjoy..
:alright:
NaN
Posted on 2002-03-30 03:39:31 by NaN
NaN,

The algo looks good, I have been playing with its behaviour in your test bed. Now that you come to mention it :) it would be handy if it WAS converted to a procedure and there was a method of manually setting the seed number.

The algo type I had in mind is one that will produce the same sequence with the same seed.

With a few fiddles the one I posted was OK on small sequrences but its repeat rate was very poor and patterns became visible so it is not powerful enough.

Now that you are a man of leisure, such a contribution to the MASM32 library would be appreciated. :alright:

hutch@movsd.com
Posted on 2002-03-30 05:00:41 by hutch--
Sure, but little lost what you want (maybe its cause i just woke up?).

You want the source for the package? - If so, take it..

You want me to make a function outat it first?

You want the Ex2 program for the package? (Dunno why, its crap code :grin: )

Or all of the above?


Anywho, glad it amuses you :)
:enjoy:
NaN
Posted on 2002-03-30 12:50:29 by NaN
I think hutch-- wants you to write it inside a procedure but don't worry I have it covered. :alright:


NaNPM PROC base:DWORD

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
ELSE
mov eax, NaNRand
ENDIF

xor edx,edx
push 127773
div DWORD PTR [esp]
push eax
mov eax, 16807
mul edx
pop edx
push eax
mov eax, 2836
mul edx
pop edx
sub edx, eax
mov eax, edx
mov NaNRand, edx
push base
mov edx, 0
div DWORD PTR [esp]
add esp,8
mov eax, edx
pop edx
ret

NaNPM ENDP
I just had a quick conversion from your macro to a proc(No Optimizations done). :)
Posted on 2002-03-30 13:04:33 by stryker
Josh,

You are a gentleman. I have changed the algo to the format I was after and plugged it directly into NaN's test piece and its working fine.

NaN,

Have a look at this form and see if you are happy with it, if its OK, I want it for the MASM32 library as it performs well and is easy to use.


; #########################################################################
;
; Park Miller random number algorithm written by Jaymeson Trudgen (NaN).
;
; #########################################################################

nrandom PROC base:DWORD

mov eax, nrandom_seed

xor edx,edx
push 127773
div DWORD PTR [esp]
push eax
mov eax, 16807
mul edx
pop edx
push eax
mov eax, 2836
mul edx
pop edx
sub edx, eax
mov eax, edx
mov nrandom_seed, edx
push base
mov edx, 0
div DWORD PTR [esp]
add esp,8
mov eax, edx

ret

nrandom ENDP

; #########################################################################

nseed proc TheSeed:DWORD

.data
nrandom_seed dd 12345678
.code

mov eax, TheSeed
mov nrandom_seed, eax

ret

nseed endp

; #########################################################################

Regards,

[email]hutch@movsd.com[/email]

Posted on 2002-03-30 16:57:47 by hutch--
nrandom PROC base:DWORD

mov eax, nrandom_seed

xor edx, edx
mov ecx, 127773
div ecx ; seed/127773

mov ecx, eax
mov eax, 16807
mul edx ; 16807 * (seed % 127773)

mov edx, ecx
mov ecx, eax
mov eax, 2836
mul edx

sub ecx, eax
xor edx, edx
mov eax, ecx
mov nrandom_seed, ecx
div base

mov eax, edx
ret
nrandom ENDP
Posted on 2002-03-30 17:55:09 by bitRAKE
Hutch it looks great to me :grin:

However, after doing some more homework on the issue, I strongly think you should use bitRAKE's above version (and give him credit for optomizing it so tightly).

Using the following code as a bench on my AMD 800 (256 Mb Ram), Windows 98 SE:
.586

.model flat,stdcall
option casemap:none
.NOLIST
include \masm32\include\windows.inc
include \masm32\include\masm32.inc
include \masm32\include\kernel32.inc
include \masm32\include\debug.inc
include \masm32\include\user32.inc
includelib \masm32\lib\kernel32.lib
includelib \masm32\lib\user32.lib
includelib \masm32\lib\masm32.lib
includelib \masm32\lib\debug.lib
.list

nrandom PROTO :DWORD
mrandom PROTO :DWORD
nseed PROTO :DWORD

TimeTest_ON macro
db 0fh,31h
push edx ; push high
push eax ; push low
endm

TimeTest_OFF macro
db 0fh,31h
pop ebx ; pop low
pop ecx ; pop hight
sub eax,ebx ; diff low
sbb edx,ecx ; diff high
endm

TLen equ 10

.data

.data?
EFX dd ?
EGX dd ?
Ave dd ?
.code
start:
pusha

PrintText "Warm up -- Shake window setup time error"

invoke nseed, 123456
mov EFX, 10000000
TimeTest_ON
@@:
invoke nrandom, 10
dec EFX
jnz @B
TimeTest_OFF
PrintDec edx
PrintDec eax

mov Ave, 0

PrintText "------------- Previous Version -----------"

mov EGX, 100
ALop:
invoke nseed, 123456
mov EFX, TLen
TimeTest_ON
@@:
invoke nrandom, 10
dec EFX
jnz @B
TimeTest_OFF
add Ave, eax
dec EGX
jnz ALop
xor edx, edx
mov eax, Ave
mov ecx, 1000
div ecx
PrintText " Average Tick Count For 1 Random Number: "
PrintDec eax

mov Ave, 0

PrintText "------------- New Version -----------"

mov EGX, 100
BLop:
invoke nseed, 123456
mov EFX, TLen
TimeTest_ON
@@:
invoke mrandom, 10
dec EFX
jnz @B
TimeTest_OFF
add Ave, eax
dec EGX
jnz BLop
xor edx, edx
mov eax, Ave
mov ecx, 1000
div ecx
PrintText " Average Tick Count For 1 Random Number: "
PrintDec eax


popa
invoke ExitProcess, NULL


The following results occoured (and were also found highly recreatable between separate executions):
Warm up -- Shake window setup time error
edx = 0
eax = 1129853437
------------- Previous Version -----------
Average Tick Count For 1 Random Number:
eax = 107
------------- New Version -----------
Average Tick Count For 1 Random Number:
eax = 98


So he shaved off 9 tick counts, and (63 - 55)= 8 Bytes from the previous version, while keeping the algorithm the same (Tested and showed 10 numbers in the same order from the same seed as my older version). So its just *better* in every direction (good job bitRAKE!).

So i sugest using somthing like this:
;  #########################################################################

;
; Park Miller random number algorithm.
;
; Written by Jaymeson Trudgen (NaN)
; Optimized by bitRAKE (Rickey Bowers Jr.)
;
; Size: 55 Bytes, CPU Time: 98 Ticks
#########################################################################

nrandom PROC base:DWORD

mov eax, nrandom_seed

xor edx, edx
mov ecx, 127773
div ecx
mov ecx, eax
mov eax, 16807
mul edx
mov edx, ecx
mov ecx, eax
mov eax, 2836
mul edx
sub ecx, eax
xor edx, edx
mov eax, ecx
mov nrandom_seed, ecx
div base

mov eax, edx
ret

nrandom ENDP

; #########################################################################

nseed proc TheSeed:DWORD

.data
nrandom_seed dd 12345678
.code

mov eax, TheSeed
mov nrandom_seed, eax

ret

nseed endp

; #########################################################################


:alright:
NaN

PS: Off topic, but i find it amazing a programmer in Astralia can get my name correct (to my surprise), while my school (which i've invested about 20K $ and 4 years of my life) gives me a graduation mug with Jaymeson Trudeau on it! Hehehe, makes me wonder what the Degree will have...
Posted on 2002-03-31 00:59:28 by NaN
Yes,

Optimisation looks good, plugged into the attached example, a rewrite of the last one.

Regards,

hutch@movsd.com
Posted on 2002-03-31 04:02:01 by hutch--
Hehe, i like it ~ its got this star wars thing to it :)

:alright:
NaN
Posted on 2002-03-31 12:42:38 by NaN


sub ecx, eax
xor edx, edx <-- Remove this
mov eax, ecx
mov nrandom_seed, ecx
div base


You really don't need the extra "xor edx, edx" and it will increase the speed of the code (by a tinsy wincy bit)..

Sliver

---EDIT---
actually both of the "xor edx, edx" aren't really used (because the value in them gets trashed anyway)... not sure what purpose they serve... :) Prob. missing something
Posted on 2002-03-31 13:49:29 by Sliver
Its because the way div works.

Here is a description from HelpPC 21:
Unsigned binary division of accumulator by source. If the source
divisor is a byte value then AX is divided by "src" and the quotient
is placed in AL and the remainder in AH. If source operand is a word
value, then DX:AX is divided by "src" and the quotient is stored in AX
and the remainder in DX.


So by extension to 32 bits: EDX:EAX becomes divided when the source is a 32 bit value. To keep the results correct we must zero out any grabage that might be there to start with...

:alright:
NaN
Posted on 2002-03-31 14:32:51 by NaN