News:

Masm32 SDK description, downloads and other helpful links
Message to All Guests
NB: Posting URL's See here: Posted URL Change

Main Menu

Random numbers multiples of 4...

Started by felipe, March 28, 2018, 03:48:07 PM

Previous topic - Next topic

felipe

Hello everyone, i have a question and maybe you can help me  :bgrin:. 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: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: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
my none asm creations
https://masm32.com/board/index.php?topic=6937.msg74303#msg74303
I am an Invoker
"An Invoker is a mage who specializes in the manipulation of raw and elemental energies."
Like SIMD coding

jj2007

Quote from: daydreamer on March 28, 2018, 07:02:32 PMMersienne 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.

QuoteI 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.

Quote
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

Quote from: aw27 on March 28, 2018, 07:36:11 PMI 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

Quote
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

Quote
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

Quote from: aw27 on March 28, 2018, 08:57:55 PMThink 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 :badgrin:

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

Quote
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.

Quote
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

Quote from: aw27 on March 28, 2018, 10:22:26 PMyour 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.