Random numer between 0 -18

[Thelen]

To get a random number between 0 and 18 I use the following routine :

 

BOM LDA RANDOM

STA TMP2 ;holds the random numer between 0 - 18

CLC

ADC #237

BCS BOM

 

But this consumes way too much time because most of the times the random numer is too high...

 

Could somebody show me the right way to do this ?

 

Thanks !

[GroovyBee]

Why is the limit 18? If it was 0 to 15 you could logical and with #$0F or shift right.

[Rybags]

There's a number of ways, you could AND out the higher bits first so that there's much better chance, e.g. AND #$1F means you'd have 0-31 but still that's nearly half that would fail.

 

Better again might be to just build the random number out of the sum of 2 smaller ones.

 

e.g. LDA $D20A

AND #3 ; will always be 0-3

STA RND

LDA $D20A

AND #$F ; will always be 0-15

CLC

ADC RND

STA RND ; will always be 0-18

[Lazarus]

What does "between 0 and 18" mean to you? Normally that would be 1 to 17

 

loop:

LDA RANDOM

LSR

LSR

LSR

CMP #19

BCS loop

 

 

 

Another possibility:

 

LDX RANDOM

LDA table18,X

 

Where table18 contains numbers from 0 to 18 in randomized or linear order.

Edited December 13, 2012 by Lazarus

[Thelen]

Thanks for thinking with me, guys ! And it would be more easy if it was a number 0-15 indeed, but it has to do with random screen x,y coordinates.

[Heaven/TQA]

go the lookup table way...

[RevEng]

Better again might be to just build the random number out of the sum of 2 smaller ones.

The downside of this method is that it makes the distribution of numbers non-uniform. The numbers at the edges of the range will be less likely to occur, as I was schooled-about in this thread.

 

@Thelen:

If you're just looking for a 1-in-19 chance, then test for the byte being 13 or less. (which is 1-in-19 scaled to a range of 256)

If you need 0-in-18 with uniform distribution, then just add an "and #31" in your original routine after loading the random number, to reduce the range so you get less retries. (edit - just noticed Rybags also suggested this. Nice!) Or use a lookup table as Heaven/TQA suggests.

If you don't care about uniform distribution, then Rybags solution is easy to implement, uses less space, and runs in constant time.

[sack-c0s]

or just fill 2^n bytes with the numbers 0-18 (as evenly as possible). Then generate a random number, use an AND to mask down to the relevant number of bits and use that as an offset into your table.

 

It won't be mathematically correct, but it should pick a reasonable distribution of screen co-ords if your initial random number generator is okay so it'll do

Edited December 14, 2012 by sack-c0s

[Thelen]

Thanks for the reply's ! It opened up my eyes to do things better !

[bogax]

One way is to just scale what you've got to what you want

You have a trade off between how much adding of extra

pieces you want to do and how nice a distribution you want

 

You could start with 5 bits ie begin by ANDing your random

number with $1F but the distribution won't be very good

 

You probably don't need to use all eight bits though

(I'm assuming you're starting with 8 bits ie 0-255)

 

Here's code that uses a number 0-63

 

It multiplies (with some rounding thrown in,

ie no clearing the carry for the adds)

by 1.1875, 1 3/16 then divides by 4 and negates

 

; assuming there's a random number 0=255 in a

and #$3F ; mask for 0-63 call that r
sta temp
lsr ; / 2 = .5 * r
adc temp ; + 1 = 1.5 * r  
lsr
lsr
lsr ; 1.5 / 8 = .1875 * r
adc temp ; + 1 = 1.875 * r , 75 max with rounding
lsr
lsr ; 75 / 4 = 18 max

; negate
eor #$FF
clc
adc #$01

Edited December 14, 2012 by bogax

[bogax]

There's a number of ways, you could AND out the higher bits first so that there's much better chance, e.g. AND #$1F means you'd have 0-31 but still that's nearly half that would fail.

 

Better again might be to just build the random number out of the sum of 2 smaller ones.

 

e.g. LDA $D20A

AND #3 ; will always be 0-3

STA RND

LDA $D20A

AND #$F ; will always be 0-15

CLC

ADC RND

STA RND ; will always be 0-18

 

Have you actually checked to see how well that works?

If it were really random, I don't think you'd get an

even distribution.

I think on average 0 and 18 will come up 1 in 76 times

17 and 1 will come up 2 in 76 times 2 and 16 will come

up 3 out of 76 and all the rest 4 out of 76.

If it's not random (and it's not, but maybe close enough)

it might be worse.

Imagine what it would be if it were a simple binary

counter instead of a polynomial counter (LFSR)

Edited December 16, 2012 by bogax

[Rybags]

It'll have the unbalanced bias.

 

