| |
Style
Registered: Jun 2004
Posts: 498 |
Pseudo-random number generator, set complete?
Hi all
Im looking for an algorithm that will generate random-looking numbers from 1 - 1000, but will only ever select any one number once. Obviously this is for the 64 screen :)
I seem to recall set complete pseudo-random algorithms at uni but cant recall much more. Any advice?
thanks
|
|
| |
chatGPZ
Registered: Dec 2001
Posts: 11293 |
my usual approach to this kind of problem is the "card shuffle" algo, ie use a regular prng and shuffle a sorted set with it. i remember "set complete" prng though, but if i recall correctly they always had a fixed size (usually 2^n) and size of the set, which is not always useful. |
| |
Style
Registered: Jun 2004
Posts: 498 |
A 2^10 set complete prng would be cool :)
shuffling a list of 1000 16 bit numbers = ~2k = expensive......
What I might do is come up with a shuffled list of say 100 8 bit numbers, and then reuse them 10 times. It would look bad if the number was divisible by 40, but maybe 100 would look ok.....
|
| |
chatGPZ
Registered: Dec 2001
Posts: 11293 |
just looked at some old source of mine, where i used this one to clear a bitmap.... not sure how much it is what you want, but it seemed to work for me:
getrandom:
lda random+1
sta temp1
lda random
asl a
rol temp1
asl a
rol temp1
clc
adc random
pha
lda temp1
adc random+1
sta random+1
pla
adc #$11
sta random
lda random+1
adc #$36
sta random+1
rts
temp1: .byte $5a
random: .byte %10011101,%01011011
|
| |
Style
Registered: Jun 2004
Posts: 498 |
cool groep, thanks for that, Ill see what it does when I get home :) |
| |
King Durin
Account closed
Registered: Oct 2007
Posts: 85 |
You could always calculate 100 cells and then on each iteration EOR the cell so that the pattern appears more random on the screen. You could also shift your starting point randomly so you aren't always starting at $FF which would enhance the randomness of the display. |
| |
JackAsser
Registered: Jun 2002
Posts: 2014 |
Or use any of the 8-bit pseudorandom algorithms on Codebase. They produce a series of 0-255 in a shuffled manner, where each value is covered exactly once. Then use 4 seeds at the same time to cover 0-1023 and use that to randomize your screen, promptly ignoring the 24 byte overflow. |
| |
ready.
Registered: Feb 2003
Posts: 441 |
I happened to have the same problem when fading pseudo-randomly the last pic in the demo Aurora 100%. This code produces pseudo random sequences from 0 to $f, but it actually has a 0-$ff range, then you can clip it by changing max_no. It is nice since it does not require any table and is very compact in memory, ok the below version is adapted so you can see the output on the screen. Press space to generate more sequences.
You can easily adapt it in order to generate sequences from any number to any number.
Furthermore it tells you when the set is complete.
*=$0801
.byte $0c,$08,$0a,$00,$9e
.byte 0+$30,2+$30,3+$30,0+$30,4+$30 ;start address
*=$0900
;clear screen
jsr $e544
;prepare zero page vector for screen output
lda #<$0400
sta zp
lda #>$0400
sta zp+1
;start CIA2 counter to be used as rnd number generator (counts down from $ffff continously)
lda #$ff
sta $dd04
sta $dd05
lda #%00010001
sta $dd0e
;y is the char x-position pointer on the screen
ldy #0
m_001
lda no ;no is the tune number 0-255 you want to load
clc
adc increment
sta no
bcc m_002
;when no > 255 pass = pass +1
inc passes
lda passes
cmp increment
bne m_002
;when passes = increment the random sequence has been completed (all number from 0 to 255 has been pulled out)
lda zp
clc
adc #40 ;add one row to display
sta zp
lda zp+1
adc #0
sta zp+1
lda #0
sta passes
m_006
lda $dd05 ;loads new random number
ora #1 ;random number must be an odd number
sta increment
sta no
ldy #0 ;reset char x-position pointer on screen
inc rows
lda rows
cmp #20 ;when row = 20 then wait for spacebar
beq m_exit
m_002
lda no
cmp #max_no ;max number of sequence, can be any from 0 to 255
bcc m_000
jmp m_001
m_000
tax
lda number_tbl,x ;generate char to be displayed
sta (zp),y ;put char on screen
iny
jmp m_001
m_exit
;wait for spacebar and generate more sequences
lda #0
sta rows
lda $dc01
m_008
cmp $dc01
beq m_008
jmp $0900
rts
;variables
number_tbl .byte $30,$31,$32,$33,$34,$35,$36,$37,$38,$39,$01,$02,$03,$04,$05,$06
zp = $2
rows .byte 0
passes .byte 0
no .byte 1
increment .byte 13
max_no = $10 |
| |
Krill
Registered: Apr 2002
Posts: 2940 |
I think that a regular LFSR algorithm with 10 bits should be alright. If you trip on something between 1000 and 1024, simply call the routine another time. Pretty unlikely to need more than 2 attempts to get your next unique number within shuffle range.. |
| |
Digger
Registered: Mar 2005
Posts: 423 |
This thread reminds me of a basic program I wrote back in '96 Randomizer and released today.
It only does up to 256 values but I thought it would be nice to unleash it ;) Enjoy. |
| |
Krill
Registered: Apr 2002
Posts: 2940 |
Oh, and i just see groepaz's solution plus ANDing with $03ff and retry until y <= 1000 would be pretty similar to what i meant.. :) |
| |
Style
Registered: Jun 2004
Posts: 498 |
Thanks for mentioning LFSR krill. Id never come across them before, but that's exactly what I need. And yep, that looks like what Groep's routine is doing - of course, Ill have to write my own, otherwise Ill have to credit Groep :)
|
| |
chatGPZ
Registered: Dec 2001
Posts: 11293 |
hihi... this routine isnt mine either... or well, the algo isnt :) |
| |
Style
Registered: Jun 2004
Posts: 498 |
pfffft...... dirty ripper
:) |
| |
ChristopherJam
Registered: Aug 2004
Posts: 1403 |
or, could use the old linear congruential. Here's x=(x*261+117)%1024:
genRand
; perform rand'=(rand*261+117)%1024
lda rand
asl
rol t4hi ; don't need to init t4hi, as only using bottom two bits
asl
rol t4hi
clc
adc rand
sta rand
lda t4hi
adc rand+1 ;a::rand' is now rand*5
clc
adc rand ;(a::rand')%1024 is now (rand*261)%1024
sta rand+1
clc
lda rand
adc#117
sta rand
lda rand+1
adc#0
and#3
sta rand+1
rts
rand
lda#0
t4hi
brk
(cf http://en.wikipedia.org/wiki/Linear_congruential_generator . The 117's an arbitrary odd number, and the multiplier must be one more than a multiple of four ) |
