Multiplication with Q8

As a gentle introduction to the Quine8 (Q8) tool, we'll start by multiplying two numbers. Because the Q8 instruction set does not contain a multiply operation, we'll have to write our own. The algorithm for multiplication is pretty easy, you probably learned it in grade school.

6 * 4 = 24

That can be expanded in one of two ways:

6 + 6 + 6 + 6 = 24
6, 4 times is 24

4 + 4 + 4 + 4 + 4 + 4 = 24
4, 6 times is 24

In a C-like language, they look like this:

int x = 0;
for (int i = 4; i > 0; i--) {
    x += 6;
}

int x = 0;
for (int i = 6; i > 0; i--) {
    x += 4;
}

If you look at the two examples carefully, you'll notice that one of the 2 will resolve faster than the other. 4 times through the loop is faster than 6, and the larger the difference between the two numbers, the more this will effect runtime. If we ran 2 * 50, it would either run through the incremental loop twice or fifty times. That makes a huge difference, especially for the Q8 bytecode.

Loop ops: 10
Add Increment tiles: 11

1 time through the loop: 10 + 11 = 21 tiles
2 times through the loop: 21 * 2 = 42 tiles
50 times through the loop: 21 * 50 = 1,050 tiles

Assuming each tile takes 1 second, that's the difference between running in 42 seconds, and running for 17 and a half minutes. This is an optimization definitely worth having.