NaN, I think Sliver was implying: If we are trying to produce random numbers, then what do we care about EDX being cleared. I can think of two reasons.

1. DIV overflow - if the number is greaterthan 32 bits then the instruction produces a Divide Error exception.

2. Predictablity - yes, we really do want this in a psuedo random number generator. The same seed with the same base will produce the same number. The only example that comes to mind right now is fractal/procedural texture generation - if your generating frames to an animation then you don't want the texture changing randomly from frame to frame. Random and psuedo are needed (truely random data would be worthless - as it should be, IMO :)).
Posted on 2002-03-31 14:55:52 by bitRAKE
Using -any- of these methods, I seem to get the same number over and over. Perhpas I am invoking GetTickCount the wrong way? Does someone have an example of how to properly call GetTickCount for these random numbers generators that are using it? :confused:

Many thanks!
Posted on 2002-06-13 18:00:08 by The Beginner
GetTickCount, is used to set the seed just once at the start of your program. Then repeated calls are made to the random number algo.
Posted on 2002-06-13 18:11:29 by bitRAKE
I guess my problem is getting the return value of GetTickCount in to the random seed. I am kind of new of this, so please forgive my ignorance. And then once I get the random number out of it all, I need to extract it.

I thought I had it from an old example I had used once in a delphi app, but that is long gone.

And, please, forgive me... I am trying to graduate from years of HLL programming. o.0
Posted on 2002-06-13 20:34:11 by The Beginner
I just pulled this out of my head, but maybe it'll help...
invoke GetTickCount

invoke nseed, eax


; random numbers will be beteen 0 and 255
YouWantNumbersLessThan EQU 256

YourLoop:
invoke nrandom, YouWantNumbersLessThan

; use random number in EAX

dec count
jne YourLoop
...this uses the PROCs from NaN's code above. Let me know how it goes, post some code, or try to explain the situation in detail. I can read most any programming language - post in what is comfortable to you.
Posted on 2002-06-13 22:05:02 by bitRAKE
Hi guys. I'll start with a little background info on my algo.

In the early years of digital electronics it was very hard to make good random generators. Doing it in software was no option, as software hardly existed. Some of the earliest computers were reprogrammed by rewiring, if at all...

But someone came up with the bright idea of hooking up shift registers with a feedback path, such that the feedback forced the registers into a pseudorandom pattern cycle.

Today that method has largely been abandoned, as it was considered to suffer from several drawbacks. Mainly they would only produce a single new bit per shift cycle, and the other bits would simply be shifted copies of old bits.

However, many failed to realize that these drawbacks can be removed when such a pseudorandom sequence is implemented in software. I did this several years ago to implement a 32 bit rng with 31 bit randomicity for M68K processors. Now I have translated that rng into x86 code, and here it is:


