Rainbow, Factorial Algorithms, and You

In mathematics, a factorial represents the product of all the positive integers less than or equal to n. This is written as n!

So, n! = n * n-1 * n-2…

Generally, this operation can be implemented very simply with a recursive function such as:

int factorial(int n) {
    if(n != 1)
       return n*factorial(n-1);
}

However, this implementation is quite inefficient (plus Rainbow doesn’t really have any concept of functions or recursion). In Rainbow, a more reasonable solution would be to set a new variable, s, to the value of n, then create a loop that subtracts by 1 and sets s to the product of and n, finally breaking the loop when n equals 1. In our pseudo-C representation, it’d look something like:

int factorial(int n) {
    int s = n;
    while(n > 1) {
        s = s * --n;
    }
    return s;
}

Thanks to labels, lookaheads, and lookbacks, basic logic like this in Rainbow is pretty simple. Here’s a factorial calculator in Rainbow:

factorial

This representation isn’t terribly helpful though. Let’s break it down by each hex string, as the RainbowVM would.

0x300101 ;in at 0x00, len at 0x01
0x101100 ;set value of 0x01 to value of 0x00
0x5000F0 ;label with const 0xF0
0xB00001 ;sub 0x00 by const 0x01
0xC01100 ;mul 0x01 by val of 0x00
0x700100 ;lookahead to val of 0x00
0x500001 ;label with const 0x01
0x201101 ;print 0x01
0x000000 ;exit
0x500100 ;label with val of 0x00
0x6000F0 ;lookback to const 0xF0
0x000000 ;exit (unreachable)

The first line, 0x300101, instructs the RainbowVM to take input, put the value of the input starting at 0x00, and the byte length of the input at 0x01. We don’t expect numbers greater than 255 (especially as 6! is 720, which is much higher than our memory cell limitation of 255, and would result in undefined behavior within the RainbowVM), so we only expect the first address, 0x00, to have the value of n. We don’t care about the length of the input, so we put it in 0x01 arbitrarily.

The next line sets address 0x01 to the value of address 0x00. Here, we’re essentially establishing address 0x00 as n, and 0x01 as s.

Next, we set a label with the constant value of 0xF0. Any value would be applicable here, 0xF0 is just an arbitrary constant. This is effectively the start of our loop.

Then, we subtract 0x00, or n, by 1, and multiply 0x01, or s, by 0x00.

Now, we see a great example of simple logic in Rainbow. The line 0x700100 instructs the VM to lookahead until it encounters a label with the value of address 0x00, or n. Immediately following is a label with the value of the constant 1. Were 0x00 to be 1, the VM would begin execution here, printing the value of 0x01, and exiting. However, if the value at 0x00 is not 1, then the VM will continue looking ahead until it reaches 0x500100, which is a label with the value at address 0x00. The instruction following that label is a lookback to our constant 0xF0, which completes our loop.

The last instruction, 0x000000 is unreachable. It’s there simply to make the program 12 instructions long so it makes a nice 3×4 bitmap image.

So, now that we know how the program works, let’s walk through the calculation of 4!.

First, address 0x00 is set to 0x04, and address 0x01 is set to 0x01 (the byte length of the input). Then, address 0x01 is set to the value of 0x00 (4). Next, the value at 0x00 is subtracted by 0x01 and becomes 0x03. Now, the value at address 0x01 (4) is multiplied by the the value at 0x00 (3), and becomes 0x0C (12). The VM now looks ahead until it reaches a label with the value at 0x01 (4). It finds the label 0x500100, and begins execution at the instruction following the label. The VM now looks back until it reaches a label with the value of 0xF0. It finds the label 0x5000F0, and begins execution at the instruction following the label. We’ve completed our first iteration through our loop.

Now, we start again. The instruction following 0x5000F0 dictates that the value at 0x00 (3) be subtracted by 0x01. It becomes 0x02. Then, as before, the value at address 0x01 (12) is multiplied by the value at 0x00 (2), and becomes 0x18 (24). The VM looks ahead for the value at 0x00, and again finds 0x500100 then looks back until 0x5000F0, completing the loop once more.

We’ve reached our final iteration. The value at 0x00 (2) is subtracted by 0x01, and becomes 0x01. The value at 0x01 (24) is multiplied by the value at 0x00 (1) and remains 0x18 (24). Again, the VM looks ahead for the value at 0x01 (1). But, this time it finds 0x500001, a label with a constant value 0x01, first. The instruction following the label, 0x201101, is executed, printing the value at address 0x01 (24), and the program exits.

 

If you are interested in learning more about Rainbow, check it out on GitHub.