Hutch,
I have several questions about "shuffle_array proc" you described in the old UK forum. Note that this method is the method I have used since days of yore.
The problem I see is that at the end, there are only two locations available (all of the others have been randomized). The calculated random number can only be 0 or 1, meaning that you will replace the incrementing location with itself (if the random number is 0), or with the end number (if the random number is 1). Now if the last location has never been selected in the prior randomizations, then, at most, the last number can only move is 0 or 1 locations.
Would it be better to make a second pass starting at the opposite end from the initial pass to further disperse the end locations?
Second question. Should the incrementing location ever be allowed to be replaced with itself (if the random number is 0)? Or should the the first possible replacement loocation always be the location just past the incrementing location? Note that in a completely random world, the result COULD be the starting set.
Dave.
Dave,
This is the shuffle algo in the current version of MASM32.
; ¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤
shuffle_array proc arr:DWORD,cnt:DWORD
LOCAL lcnt :DWORD
mov eax, cnt ; copy cnt to lcnt
mov lcnt, eax
push ebx
push esi
push edi
mov esi, arr
mov edi, arr
xor ebx, ebx
@@:
invoke nrandom, cnt ; get the random number within "cnt" range
mov ecx, [esi+ebx*4] ; get the incremental pointer
mov edx, [edi+eax*4] ; get the random pointer
mov [esi+ebx*4], edx ; write random pointer back to incremental location
mov [edi+eax*4], ecx ; write incremental pointer back to random location
add ebx, 1 ; increment the original pointer
sub lcnt, 1 ; decrement the loop counter
jnz @B
pop edi
pop esi
pop ebx
ret
shuffle_array endp
; ¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤
I think you have misunderstood the algo, it uses a library routine that provides random numbers within a user specified range. The basic algo is an old card shuffling one that has been around forever and part of its design IS to select the swap pair randomly and NOT interfere with the random pointer.
You test the result with an app like ENT to see what the distribution is like. To do this you use an ordered array, (1,2,3,4,5,6,7,8 etc...) then randomise it then test it.
Hutch,
As far as I can see, this is the same as the old version, no problems there. I have been using a similar procedure for years.
Do you have a link for ENT? Couldn't find anything on Google for Ent or Entropy. I would be interested in checking how random my RNG really is.
Dave.
The thing to note is that the final element may have already been swapped multiple times with previous elements, so it's not necessarily the same as the original final element - so it's not necessary to force it to be swapped afterward.
Also, ENT: http://www.fourmilab.ch/random/ (http://www.fourmilab.ch/random/)
Tedd,
Thank you for the link. I will see what kind of output ENT produces and test my RNG with multiple seeds and many iterations against a 256 element array, and then test nrandom with the same seeds and iterations and array.
It is interesting that neither Google nor Wiki came up with that link. With this post (as much as Google is data mining these forums), it will now probably show up.
Dave.