Skip to navigation

Lander on the Acorn Archimedes

Maths (Arithmetic): GetRandomNumbers

Name: GetRandomNumbers [Show more] Type: Subroutine Category: Maths (Arithmetic) Summary: Generate pseudo-random numbers from the random number seeds Deep dive: Random numbers
This algorithm appears in the original 1986 ARM Assembler manual that came with Acorn's ARM Evaluation System (it's in section 11.2 on page 96). It also appears in later Acorn manuals, such as Acorn Desktop Assembler (release 2), where it's on page 186. Here's the algorithm's description from the manual: "It is often necessary to generate (pseudo-)random numbers and the most efficient algorithms are based on shift generators with exclusive-or feedback rather like a cyclic redundancy check generator. Unfortunately the sequence of a 32-bit generator needs more than one feedback tap to be maximal length (that is 2^32-1 cycles before repetition). A 33-bit shift generator with taps at bits 20 and 33 is required. The basic algorithm is newbit := bit33 eor bit20, shift left the 33 bit number and put in newbit at the bottom. Then do this for all the newbits needed, that is 32 of them. Luckily this can all be done in five S cycles."
Returns: R0 A random number R1 A random number
.GetRandomNumbers STMFD R13!, {R14} \ Store the return address on the stack LDR R0, randomSeed1 \ Set R0 = randomSeed1 LDR R1, randomSeed2 \ Set R1 = randomSeed2 TST R1, R1, LSR #1 \ Set flags on R1 AND (R1 >> 1) MOVS R14, R0, RRX \ Rotate R0 right, incorporating the C flag, \ and store the result in R14, replacing the \ C flag with bit 0 from R0 ADC R1, R1, R1 \ R1 = R1 + R1 + C EOR R14, R14, R0, LSL #12 \ R14 = R14 EOR (R0 << 12) EOR R0, R14, R14, LSR #20 \ R0 = R14 EOR (R14 >> 20) STR R1, randomSeed1 \ Set randomSeed1 = R1 STR R0, randomSeed2 \ Set randomSeed2 = R0 LDMFD R13!, {PC} \ Return from the subroutine