Knuth shuffle: Difference between revisions
→{{header|6502 Assembly}}: Overhauled this section with a solution that can work with any range of values
Puppydrum64 (talk | contribs) m (→When the array address is known before runtime: forgot label to beginning of loop) |
Puppydrum64 (talk | contribs) (→{{header|6502 Assembly}}: Overhauled this section with a solution that can work with any range of values) |
||
Line 127:
=={{header|6502 Assembly}}==
===When the array address is known before runtime===
Runs on easy6502, which has a random number generated memory-mapped at zero page address <code>$FE</code> that updates after every instruction. Works on any array size up to and including 256 bytes. (The code I wrote here prior to this edit was much faster but only worked on arrays of exactly 256 bytes in size). The reason for this was that constraining a random number generator that can produce any 8-bit value to a subset is tricky, since just "rolling again" if out of range will eventually cause the program to lock up if it can't produce a value in range purely by chance. This method uses a bit mask that shifts right as the loop counter decreases to zero, which means that even when only a few bytes still need to be shuffled, the routine is just as quick as it was at the beginning.
<lang 6502asm>define sysRandom $fe
define
define range $00
define tempX $01
define tempY $02
define tempRandIndex $03
define temp $04
CreateIdentityTable:
txa
sta $0200,x
sta $1000,x
inx
bne CreateIdentityTable
;creates a sorted array from 0-255 starting at addr $1000
;also creates another one at $0200 for our test input
lda #1
sta range
ConstrainRNG:
ldx #255
;max range of RNG
lda range
bne outerloop
jmp end
outerloop:
cpx range
bcc continue ;if X >= range, we need to lower X
pha
txa
sta tempX
cmp range
bcc continue2
tax
pla
jmp outerloop
continue2:
pla
ldx tempX
continue:
ldy range
KnuthShuffle:
lda sysRandom
and $1000,x ;and with range constrictor
tay
lda $0200,y
sty tempRandIndex
sta temp
ldy range
lda $0200,y
pha
lda temp
sta
pla
ldy tempRandIndex
sta $0200,y
dec range
jmp ConstrainRNG
end:
brk</lang>
=={{header|AArch64 Assembly}}==
|