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

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.