rand_32 MACRO ChosenSeed
mov eax,ChosenSeed ;seed = last value (bit 31 irrelevant)
;
;------- Start of phase 1, each phase to generate 16 new random bits
;
mov ecx,eax ;copy eax to ecx (orig bit 31 won't be used though)
shr ecx,3 ;shift ecx by 3 bits for 31 bit pseudorandomicity
xor ax,cx ;generate 16 new pseudorandom top bits
ror eax,16 ;align 16 new bits correctly
shl ax,1 ;align 15 old bits, bit 0=garbage, losing original bit 31
ror eax,1 ;Adjust 31-bit pseudorandom shifter, bit 31 = 0
;
;------- Phase 1 is complete. 16 new (of 31 present) random bits generated
;
mov ecx,eax ;copy eax to ecx (dummy bit 31 is replaced later)
shr ecx,3 ;shift ecx by 3 bits for 31 bit pseudorandomicity
xor ax,cx ;generate 16 new pseudorandom top bits
ror eax,16 ;align 16 new bits correctly
bt cx,12 ;CF = lowest new bit generated in phase 1
rcl ax,1 ;align 16 old bits, losing dummy bit 31
ror eax,1 ;Adjust 31-bit pseudorandom shifter (bit 31 also random)
;
;------- Phase 2 is complete, 32 new random bits generated, replacing all old
;
mov ChosenSeed,eax ;store seed (bit 31 irrelevant)
ENDM
;
;NB: In the above "irrelevant" means that bit 31 has no effect on future
; results from the generator, although this bit too is pseudorandom.
; Note also that initial values of 0 or 0x80000000 for seeds are illegal,
; as 31 zeroes is not included in the sequence of (2^31 - 1) values.


As you can see this method uses no multiplication or division, but only bit shifts and byte swaps (it's a pity there's no word swap opcode though). This should make it faster than most competing algorithms, though I haven't tested that yet.

PS: I just edited the post to remove a 'typo' in the macro argument, and include bitRAKE's 'almost word swap' in phase 1
PPS: Edited it again to reorder code like bitRAKE said recently to allow fast swapping in both phases.
Posted on 2002-06-14 00:26:15 by RAdlanor
;ABCD;

;ABDC; xchg al,ah ;\
;CDBA; bswap eax ; > align 16 new bits correctly
;CDAB; xchg al,ah ;/

ror eax,16
Posted on 2002-06-14 00:39:42 by bitRAKE
Thanks bitRAKE, but that won't quite cut it.

I did edit it into phase 1, but it won't work in phase 2, because that would clobber the carry flag needed to get 32 bits. That's an option only if you accept having bits 31 and 30 identical, or with another slight change having bit 31 always cleared.

But I want 32 bits, so that's not for me.
Posted on 2002-06-14 02:58:55 by RAdlanor
Move the instructions around. :)
rand_32 MACRO Chosen_Seed

mov eax,ChosenSeed
mov ecx,eax
shr eax,3
xor cx,ax
ror ecx,16
shl cx,1
ror ecx,1
mov eax,ecx
shr ecx,3
xor ax,cx
ror eax,16
bt cx,15-3
rcl ax,1
ror eax,1
mov ChosenSeed,eax
ENDM
Posted on 2002-06-14 05:42:40 by bitRAKE
;*****************************************
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
;*****************************************

That is what I am using, from this thread. In the thread (sorry, I forget who posted it at the moment), the poster said all one needs to do is invoke GetTickCount to make the random seed.

I think I am missing something in this because invoking GetTickCount is as far as it seems to work. I pick a min/max number, invoke this PROC, and it gives me the same number over and over.

When the app starts up, I do this:

invoke GetTickCount

From there, where do I go? What do I do? As I said, I am new to ASM and I am trying to figure this out if I can. Heh, it took me 3 days (though I did it finally) to figure out how to implement a TimerProc() from an old delphi app in MASM. It works wonderfully and I need this random number to make it work exactly as it does in the delphi application.

But I guess actually GETTING the value returned from GetTickCount to go to RandSeed and finally to getting the random number to go to another global variable called Count is the problem. I know that mov Count, RandomNumberHere will store it in Count for me, correct? If not, then I am a little further back than I thought I was.

Thanks bitRAKE, all of this organized chaos is actually helping someone learn quite quickly. And as far as posting in any language... this is in delphi (object pascal).

function MakeItRandom(Min, Max: Integer): Integer;
begin
Result := Random(Min) + Random(Max)
end;

This gives me a number between my minimum and maximum (which is what I need) selections. That is what attracted me to the MASM code above; the fact I could pick a min/max and have it (in theory) return one for me.:confused:

Thanks again for all the help. I think I am almost going somewhere with this! :grin:
Posted on 2002-06-14 06:52:16 by The Beginner
The Beginner, first the Delphi code should imho be:
function MakeItRandom(Min, Max: Integer): Integer; 

begin
Result := Min + Random(Max - Min)
end;
This is assuming Random(num) returns a value between [0,num) --- which is fairly standard function for Random().

