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:
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