Writing a programming language: Implementing the Sieve of Eratosthenes on DVM01

Okay, so how do we implement this in DVM01? Since we (currently) have poorno support for memory management, the first thing I thought was that we need some agreement over how to do the marking. Usually, you set up a bunch of memory first, initializing it. Better implementation don’t use a list of booleans, but use every bit separately, thus saving a huge load of space. We won’t do that, because it makes the code more complex. Also, we won’t initialize the memory, as the DVM01 does this for us (every cell is zero at first access).

Then, “traditional” implementations do the output and calculation in the same loop: If your cell has not been marked as non-prime, output it before increasing the step size. For simplicity, I’ve decided to rip out the print loop and write it separately. Other than that, the implementation follows the normal rules of the algorithm.

So, how does it work?

Okay. The first step is pretty easy - It’s a NOP slide initialisation to make space for some faux “registers”.

START # 0: contains program counter
NOP   # 1: Points to the beginning of the data
NOP   # 2: Largest number to check
NOP   # 3: Current step size
NOP   # 4: Pointer to currently evaluated cell
NOP   # 5: Start address of outer marker loop and print loop
NOP   # 6: Start address of inner marker loop
NOP   # 7: Conditional accumulator for loop termination
NOP   # 8: Counter for printing

SET 1 100 # Marks the beginning of data section. TODO: calculate dynamically
          # Note: this has been determined by using DUMP. When the program
          # expands, this MUST be increased, or you WILL get ugly results :)

SET 2 100 # Biggest number to check for. Well, approximately, as we're not
          # very careful about when to stop (allows us some simplifications)

Pretty easy, huh? Well that was only the initialisation, so don’t yawn too early! The next step is a nested loop: The outer loop basically increases the step size and re-sets the current-cell pointer. The inner loop walks the “data area” and marks every seen number (which is a multiple of the step-size) as non-prime. Then, only some small-god magic is required to figure out whether to terminate the loop or not.

# Begin outer marker loop (counting up the step size).

SET 3 2   # Step size, begins with 2
SET 4 @1  # Pointer to currently evaluated cell.

SET 5 @0   # Marker for outer loop

    SET 4 @1   # Start out at position zero
    ADD 4 @3   # Add current-step-size to our pointer.

    # Begin inner marker loop (do the actual marking)

    SET 6 @0   # Marker for inner loop
        ADD 4 @3   # Add current-step-size to our pointer
        SET @4 1   # Mark position as non-prime

        # Figure out if we need to re-run inner loop:
        # If pointer is bigger than position of largest number
        # to check, we abort the loop.

        SET 7  @1     # beginning-of-data
        ADD 7  @2     # add number range
        JGT @6 @7 @4  # Re-run loop if upper bound (@7) > current-ponter (@4)

    ADD 3  1 # Increase step-size

    # Figure out if we need to re-run inner loop:
    # If step-size is bigger than half of the number range,
    # we abort the outer loop.

    SET 7  @3     # 7 is now step-size
    MUL 7   2     # 7 is now step-size * 2
    JGT @5  @2 @7 # Re-run loop if number-range (@2) > step-size * 2 (@7)

Okay, now that we have the primes sorted, it’s only a question of telling the user about our discovery. Not very hard:

SET 5 @0

    ADD 8 1       # add 1 to output counter
    ADD 4 1       # Evaluate next cell
    COPY 7 @4     # De-reference pointer-to-current-cell, to check it's content
    JNZ @5 @7     # Restart loop if current-cell is nonzero (it had been marked)
                  # Note that this only works because uninitialized memory is always zero
    WRITEI @8     # Output number in register 7 - it's a prime number.
    WRITEC 10     # Newline

    JGT @5 @2 @8  # Restart loop if number-range (@2) > our counter (@7)

# End program

END

Of course, you can grab a copy of all examples, plus the implementation of the VM on Github:

Post Scriptum

Oh by the way - I’ve changed the source a bit to make it run on node.js, as well. You can run it with logging enabled or disabled, like this:

:::shell
# Full Parser/VM logging output:
node noderunner.js source-file.txt

# Disable Parser/VM output - only allow your program to write:
node noderunner.js -nolog source-file.txt