Author Topic: random number between 0 and 41  (Read 1221 times)

0 Members and 1 Guest are viewing this topic.

Offline johnlobo

  • CPC464
  • **
  • Posts: 32
  • Country: es
    • JohnLobo at Itch.io
    • Awards
random number between 0 and 41
« on: 12:31, 14 August 21 »
Hi,
I'm generating in assembler a pseudo random number of one byte (0 to 255) , but a need to limit the result to a number between 0 to 41.

Is there an easy way to do this?? I'm trying to avoid to include a routine to calculate the modulus just for this.

Regards.

Offline SpDizzy

  • Supporter
  • CPC664
  • *
  • Posts: 83
  • Country: es
    • Awards
Re: random number between 0 and 41
« Reply #1 on: 13:14, 14 August 21 »
Maybe you can compare with highest value, and substract it if carry (for example)
Code: [Select]
;; assuming 'a' register already has random calculated number

ld b, #42  ;; highest value + 1
cp b
jr c, _returnValue

sub b

_returnValue:
ld l,a
ret
like
0
No reactions

Offline TotO

  • 6128 Plus
  • ******
  • Posts: 4.052
  • Country: fr
    • ?area=showdonations;u=4
    • Awards
Re: random number between 0 and 41
« Reply #2 on: 13:32, 14 August 21 »
Modulo?
like
0
No reactions
"You make one mistake in your life and the internet will never let you live it down" (Keith Goodyer)

Offline johnlobo

  • CPC464
  • **
  • Posts: 32
  • Country: es
    • JohnLobo at Itch.io
    • Awards
Re: random number between 0 and 41
« Reply #3 on: 14:13, 14 August 21 »
Thanks for the answer, but I think that this method only works while the random number is lower than 84, becasue if it's higher than that, when you substract 42 (sub b), you get a number higher than 41... so,  the result it's out of range, isn't it??

Maybe you can compare with highest value, and substract it if carry (for example)
Code: [Select]
;; assuming 'a' register already has random calculated number

ld b, #42  ;; highest value + 1
cp b
jr c, _returnValue

sub b

_returnValue:
ld l,a
ret

Offline Bread80

  • CPC464
  • **
  • Posts: 19
  • Country: england
    • Bread80.com
    • Awards
Re: random number between 0 and 41
« Reply #4 on: 14:31, 14 August 21 »
If you just do a modulo then the result won't be truly random. Since 255 isn't an even multiple of 42 some output values will have a slightly higher probability than others. Ie. 42*6 = 252. So the values 252..255 will modulo to a value of 0..3 (if you repeatedly modulo until in range). Thus 0-3 will have a higher probability of being generated than 4-41.


You can try dividing the initial RNG output, but with an 8-bit RNG the resolution won't be great - you may want to consider using a 16-bit one.


The other option would be to generate another number if the output isn't in range. This obviously carries a time penalty.


The compromise might be to re-run for number >= 252 and modulo any other value.


(All of which depends on your need for randomness and your need for speed).
like
0
No reactions

Offline Cwiiis

  • CPC664
  • ***
  • Posts: 138
  • Country: gb
    • Blog
    • Awards
Re: random number between 0 and 41
« Reply #5 on: 14:51, 14 August 21 »
If you're not too worried about the weighting being uneven, you could discard the top 2 bits (so you end up with a number between 0-63) and take away 42 if it's greater than 42... I suppose you could also use the discarded bits to choose 4 different strata of number to subtract between 21-42 and reduce the impact of the otherwise obvious weighting.
like
0
No reactions

Offline SpDizzy

  • Supporter
  • CPC664
  • *
  • Posts: 83
  • Country: es
    • Awards
Re: random number between 0 and 41
« Reply #6 on: 14:55, 14 August 21 »
Thanks for the answer, but I think that this method only works while the random number is lower than 84, becasue if it's higher than that, when you substract 42 (sub b), you get a number higher than 41... so,  the result it's out of range, isn't it??
Of course, sorry, that's my fault.

Out of modulus, I think as @Bread80 has said, generate another random number if the output is out of range may be a possibility.


Even better, discard top 2 bits as @Cwiiis suggested looks fine to me.
« Last Edit: 17:28, 14 August 21 by SpDizzy »
like
0
No reactions

