💾 Archived View for thrig.me › blog › 2024 › 02 › 18 › lehmer-prng.gmi captured on 2024-05-12 at 15:17:51. Gemini links have been rewritten to link to archived content
⬅️ Previous capture (2024-03-21)
-=-=-=-=-=-=-
Old pseudorandom number generators (PRNG) may have uses, say in musical composition where too predictable or too soon repeated numbers may be beneficial. Or maybe you are replicating an old game and want the authentic experience? I had been cargo culting the rogue 3.6.3 code around, but there are other old algorithms and seed values.
The middle-square method (1946) looked too fiddly to implement, so next is the Lehmer generator (1951). The input values should be chosen with care if you want the least bad results, or use an existing implementation from, say, the GNU Scientific Library, probably available in a ports or package system near you.
In music the ambitus is usually very small; MIDI runs from 0 to 127 inclusive (or 1 to 128 if you're one of those people), and many of those notes are not usable; a piano has 88 keys, or so, with the more distant notes less used. Most vocal or even instrumental works confine themselves to a much, much smaller range. Rhythms are usually also very small integers. An 8-bit value provides plenty of space for most things musical.
#include <stdint.h>
uint8_t
lrngsmol(uint8_t *state, uint8_t m, uint8_t a)
{
return *state = (uint16_t) *state * a % m;
}
This is probably too small. "m" should not be a power of two, unless you like repeats at a rate of "m/4". What does this look like? The "a" value is set somewhat arbitrarily to 7, using a value from the "Gauss Table" linked below.
for (uint8_t seed = 0; seed < 32; seed++) {
printf("seed %u -", seed);
uint8_t state = seed;
for (size_t i = 0; i < 8; ++i) {
printf(" %u", lrngsmol(&state, 32, 7));
}
putchar('\n');
}
$ make lrngsmol-32-7
cc -O2 -pipe -o lrngsmol-32-7 lrngsmol-32-7.c
$ ./lrngsmol-32-7
seed 0 - 0 0 0 0 0 0 0 0
seed 1 - 7 17 23 1 7 17 23 1
seed 2 - 14 2 14 2 14 2 14 2
seed 3 - 21 19 5 3 21 19 5 3
seed 4 - 28 4 28 4 28 4 28 4
seed 5 - 3 21 19 5 3 21 19 5
seed 6 - 10 6 10 6 10 6 10 6
seed 7 - 17 23 1 7 17 23 1 7
seed 8 - 24 8 24 8 24 8 24 8
seed 9 - 31 25 15 9 31 25 15 9
seed 10 - 6 10 6 10 6 10 6 10
seed 11 - 13 27 29 11 13 27 29 11
seed 12 - 20 12 20 12 20 12 20 12
seed 13 - 27 29 11 13 27 29 11 13
seed 14 - 2 14 2 14 2 14 2 14
seed 15 - 9 31 25 15 9 31 25 15
seed 16 - 16 16 16 16 16 16 16 16
seed 17 - 23 1 7 17 23 1 7 17
seed 18 - 30 18 30 18 30 18 30 18
seed 19 - 5 3 21 19 5 3 21 19
seed 20 - 12 20 12 20 12 20 12 20
seed 21 - 19 5 3 21 19 5 3 21
seed 22 - 26 22 26 22 26 22 26 22
seed 23 - 1 7 17 23 1 7 17 23
seed 24 - 8 24 8 24 8 24 8 24
seed 25 - 15 9 31 25 15 9 31 25
seed 26 - 22 26 22 26 22 26 22 26
seed 27 - 29 11 13 27 29 11 13 27
seed 28 - 4 28 4 28 4 28 4 28
seed 29 - 11 13 27 29 11 13 27 29
seed 30 - 18 30 18 30 18 30 18 30
seed 31 - 25 15 9 31 25 15 9 31
These are bad in that they repeat too often, and do not vary much. There are simpler ways to vamp on two or four notes (put the desired notes into a list and iterate on that), and the ranges here might be too large if mapped directly to pitch numbers or used as a rhythm. So we want more variety and less range.
Here a second modulus is taken to fit the output into a pentatonic scale (or rather index values that are used to lookup the desired pitches from an array), and all the seeds are looped through playing ten notes from each seed. Rhythm is distinct and is handled by something like the RANDU call. Not terrible (but it's hard to be terrible with a pentatonic scale), and it probably uses less CPU than a more complicated algorithm.
The rhythm and the melody need to be better integrated with one another, but that's more difficult.
Anyways the Lehmer random number generator is pretty simple and may suffice for certain needs. A small bummer is that the initial state should be coprime with the modulus, though with a low "m" it may be possible to test all starting values to see if any produce unusable results.
Mostly this involves opening a byte stream, writing bytes to it, sleeping, and remembering to flush the otherwise buffered output.
(defun noteoff (stream pitch &optional (velocity 0))
(write-byte #x80 stream)
(write-byte (logand pitch #x7f) stream)
(write-byte (logand velocity #x7f) stream)
(finish-output stream))
(defun noteon (stream pitch &optional (velocity 96))
(write-byte #x90 stream)
(write-byte (logand pitch #x7f) stream)
(write-byte (logand velocity #x7f) stream)
(finish-output stream))
(defun play-note (stream dtime pitch &optional (velocity 96))
(noteon stream pitch velocity)
(sleep (if (= dtime 48) 0.42 0.21)) ; KLUGE
(noteoff stream pitch))
(defun generate-midi (stream)
; TODO
)
(let ((stream (open "/dev/rmidi0" :direction :output
:if-exists :append :if-does-not-exist :error
:element-type '(unsigned-byte 8))))
(unwind-protect
(generate-midi stream)
(loop for n from 0 to 127 do (noteoff stream n))))
Gauss's Table of Primitive Roots and Indices from "Disquisitiones Arithmeticae"