PRNG component

[gixslayer]

I was working on an example processor, and wanted to create some very simple games for it (something like a number guessing game), as a fun way to showcase some features such as the terminal/keyboard. I think simple games like that could be great pedagogical tools with respect to assembly programming. The problem I ran into however is that I needed a source of random numbers for many of these games, which as far as I can tell Digital does not provide natively.

My workaround so far is to have a Counter increase on every rising clock edge, and then use the value of this counter to seed a Linear congruential generator implemented in assembly after an indeterminate amount of time (in this case after the player enters their name). While this works, it is pushing quite a bit of complexity into the assembly sides of things. The processor I'm working on is purposely kept very simple so that it is easier to build for students, meaning things such as multiplies, divides and remainders are not natively supported in the machine code, and also have to be built up using functions that emulate them.

A much simpler solution (from my perspective) would be to have a special PRNG component capable of generating pseudo random numbers. I was wondering how you would feel about such a component. Is it something you'd consider adding to Digital, or is it too specialized for this situation, and should it be relegated to the loadable Java library (external JAR) instead? So far I've managed to build (a version of) this entire processor (+ additional components such as I/O and the screen) using nothing but the readily available components in Digital.

Do you have any other ideas of how to implement something such as this? I've considered implementing most of the LCG itself in a Digital circuit, which would eliminate a lot of complexity in the assembly side of things, but that still leaves the problem of having to obtain a random seed to get the LCG going. Is a counter tied to the clock, polled at an indeterminate time, the best way to obtain such a seed, or are there easier options? Note that I don't specifically care for high quality random numbers, certainly nothing cryptographically secure. As long as it appears random enough for these example games I'm satisfied.

This is the code I was toying around with just now, which seems to work after doing just a tiny bit of manual testing:

public class PRNG extends Node implements Element {
    public static final ElementTypeDescription DESCRIPTION
            = new ElementTypeDescription("PRNG", PRNG.class,
            input("S", "PRNG seed input"),
            input("se", "If set, then seed PRNG with seed input on rising clock"),
            input("ne", "If set, then set value to next pseudo-random number on rising clock"),
            input("C", "Clock").setClock()) {

        @Override
        public String getDescription(ElementAttributes elementAttributes) {
            return "A Pseudo-random number generator";
        }
    }.setShortName("PRNG")
            .addAttribute(Keys.ROTATE)
            .addAttribute(Keys.BITS)
            .addAttribute(Keys.LABEL);

    private final ObservableValue output;
    private final int bits;
    private final long minValue;
    private final long maxValue;
    private ObservableValue seedVal;
    private ObservableValue setVal;
    private ObservableValue nextVal;
    private ObservableValue clockVal;
    private boolean lastClock;
    private long value;
    private final Random random;

    public PRNG(ElementAttributes attributes) {
        bits = attributes.get(Keys.BITS);
        output = new ObservableValue("R", bits).setDescription("The current random value");
        // TODO: let these be set by attributes
        minValue = Long.MIN_VALUE;
        maxValue = Long.MAX_VALUE;
        // Let Java set the initial seed so that different values are generated each simulation,
        // unless a specific seed is set by the user later on.
        random = new Random();
        value = ensureValueInRange(random.nextLong());
    }

    @Override
    public void readInputs() throws NodeException {
        boolean clock = clockVal.getBool();

        if (clock && !lastClock) {
            // First update seed
            if(setVal.getBool()) {
                random.setSeed(seedVal.getValue());
            }

            // Then value. This keeps the component well defined in case both 'set' and 'next' inputs are set.
            if(nextVal.getBool()) {
                value = ensureValueInRange(random.nextLong());
            }
        }

        lastClock = clock;
    }

    @Override
    public void writeOutputs() throws NodeException {
        output.setValue(value);
    }

    @Override
    public void setInputs(ObservableValues inputs) throws NodeException {
        // Note: could separate bit count for seed input & value output
        seedVal = inputs.get(0).checkBits(bits, this);
        setVal = inputs.get(1).checkBits(1, this);
        nextVal = inputs.get(2).checkBits(1, this);
        clockVal = inputs.get(3).addObserverToValue(this).checkBits(1, this);
    }

    @Override
    public ObservableValues getOutputs() {
        return output.asList();
    }

    private long ensureValueInRange(long value) {
        // Ensure value lies in the [minValue, maxValue) range, i.e. minValue <= value < maxValue.
        return minValue + Math.floorMod(value, maxValue - minValue);
    }
}

[hneemann]

There is indeed a way to generate random numbers: The clocked RS flipflop outputs a random bit if S and R are set at the rising edge of the clock. But using this is probably misuse. 😄
Now that I read this post, I also remember two very motivated students who also programmed a game in assembly, and encountered the same problem some time ago: There was no way to generate random numbers required for a game.

So there is definitely a need for such a component.

Your suggestion looks quite good. But why would you want to set min, max and bits? Isn't that redundant?

[gixslayer]

Yea you're right those parts are redundant and could be accomplished with some extra circuit bits (or pushed to assembly level to deal with). Technically all I would need is something that can output a (64 bit) random number. Having some control on the seed used, and when it generates the next random number in the sequence are just some nice additions to make it a bit easier to work with, especially when debugging as you can still get deterministic behavior. The code above was mainly a test to see if I could quickly get something working in Java.

I would like to be able to set the seed from within a circuit (as opposed to using the GUI with an attribute), as this allows me to set the seed with a program being executed. That way I can write programs that are fully deterministic across different machines, without having to change anything inside Digital itself. Again this would be nice for debugging purposes, and if it ever gets to the point of being included in some exercise/assignment for students on our side, we can also use this deterministic behavior to simplify the grading as the behavior/output should be the same for all students.

I suppose technically a single random source would still suffice for that use case if you build a RNG circuit on top of it that is either seeded with that random value, or a known seed, but again I'm thinking in terms of what would be convenient for me. As long as I have something that spits out a random number I can make it work.

[hneemann]

added a PRNG in 2dab02e