Now for the code your using - something like the following would store the TickCount in the RandSeed.
invoke GetTickCount

invoke RandSeed, eax
Then you would just call the random function when you your random number.
Posted on 2002-06-14 07:20:05 by bitRAKE
Sure, your random function would work as well. But I like the high-end of the min/max more than the low-end, so my method works for me.

I typically never use a zero number for my randoms, because they have no use in what I am trying to do. :)

Now, as far as GetTickCount goes, this works! Heh, I knew it would end up being something simple that I was missing... always the little things. :D

Thanks again, bitRAKE. And in case you are curious as to exactly HOW I was messing this up.. here it is.

invoke GetTickCount
mov RandSeed, GetTickCount

Heh, it made sense to me somehow... just don't ask me why!

But try this in delphi.

Take my function and give it a try, then use yours. Let me know exactly how different they are to you. :D
Posted on 2002-06-14 07:29:26 by The Beginner

Take my function and give it a try, then use yours. Let me know exactly how different they are to you. :D
Your function doesn't work for :)
Your function is [0,max+min]! :)
Posted on 2002-06-14 08:09:22 by bitRAKE
Of course mine works! Now ya made me drag out my Delphi and make an example app with both methods. Yours (bitRAKEMethod) and mine (MakeItRandom).

Check it out. Includes the rather dull (2 minutes, whew) source code with no comments.

This was done in Delphi6 Enterprise.. in case anyone want to recompile it.
Posted on 2002-06-14 08:34:59 by The Beginner
My first try


min = 45
max = 60

your result = 93
93 is not between [45,60]! :tongue:
Posted on 2002-06-14 08:44:19 by bitRAKE
Hehe, my findings using the bitRAKE method(tm):

Min, 75
Max, 100

Result0 = 75
Result1 = 99
Result2 = 98
Result3 = 99
Result4 = 100
Result5 = 90
Result6 = 89
Result7 = 91
Result8 = 99
Result9 = 101 <----

I know my method has a chance at returning higher numbers than we want (view the README), but it is more consistent in actually being random and it does not always return higher numbers than we want. I could make it so that it never returns a higher number than the max, but that was a quick and dirty example.

I love these discussions... makes coding more interesting. =P
Posted on 2002-06-14 08:53:40 by The Beginner
How is the output to Delphi's Random() defined? I thought the
goal was a random number between - my algo does that. :)
Posted on 2002-06-14 09:00:44 by bitRAKE
The Random() method in Delphi is based, sadly, on CPU cycles. This limits you somewhat unless you can work around it, which we have both kind of done, to a point.

Your method -does- make a random between A and B, but it also tends to stay in the same range as I have shown above. It also, one time, returned 101 as a value. It does that less often than mine, but it does it none-the-less. ;)

So, yes, the goal was a number between A and B, but it had to have a much better randomness to it. :)

Now, back to forcing myself to learn how to work with MASM! I think I am hooked so far as I think about it constantly.. even at work. *sigh*
Posted on 2002-06-14 09:07:26 by The Beginner

Your method -does- make a random between A and B, but it also tends to stay in the same range as I have shown above. It also, one time, returned 101 as a value. It does that less often than mine, but it does it none-the-less. ;)
It is hard to judge randomness on such a small range of values. Delphi Random(num) might return [1,num]. In that case the algo should be:
function MakeItRandom(Min, Max: Integer): Integer; 

begin
Result := Min + Random(Max - Min + 1) - 1
end;
Yeah, asm is great - I think about it all the time myself...
Posted on 2002-06-14 09:18:37 by bitRAKE
bitRAKE,

about the reordering of code in my rand_32 macro:

You're absolutely right, and I'll edit the original post again, so that only the optimized version is available. I don't know how I could miss that reordering option myself, except that I must have been tired.

Anyway, summing it up, this has shortened the code by four instructions.
This should make it an even better choice for speed freaks.
:)
Posted on 2002-06-14 12:09:32 by RAdlanor