We’ve got something special for you: a guest post by Andrew Pritchard, who has made a few binary calculators in N. He’s written an awesome, in-depth summary of how binary addition works and how he implemented it in N, and we had to share it with you all because of how incredibly cool this is. So without further ado, take it away, Andrew!

————————————-
Hello,

I’ll say this one straight off the bat, but unfortunately, it’s not a completely original idea. I saw a similar map (years ago) on NUMA for a 4 bit binary adder, but I had no idea how it worked, the two maps that I made for addition are quite different to the system used previously, and this design is completely my own. The map is nowhere to be found as far as I can tell, so I decided to create one for Nv2 online so that people may be able to see it in the future. You can find the map for my 8 bit binary adder here (Map 105920).

If you don’t know how binary addition works, wikipedia has a good introduction!

So how to use the level? Hit the switches at the beginning for every digit you want to change from 0 to 1, there is one additional switch at the very start to add an extra 1. This is called “carry in” or Cin for short. Go through the level to the finish to get your answer. To add numbers longer than 8 binary digits, input the last 8 digits of your two numbers, and leave the Cin switch alone. The most leftmost digit (“carry out” or Cout for short) of your answer becomes the new Cin for the next addition. Add the next 8 digits of your numbers plus the new Cin and don’t forget to record the carry for the next 8 digits.

For subtraction, take the two’s compliment of the number you want to subtract and then add it to the the other number.

Why did I make this level? The reason that I revisited the concept was because I was wondering if certain games were turing complete, i.e. able to perform any calculation, and simulate any computer. Minesweeper, for example is turing complete, and I believe Super Mario World is too if you edit the levels to your needs. With n’s level editor and complex system of doors and gates, I thought n would be too. I believe n is turing complete (if the map was infinitely large), making it possible for N to simulate a game of Minesweeper, or Super Mario World, or even N itself! For those technologically minded: rule 110 or a 4 state 6 symbol turing machine would be the easiest to implement, and I have a design for rule 137 (which is equivalent to rule 110) in the pipeline.

Addition is also the most complex arithmetic instruction to be performed on many 8 bit CPUs, allowing for complex arithmetic. Multiplication should also be able to be performed in a game of N, however, I found the level size was too constricting.

Before reading any further, it will make it a lot easier if you understand what a half adder and a full adder are.

So here’s the how: First of all a signal of 1 in the adder is considered to be hitting a switch. if no switch is hit, the logic defaults to zero. The first map I made was *relatively* straightforwards. n moves from right to left in the image. For a full adder, we need to add two digits (called A and B) and Cin (carry in), and each of those values can be 0 or 1, meaning 2*2*2 = 8 input possibilities. The image below shows one full adder, it is 8 blocks high, allowing for all 8 possibilities. Only one path out of 8 will ever be open (however my map has a glitch, and kudos to whoever finds it!):

Whenever A, B or Cin changes from 0 to 1 by hitting a switch, (let’s say A for now) half of the 8 possibilities are blocked off using doors (corresponding to A = 0, we’ve hit the switch so that A is now 1, so we don’t want n going through the any box corresponding to A = 0), and the other half are opened using gates (corresponding to A = 1). The switch on the far left corresponds to Cout for the next full adder. The 8 switches in the middle column will display a 0 using doors, or a 1, by leaving it alone.

The next adder is a bit more complicated, and this calculator for addition of one is a simplified version. I used this schematic using only XOR and NAND gates to create my calculator.

We need two XOR gates (numbers 1 and 4) and three NAND (numbers 2, 3, and 5) gates to get the result we want. Here is a NAND gate in n, n goes from top to bottom:

NAND gates only output 0 if both inputs are 1. Both of the switches at the top control a gate on the left, so they must both be hit (input of 1) in order to go to the left (output of 0). n will normally go to the right (output 1), because both doors will be open by default if you leave them alone (input of 0). n has to hit (1) both switches for the path to be blocked off on the right. When n hits the switch in front of the one way door (1), it codes for an input of 1 for the next logic gate, or displays a 1 at the top of the level. If n does not hit the switch behind the one way door, by going to the left (0), the next logic gate will assume that the input is 0 instead, or the top of the level will display a 0 (the 0 is already there, so by not doing anything, the 0 stays)

Here is a XOR gate, n goes from top to bottom:

​XOR gates are a bit more complicated and will output 1 if and only if both inputs are different. You can’t see it very well in the screenshot but the left side (0) is open if n leaves the two input switches alone (0). If he hits one, a door will block of the path to the left (0) and open a path to the right (1). If n hits (1) both switches, the path to the right (1) becomes obstructed, and the path to the left (0) become open again.

The final challenge is to wire everything together, but copy and paste makes light work of it. n has to go from right to left because that’s the way the carry propagates.

Anyway, happy adding, and for those who haven’t already, try out Ned for yourselves to create your own unique pieces of art in N!

Well, I hope this was an entertaining read, and congrats to Mare and Raigan for making a game that can simulate itself, making N a truly meta game.

————————————-
Thanks very much, Andrew, for sharing your process and for doing such a creative thing in N!