Offline gerald

  • Supporter
  • 6128 Plus
  • *
  • Posts: 1.581
    • Awards
Re: random number between 0 and 41
« Reply #7 on: 16:36, 14 August 21 »
If you already have a 8x8bit multiplication, just multiply the random number by 42, and keep the MSB of the result.
like
0
No reactions

Offline Animalgril987

  • Supporter
  • CPC6128
  • *
  • Posts: 231
  • Country: gb
    • Awards
Re: random number between 0 and 41
« Reply #8 on: 22:06, 14 August 21 »
SpDizzy almost had it:
Label the "Dec b" as "_loop", and put "jr , _loop" after the "sub b"
Now the routine will loop until the value in a is less than 42.
like
0
No reactions

Offline SpDizzy

  • Supporter
  • CPC664
  • *
  • Posts: 83
  • Country: es
    • Awards
Re: random number between 0 and 41
« Reply #9 on: 22:49, 14 August 21 »
SpDizzy almost had it:
Label the "Dec b" as "_loop", and put "jr , _loop" after the "sub b"
Now the routine will loop until the value in a is less than 42.
Oh my bad, just as simple as that! Time for me to go to bed...


Code: [Select]

;; assuming 'a' register already has random calculated number
ld b, #42  ;; highest value + 1


_loop:
cp b
jr c, _returnValue


sub b
jr _loop


_returnValue:
ld l,a
ret
like
0
No reactions

Offline johnlobo

  • CPC464
  • **
  • Posts: 32
  • Country: es
    • JohnLobo at Itch.io
    • Awards
Re: random number between 0 and 41
« Reply #10 on: 11:18, 15 August 21 »
Yes, now it works.

If I don't find anything more accurate, I'll go with this.
Thank you.

SpDizzy almost had it:
Label the "Dec b" as "_loop", and put "jr , _loop" after the "sub b"
Now the routine will loop until the value in a is less than 42.

Offline johnlobo

  • CPC464
  • **
  • Posts: 32
  • Country: es
    • JohnLobo at Itch.io
    • Awards
Re: random number between 0 and 41
« Reply #11 on: 11:19, 15 August 21 »
Yes I have implemented 8x8 multiplication... I will try this too.
Thank you.

If you already have a 8x8bit multiplication, just multiply the random number by 42, and keep the MSB of the result.

Offline Animalgril987

  • Supporter
  • CPC6128
  • *
  • Posts: 231
  • Country: gb
    • Awards
Re: random number between 0 and 41
« Reply #12 on: 15:53, 15 August 21 »
@SpDizzy
Oh my bad, just as simple as that! Time for me to go to bed...
I have those kind of days too :D
like
0
No reactions

Offline eto

  • Supporter
  • 6128 Plus
  • *
  • Posts: 507
  • Country: de
    • Awards
Re: random number between 0 and 41
« Reply #13 on: 16:36, 16 August 21 »
Would this also work?

Create a random 8 Bit number, get the upper 3 bits 0-7 and the lower 5 bits 0-31, add these values (0-38) and finally add the lowest 2 bits (0-3) of register R. That should give you a number between 0-41.
like
0
No reactions

Offline Animalgril987

  • Supporter
  • CPC6128
  • *
  • Posts: 231
  • Country: gb
    • Awards
Re: random number between 0 and 41
« Reply #14 on: 20:37, 16 August 21 »
@eto: That's an interesting and novel approach :D
It should work ok, and if the OP isn't using R for his random number, it will add an "extra randomness" to the bottom 2 bits.
like
0
No reactions

Offline andycadley

  • Supporter
  • 6128 Plus
  • *
  • Posts: 1.022
    • Awards
Re: random number between 0 and 41
« Reply #15 on: 21:11, 16 August 21 »
Would this also work?

Create a random 8 Bit number, get the upper 3 bits 0-7 and the lower 5 bits 0-31, add these values (0-38) and finally add the lowest 2 bits (0-3) of register R. That should give you a number between 0-41.
It will give you a number in the right range, though I suspect the distribution won't necessarily be very even.
like
0
No reactions

Offline Animalgril987

  • Supporter
  • CPC6128
  • *
  • Posts: 231
  • Country: gb
    • Awards