The hardware random number generator is totally deterministic (so isn't really "random") - but for most purposes it's just fine. The variable timing of 6502 code + the fact that scalines/frames aren't integer divisors of the sequence length mean that a program would rarely read the same sequence twice.

 

Possibly a better method could be to (1) read the Random register, then save it.

(2) Then AND #$1F and compare. (3) If it's over 18, get the saved value and shift right (divide by 2). If the result = 0 go back to (1) otherwise go back to (2)

[bogax]

You have a trade off between how much adding of extra

pieces you want to do and how nice a distribution you want

 

You could start with 5 bits ie begin by ANDing your random

number with $1F but the distribution won't be very good

 

You probably don't need to use all eight bits though

(I'm assuming you're starting with 8 bits ie 0-255)

After a second look, it's really not

much more to use all 8 bits

It only costs a couple cycles and it

gives you a better distribution.

 

The code is basically the same.

sta temp
lsr
adc temp
ror
lsr
lsr
adc temp
ror
lsr
lsr
lsr

eor #$FF
clc
adc #$01

[popmilo]

.... Possibly a better method could be to (1) read the Random register, then save it.

(2) Then AND #$1F and compare. (3) If it's over 18, get the saved value and shift right (divide by 2). If the result = 0 go back to (1) otherwise go back to (2)

Tried it with values needed from 0-5 and distribution is not uniform. Most often it produces 2,3,4... I guess it's focused around middle of given range.

 

Simple loop until random (and mask) is less then maximum value produces nice results and isn't much slower.

[Bryan]

I'm sure someone has a really elegant solution to this (it seems there's always a bit of trick 6502 code for any problem). So...

 

We have 19 desired states (0,1,2...18) and we want equal weighting from an 8-bit random source. If we divide 256 states by 19, we get roughly 13.5- an ugly number for distribution, but 512 states gives us 26.95 which is workable. So, we take 27 states and assign them to one resulting value, and the last value is weighted slightly lower at 26 (applying a moving offset to the result would mask the presence of this anomaly if it was really critical).

 

A 512-byte LUT may be a bit cumbersome for some projects. I'm trying to figure out if there's a shortcut to the division. Doing it with a tree would return a result after a few comparisons.

[Bryan]

Follow up: I think this will work, but I haven't tested it.

;The code finds out which range of 27 values we're in and the value is left in X
;0-26=0, 27-53=1 ... 243-255=9 <-this is a short range of 13 values.
;To speed things up, a jump to case 5 is made immediately if the RANDOM value is >=135.
;Once we have a value (in X), we test a 9th random bit for the 2nd half of the range.
;To create the 2nd half, we flip the 0-9 range so that 9=9, 8=10, 7=11, etc...
;This way, we contribute another 13 values to the 9 case for a total of 26.
;This means all values have a 27-in-512 chance except for case 9 which is 26-in-512.


   lda RANDOM    ;random byte in A
   ldy #4        ;loop counter
   ldx #0        ;table index
   cmp #135    ;>= half-way point?
   bcc loop
   ldx #5
loop
   cmp table1,x
   bcc escape
   inx
   dey
   bne loop
escape
   txa        ;X is our value
   bit RANDOM    ;test bit 7 to make 'bit 8'
   bpl escape2
   xor #$FF    ;flip X
   clc
   adc #19        ;range 9-18
escape2

;A is our random number!!!


table1
27,54,81,108,0,162,189,216,243,0

[Bryan]

I know this is an old thread and Thelen probably isn't reading it, but I had another idea for an even distribution method (this is probably similar to what others stated above)... Take the last number and add a random offset to it - Something like:

 

 

lda RANDOM

and #$F ;max offset of 15.

clc

adc OLDVAL

cmp #19 ;>= 19?

bcc skip

sbc #19 ;a value of 19 becomes a value of 0

skip

sta OLDVAL

 

At this point, we have a new RND value in A. but it's not completely random since there are values that cannot follow each other. So, the more times you run the loop before using the value, the more random it becomes. However, the final distribution of values is even.

[popmilo]

I know this is an old thread and Thelen probably isn't reading it, but I had another idea for an even distribution method (this is probably similar to what others stated above)...

It is an old thread, but the subject is always interesting.

 

Experimenting with different random approaches I stumbled on something interesting.

I applied non-uniform distribution results onto x,y coordinates of bunch of objects.

Turns out I could tweak one parameter and 'decide' where the majority of objects would move after a while.

Basically - set a rough direction and all objects would slowly 'drift' or 'flock' to one side or corner of screen.

 

Still don't know what to use it for, but it sure looked like I made something smart intentionally

[xxl]

lda #0

ldy #17

@ lsr random

adc #0

dey

bpl @-

 

regA (0-18)

 

Edited May 14, 2013 by xxl

[Bryan]

lda #0

ldy #17

@ lsr random

adc #0

dey

bpl @-

 

regA (0-18)

 

This gets a 1 or a 0 in C 18 times and adds them together, right? I would tend to think this would clump all the values around the middle (50%) since only all 0's or all 1's can produce the extreme values.

[Bryan]

It is an old thread, but the subject is always interesting.

 

Experimenting with different random approaches I stumbled on something interesting.

I applied non-uniform distribution results onto x,y coordinates of bunch of objects.

Turns out I could tweak one parameter and 'decide' where the majority of objects would move after a while.

Basically - set a rough direction and all objects would slowly 'drift' or 'flock' to one side or corner of screen.

 

Still don't know what to use it for, but it sure looked like I made something smart intentionally

It could make an interesting AI following routine.

[+Gemintronic]

I just looked up what a numer is:

http://www.urbandictionary.com/define.php?term=Numer

 

I'm not sure if I'd want one (random or not).

[xxl]

lookup table

 

 

_ini600 lda #$0d

_2 eor #$01

pha

tax

_3 lda #$00

_1 sta $600

inc _1+1

beq _ret

dex

bpl _1

pla

inc _3+1

bne _2

_ret pla

rts

 

 

 

_0to18 ldx random

lda $600,x

rts

 

?

Edited May 14, 2013 by xxl