- That’s totally freakin’ awesome by the way
- — Ben Johnson, September 11, 2006
For those who don’t know, Carnage Heart is a video game for the original Sony Playstation. It’s a war/strategy game, where your troops are Mechs. You spend your money buying new technologies, then assemble them into a design, and finally spend more money producing them in a factory and sending them off to capture enemy bases.
The interesting thing is that in battle, you don’t control them directly; instead you write programs to control them. The programming language is rather primitive, but it contains things to detect friendly or enemy Mechs, detect incomming missles, move in various directions, fire weapons in various directions, etc.
So yesterday (Feb 4, 1998) there was too much hail and ice to ride my motorcycle to school, so I walked in. On the way home, I got to thinking. That’s the problem with walking: you’re left alone with your thoughts. Anyways, I was thinking about the Carnage Heart video game (that’s the one that lets you program Mechs for battle). I was thinking about it’s computation engine, and whether you could do some traditional programming tasks on it, like computing Pi. After all, it’s Turing complete. So I started thinking about how I would do it. You have registers, which hold (I later found out) 3 decimal digits, and a sign. But, the only operations you have are add a constant, subtract a constant, multiply by a constant, divide by a constant, assign from a constant, and compare to a constant. The constants must be in the range 1 to 100 (inclusive), and there are no operations that involve two registers.
Now, there’s a really simple formula for Pi:
Pi/4 = 1 – 1/3 + 1/5 – 1/7 + …
A couple things crossed my mind. First, I only had 5 registers, so I could only compute a few digits of Pi. But wait! I have 3 mechs! And they can communicate! There are 5 different channels (1-5), each of which can send or recieve 5 messages (named after 5 colours). It wouldn’t be hard to use a single channel and transmit a number in base 5. So, that’s 15 registers at my disposal.
But a bigger problem is that there’s no (direct) way to take a reciprical. There isn’t even a direct way to add two registers. But this is where my theory of computing classes come in. If you want to add register B to register A, you can do (assuming B > 0):
foo: A = A + 1
B = B - 1
if B > 0 then goto foo
Of course, this destroys B, but you can make a copy of it before hand:
[Copy B to C and D, destroying B]
C = 0
D = 0
bar: C = C + 1
D = D + 1
B = B - 1
if B > 0 then goto bar
Now that you can add (or subtract) two numbers, you can compare them by subtracting the two and seeing if the result is positive, negative or zero. Or, equivalently, you can subtract 1 from each, and whichever gets to zero first is the smallest.
Then, you can do division by repeated subtraction:
[Calculate A / B, quotient in C, remainder in A]
C = 0
baz: if A < B then end [in practice, goto the first statement of the next step]
A = A - B
C = C + 1
goto baz
If you expand everything out, you can combine many steps. For example, the copy and subtract can be combined like this:
[A = A - B; C = B; B = 0]
C = 0
phat: A = A - 1
B = B - 1
C = C + 1
if B > 0 then goto phat
There are some other speedups you can do too. Instead of subtracting 1 all the time, you can do:
[A = A - B; B = 0]
phat1: if B < 100 then goto phat2
A = A - 100
B = B - 100
goto phat1
phat2: if B < 10 then goto phat3
A = A - 10
B = B - 10
goto phat2
phat3: if B < 1 then end
A = A - 1
B = B - 1
goto phat3
The ultimate in this vain would be a binary thing: compare to 512, 256, 128, 64, …, 1. You don’t even need the loop, since you only need to subtract each number at most once. (Actually, it’s hard to compare to numbers bigger than 100, since it can’t be done directly. Probably best to have a loop to get it under 100, then do the binary thing.)
Also, for division, you could do "if A > 10*B then A = A - 10*B, C = C + 10". Multiplying by 10 is built in, and you need to make a copy of B anyways.
Well, I wrote the program out on paper. It’s only for a single mech, and while I combined as many steps as I could, it doesn’t have any of the other optimizations. It should compute the first 2 or 3 decimal places of Pi (that is, 3.141 or pretty close). Who would have thought those theory of computation constructions could actually be used?? I haven’t implemented it yet, I’m waiting until I get the “best” CPU (fastest and largest program storage). Then I’ll try it. I’ll be curious to see how far it gets in the 150 second time limit. (Too bad I can’t let it run all night!) That series converges really slowly, especially if your variables only ever go up or down by 1 at each timestep!
I’m such a nerd.
Martin.
P.S. I eventually did implement it, and it didn’t even get a single digit, because the time for the match ran out.
P.P.S. The next step would be a multi precision, parallel communicating version. The above formula converges so slow, so it would have to be based on the Taylor series for arctan…
Created Thursday February 5, 1998
Martin C. Martin Email: martin at metahuman.org
Martin C. Martin 