Re: random number between 0 and 41
« Reply #16 on: 21:34, 16 August 21 »
@andycadley  Real random numbers aren't evenly distributed anyway, just take a look at a lottery draw: there are often "clumps" of numbers at one end or in the middle.  :D
like
0
No reactions

Offline andycadley

  • Supporter
  • 6128 Plus
  • *
  • Posts: 1.022
    • Awards
Re: random number between 0 and 41
« Reply #17 on: 01:02, 17 August 21 »
Indeed. But a property of a "good" random number routine is usually that it gives a reasonably even distribution over a long enough sample set, "clumps" can lead to results seeming too predictable or pattern like.


Obviously it depends what you're doing. Sometimes good enough is all it needs.
like
0
No reactions

Offline eto

  • Supporter
  • 6128 Plus
  • *
  • Posts: 507
  • Country: de
    • Awards
Re: random number between 0 and 41
« Reply #18 on: 15:29, 17 August 21 »
Real random numbers aren't evenly distributed anyway,

then they are not good random numbers. At least when the sample size is big enough, the random numbers should be (almost) evenly distributed.
like
0
No reactions

Offline eto

  • Supporter
  • 6128 Plus
  • *
  • Posts: 507
  • Country: de
    • Awards
Re: random number between 0 and 41
« Reply #19 on: 15:34, 17 August 21 »
though I suspect the distribution won't necessarily be very even.

can you share why? The only thing I see could be R, but at least if the random number generation is not at predictable times, R should be "random" enough to ensure the even distribution as long as the random number generator is good. I'd love to test this now, but I don't have access to my machine right now, as I'm on vacation.
like
0
No reactions

Offline Animalgril987

  • Supporter
  • CPC6128
  • *
  • Posts: 231
  • Country: gb
    • Awards
Re: random number between 0 and 41
« Reply #20 on: 19:33, 17 August 21 »
I have tested both @eto 's method and SpDizzy's ( as modified) and ego's is slightly more effective at being random.
like
0
No reactions

Offline SpDizzy

  • Supporter
  • CPC664
  • *
  • Posts: 83
  • Country: es
    • Awards
Re: random number between 0 and 41
« Reply #21 on: 20:26, 17 August 21 »
I have tested both @eto 's method and SpDizzy's ( as modified) and ego's is slightly more effective at being random.
In cases where speed is highly compromised, @eto's method always take same amount of microseconds and is a bit faster,  whereas mine could be slightly slower for bigger numbers, since you are repeating the loop until random number is below 42. On respect to size, I guess eto's takes 3 - 4 bytes more.
like
0
No reactions

Offline andycadley

  • Supporter
  • 6128 Plus
  • *
  • Posts: 1.022
    • Awards
Re: random number between 0 and 41
« Reply #22 on: 22:30, 17 August 21 »
can you share why? The only thing I see could be R, but at least if the random number generation is not at predictable times, R should be "random" enough to ensure the even distribution as long as the random number generator is good. I'd love to test this now, but I don't have access to my machine right now, as I'm on vacation.


Yes, largely because of R which has a habit of introducing predictability to RNGs. As you say, it may not make a difference though and you'd have to try it out to see for sure.
like
0
No reactions

Offline eto

  • Supporter
  • 6128 Plus
  • *
  • Posts: 507
  • Country: de
    • Awards
Re: random number between 0 and 41
« Reply #23 on: 11:34, 18 August 21 »
Yes, largely because of R which has a habit of introducing predictability to RNGs.

All pseudo random generators generate predictable sequences (unless you are using a different seed every time but then also R is no longer an issue I guess).
like
0
No reactions

Offline Targhan

  • Supporter
  • 6128 Plus
  • *
  • Posts: 1.426
  • Country: fr
    • Awards
Re: random number between 0 and 41
« Reply #24 on: 11:39, 18 August 21 »
Just to be sure, do you guys know about this article about generating pseudo-random numbers, written by @Grim ?
like
0
No reactions
Targhan/Arkos

Arkos Tracker 2.0.1 now released! - Follow the news on Twitter!
Disark - A cross-platform Z80 disassembler/source converter
FDC Tool 1.1 - Read Amsdos files without the system

Imperial Mahjong
Orion Prime