Rosetta Code

Knuth shuffle: Difference between revisions

Page Discussion

Knuth shuffle (view source)

Revision as of 20:36, 30 December 2021

1,212 bytes removed ,  2 years ago
→‎{{header|6502 Assembly}}: Overhauled this section with a solution that can work with any range of values
m (→‎When the array address is known before runtime: forgot label to beginning of loop)
(→‎{{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.
This is a bit easier since you can use both the X and Y registers to index the same array.
 
If the array is exactly 256 bytes, and the RNG can output anything from 0-255, the shuffle will be much faster since there's no way
to index out of bounds. '''The code below assumes both are true and won't work properly otherwise.'''
 
Runs on easy6502.
<lang 6502asm>define sysRandom $fe
define temptempMask $00ff
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 of values from 0-255
;creates a sorted array from 0-255 starting at addr $1000
;also creates another one at $0200 for our test input
 
lda #1
KnuthShuffle:
sta range
lda $0200,y
sta temp
 
ConstrainRNG:
lda $0200,x
ldx #255
sta $0200,y
;max range of RNG
lda range
bne outerloop
jmp end
 
outerloop:
lda temp
cpx range
sta $0200,x
bcc continue ;if X >= range, we need to lower X
pha
txa
sta tempX
 
dexlsr
cmp range
bne KnuthShuffle
bcc continue2
 
tax
pla
jmp outerloop
 
continue2:
pla
ldx tempX
 
continue:
brk ;end program</lang>
ldy range
 
===Using pointers===
Unfortunately, we are limited to using Y for offsetting. This means there are more temp variables to keep track of.
(Even though the array's location is still fixed in the example, in practice you'll want a function that can shuffle arrays anywhere,
so the code assumes that the location isn't already known.)
 
<lang 6502asm>define sysRandom $fe
define temp $00
define HL $02
define L $02
define H $03
define tempY $04
define tempY_random $05
 
CreateIdentityTable:
txa
sta $0200,x
inx
bne CreateIdentityTable
 
 
lda #$00
sta L
lda #$02
sta H ;lda HL,$0200
 
 
ldy #0 ;i
KnuthShuffle:
lda sysRandom
sty tempY
and $1000,x ;and with range constrictor
ldy sysRandom
tay
lda (HL),y
sta temp
sty tempY_random
ldy tempY
lda (HL),y ;lda (HL),i
 
lda $0200,y
sty tempRandIndex
sta temp
ldy range
lda $0200,y
pha
lda temp ;lda (HL),sysRandom
sta (HL)$0200,y ;sta (HL),i
pla
ldy tempRandIndex
sta $0200,y
dec range
jmp ConstrainRNG
 
end:
ldy tempY_random
brk</lang>
sta (HL),y ;sta (HL), sysRandom
 
ldy tempY
dey ;i--
bne KnuthShuffle
 
brk ;end program</lang>
 
===Using self-modifying code to speed up the previous method===
Once again, this method assumes an array size of 256 and a random number generator that is equally likely to produce any outcome from 0 to 255.
 
<lang 6502asm>define sysRandom $fe
define temp $00
define tempX $01
 
CreateIdentityTable:
txa
sta $0200,x
inx
bne CreateIdentityTable ;creates a sorted array of values from 0-255
 
LDA #$00
LDX #$00
LDY #$02
 
KnuthShuffle:
;input: A = the array size (max 256, use 0 for 256)
;X = low byte of addr. where array begins
;y = high byte of addr. where array begins
 
stx smc_KnuthShuffle_alpha+1
stx smc_KnuthShuffle_beta+1
stx smc_KnuthShuffle_gamma+1
stx smc_KnuthShuffle_delta+1
 
sty smc_KnuthShuffle_alpha+2
sty smc_KnuthShuffle_beta+2
sty smc_KnuthShuffle_gamma+2
sty smc_KnuthShuffle_delta+2
 
tax ;get array size into x, to act as the loop counter
 
doKnuthShuffle:
ldy sysRandom
smc_KnuthShuffle_alpha:
lda $BEEF,y ;B9 EF BE (BEEF will get overwritten with the desired address in all four cases)
 
sta temp
smc_KnuthShuffle_beta:
lda $BEEF,x ;BD EF BE
 
smc_KnuthShuffle_gamma:
sta $BEEF,y ;99 EF BE
 
lda temp
smc_KnuthShuffle_delta:
sta $BEEF,x ;9D EF BE
 
dex
bne doKnuthShuffle
 
brk ;end program</lang>
 
=={{header|AArch64 Assembly}}==
Puppydrum64
1,489

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/111137"