Random numbers multiples of 4...

[felipe]

Hello everyone, i have a question and maybe you can help me  . I'm working in a new game (very simple, please be patience to me  :redface:), that i will upload here soon (hopefully before this weekend). Now, i need to generate random numbers between a little range (let's say 0-36). I need that the numbers don't repeat and that they must be multiples of 4.
I know i can use the masm lib to generate pseudo random numbers between a range. And i can make a loop to get a number that is not repeated and i even can check in that loop that the numbers generated are multiple of 4...
My question is if you know of an algorithm or function (maybe in the masm lib that i haven't see?) that generates this random numbers beetwen a range and that the numbers are multiple of 4 (doesn't matter if the numbers repeat, that's not so terrible i guess). I ask because i think it will be better such algorithm (if exist) than a loop , which probably, it will take more time of execution.

Ok, thanks for your help. Bye all.  :icon14:

[LordAdef]

Hi Felipe!

First of all, am looking forward for your next game.

I'm not the best one to help you out. But I recently needed to use random numbers in my own game. In my case, it didn't matter that much witch numbers or how random they were.

But I was concerned about the speed factor so I decided to pre computer  a series of random numbers into a LUT. In my case the LUT was perfect, so I pre-computing the numbers was my solution.

[hutch--]

felipe,

Would this work ? Make a list of the numbers in the range you want that are intervals of 4 then shuffle them like a card game does. No duplicates and randomised order.

Its in the example code.

; ¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤

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

; ¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤

[aw27]

Select a range (example 0-36), divide the range by 4 (0-9), get random integer number, multiply the number by 4 (shift left by 2).

[jj2007]

  Dim MyInt() As DWORD          ; create a DWORD array
  Print CrLf$, "Unordered: "
  xor ecx, ecx
  .Repeat
        Rand(0, Range/4+1, MyInt(ecx), unique)      ; assign a unique value between 0 and 9
        shl MyInt(ecx), 2                           ; expand to 0 ... 36
        Print Str$(MyInt(ecx)), " "
        inc ecx
  .Until ecx>Range/4

  ArraySort MyInt()             ; sort values ascending

  xor ecx, ecx
  .Repeat
        Print Str$("\n%i\t", ecx*4), Str$(MyInt(ecx))
        inc ecx
  .Until ecx>=MyInt(?)          ; loop until #elements reached
EndOfCode

Output:

Code Select Expand

Unordered: 16 0 4 32 24 8 28 20 12 36
0       0
4       4
8       8
12      12
16      16
20      20
24      24
28      28
32      32
36      36

I have added Hutch's code to the attached project, but you will need to a) add the code for the source array and b) test if it yields unique results (which is not trivial and not easy to detect, given the small number, see also this thread)

Anyway, here is an attempt to get Hutch's code to work, but unfortunately it produces always the same numbers, probably I misinterpret the documentation about nrandom_seed:

Code Select Expand

Range=36
.data
nrandom_seed dd ?
srcdest dd 0, 4, 8, 12, 16, 20, 24, 28, 32, 36 ; source and destination for shuffle_array
.code
  Init
if 0 ; from the docs:
The seed for the random algorithm is set as a variable of GLOBAL scope in a seperate procedure atached to the library module.
The variable is nrandom_seed and this variable should be set with a DWORD size number prior to the use of this algorithm.
endif
  mov nrandom_seed, rv(GetTickCount)
  invoke shuffle_array, addr srcdest, Range/4
  For_ ecx=0 To Range/4-1
mov eax, srcdest[4*ecx]
Print Str$(eax), " "
  Next

[aw27]

JJ,
I noticed you used my simple idea without a single reference in your pseudo ASM code.
Sure, it is simple but you had not figured it out otherwise you would have rushed with the pseudo ASM sample within 5 minutes as you always do.

[jj2007]

Oh José, my dear... yes, your idea is simple. Actually, it's trivial. What is not trivial is making sure that the numbers are unique.

[daydreamer]

check the archive, I Think Mark Larsson made a special Mersienne twister that uses SIMD to produce several random numbers at once
I mostly have experience of simplest random generators for perlin noise, but I Think they are too repetive for your use
you use some big constant like all digits from pi or sqrt2 in an integer+ Another integer constant
and all is required is one ADD and one MUL

you can use AND 9 and SHL 2 to get your random number

I Think Hutch has a good solution
I also recommend lot of Reading in old archive for newer members,and searching

[jj2007]

Mersienne twister

Check http://www.cacert.at/cgi-bin/rngresults
Search Mersenne inside the page (there is also a MasmBasic entry). There are over 20 entries for Mersenne, and some look really awful, quality-wise.

I Think Hutch has a good solution

Indeed, for this specific problem it's a very good one. But I can't get random_seed to work :(

[aw27]

My esteemed friend JJ,
"What is not trivial is making sure that the numbers are unique."
That is also trivial. What do you do when you have some errands to do and don't want to perform them in any particular order?
You make a list of them:
1- Buy newspaper
2- Talk with Joe
3- Take car to petrol station
4- Give a bath to dog
5, 6... etc

Then you choose a random task, using for example Hutch's random number generator. When the task is complete you tick it on the list to mark as completed.
Then you reduce the count of tasks by one, and choose a random from the new count of tasks. Counting from the beginning of the list you tick the task in the position that corresponds to the obtained number, skipping tasks already completed. Repeat until you have no more tasks.
I am sure you can do it in pseudo ASM in 5 minutes.

Anyway, here is an attempt to get Hutch's code to work, but unfortunately it produces always the same numbers,

But you know the boss is always right even when you don't understand what he says.  :t

[jj2007]

I am sure you can do it in pseudo ASM in 5 minutes.

It's already implemented as Rand(lowest, highest, pInteger, unique). And it's not as trivial as you describe it.
Btw every source code that assembles with MASM is by definition real ASM. I wouldn't call you a pseudo troll, for example ;)

[aw27]

Btw every source code that assembles with MASM is by definition real ASM

In your mind only, please check in Wikipedia what is assembly language because you don't appear to know:
https://en.wikipedia.org/wiki/Assembly_language

I wouldn't call you a pseudo troll, for example

Think a bit and you will conclude that you are the real troll here, using an Assembly Language forum to promote ad nauseam something that only you and a pair of others use.

[jj2007]

Think a bit and you will conclude that you are the real troll here, using an Assembly Language forum to promote ad nauseam something that only you and a pair of others use.

I show what the "M" in MASM stands for, and demonstrate that many things can be done much easier (and faster) in assembler than, for example, in C/C++. You are not obliged to use the MasmBasic library. It is based on hard work, many algos have been developed over years in the Lab by a dozen or more distinguished members of this forum. That is not your cup of tea, I know - you are very good at using that other library called "WinAPI". You are also good at insulting members and poisoning the atmosphere here, not only with me, although you seem to like me in particular - I feel honoured

For those interested in the topic:

- MasmBasic Rand(... unique) ensures that the numbers are not repeated (under the hood is roughly the mechanism that José describes above);

- Hutch's shuffle_array produces also unique numbers, with a small caveat: It may happen that a slot in the array doesn't get touched at all, because the random generator produces twice the same number; the risk is low and can be further lowered by doing more shuffling than necessary, but the standard tests of randomness would probably spot the problem.

[aw27]

many things can be done much easier (and faster) in assembler than, for example, in C/C++

You can't show anything, your library is bloated and not optimized. C/C++ will beat it in speed and size hands down.

You are also good at insulting members and poisoning the atmosphere here, not only with me, although you seem to like me in particular - I feel honoured

I know the old tactic of trying to recruit when we feel alone and without arguments.
My "arrogant" tone is typical in most forums, new members expect it from veterans.
But how many new members stop coming here after having been exposed to your absurd theories on what  "M"ASM is. This is the real problem.

[jj2007]

your library is bloated and not optimized. C/C++ will beat it in speed and size hands down.

You have no idea what you are talking about. Take it easy, José - perhaps you should dedicate more time to your company.