For a while now I've been wondering whether it would be possible to build simple computer-circuitry in furcadia. Or more specifically I wanted to build a machine that would add two binary numbers by using a set of simple binary building blocks.
Chronicled here are the results of my experiments as well as examples of the various components and how they work as well as the schematics and explanation of my binary adder.
But first the six components that make up my 'computer'. First of all there are the 'wires' which will transport 1's and 0's to their rightful places. Then there are splitters and crossers that will perform simple tasks on the wires, like duplicating them and providing a way to cross wires. And finally there are the three binary ports that are needed to build our adder.
The wires are the heart of the system. They move the bits to all the right places. Fortunately they're very easy to build. If a particular wire-square is empty, it will just perform a swap with the tile before it and move any content there along the wire.
A short wire from (10,10) to (12,12) would require the following dragonscript in that case:
Note that I have constructed the wire from the back to the front. Though the other way around will work as well, this one looks better as the numbers will move one space a second. If you do it the other way around, it will rapidly shoot the numbers along the wire as something at the beginning of the wire will move to the second spot, and then immediately be moved from second to third. And so on.
It happens at times that we want one stream of numbers to go into two different directions. That's what the splitters are for. They all take one input and two outputs, producing a duplicate of every bit passing through it.
This is a fairly easy thing to do. We just check whether the outputs are empty and whether the input is non-empty (though technically the last isn't really needed), and if they are we just copy the input to both output-locations and then remove the original.
The code-example here assumes that the split is at (10,10), with the input at position (10,11) and the outputs at positions (10,9) and (12,11).
I am aware that my code is not always the most efficient, as the following variant would perform the exact same task, but I prefer to have it readable instead of just short. Not to mention that leaving out the (1:1014) line might affect the efficiency after all as the input is often empty, in which case the one above will stop evaluating at the second line of the script, but the bottom one would continue copying empty space.
Unfortunately it's sometimes required to have one wire cross another. That's what the 'crossing' is for. For both directions it has an input on one side and an output on the other. All it does is move anything that appears on the input to the output side, thus 'crossing' the other wire.
The dragonspeak for it is easy. For a crossing at (10,10) with the first wire entering at (10,9) and coming out at (12,11) and the second wire entering at (10,11) and coming out at (12,9), the dragonscript will be as follows.
The NOT port
The NOT port (depicted to the right) has only one input and one output. All it does is flip the input to the other value, so a 1 becomes a 0 and a 0 becomes a 1.
Now one way we could do this is by checking whether the input is a 1 and place a 0 at the output position (provided it is empty) or, when the input is a 0, place a 1 at the output position. There are a few tricks we can apply here though.
We still need the check whether the output location is empty (though we don't necessarily need the check that the input location is not empty). Then we just move the input to the output location and perform a swap between the 0-object and the 1-object. This will turn 0s into 1s and 1s into 0s as well.
This leads to the following dragonscript for a not-port at (10,10) with the input at position (10,11) and the output at (12,9). (It's the same layout as the example image above)
The OR port
Now it's time for the more fun stuff. The OR port has two inputs and will produce a 1 on the output if either or both of the inputs is 1. Otherwise it will output a 0.
We could make four case-distinctions in dragonscript, one for each possibility on the inputs, but let's try something a bit more fancy. If there's a 1 on one input, it doesn't even matter anymore whether there's a 1 on the other. Now we're going to use this to our advantage.
We're just going to copy the first input to the output and then, based on what the second output looks like, we're going to adjust it so that it provides the correct answer. If the second output is a 0, we will just leave it the same (the first input is the decisive one in that case), but if it's a 1, we will replace the output with a 1 instead as we know for sure that the answer is one, no matter what the first input was.
For an or-port at position (10,10) with the inputs at (10,11) and (12,11) and the output at (12,9) the following dragonscript would be needed. Here objects 2400 and 2401 are the 0 and the 1 respectively. (note the use of the variable to link the three separate statements together)
The AND port
Now there's only one more port left and that's the AND port. Similar to the OR port, the AND port has two inputs and one output. Unlike the OR port however, it requires both inputs to be 1 before outputting a 1 itself.
Constructing it is very easy though, as we can follow about the same approach as the OR port, with only a few things altered. For an and-port at position (10,10) with inputs at (10,11) and (12,11) and an output at (12,9), the dragonscript becomes:
The binary adder
And now the time has come to build something more interesting from the building blocks above. To make it a bit of a challenge we're going to build a binary adder which can handle any number of bits. First let's take a look at how addition works.
When adding two numbers (for example 126 and 37) you will first add the 6 and the 7, end up with 13, so you write down a 3 and carry the 1. You add the 2 and the 3, add the carry and end up with 6. etcetera etcetera.
The same process is a lot easier in binary. The only possibilities you have are:
- 0 + 0 = 0 (carry 0)
- 0 + 1 = 1 (carry 0)
- 1 + 0 = 1 (carry 0)
- 1 + 1 = 0 (carry 1)
Well look at that. Doesn't that pattern for the carry look awfully familiar. You're right. It's the AND port. So to calculate the carry for the addition, we can just AND the input.
Unfortunately the result of the addition isn't as easy. It looks kinda like an OR, but the last value is out of line. But all is not lost as we might be able to simulate it by combining a few of the ports.
We could AND it with a pattern that gives us 1's in the first three places, but we don't have that function either. But we do have an AND that does exactly the opposite. So combining this with a NOT will give the function we want.
Now we just combine it with an AND and we will have the result we're looking for.
|A||B||A or B||A and B||not(A and B)||not(A and B) and (A or B)|
So let's do some fancy wire-work and connect the ports in the right ways. This gives us the following piece of machinery more commonly known as a half-adder.
Unfortunately we're not quite done yet, as we might have a carry lying around from the previous addition. This however is far easier as we can just use the half-adder again, this time to add the result of the first half-adder and the carry we still had.
Now there's one final matter we need to solve and that is to prepare the carry for the next cycle of the machine. We have two carries now, one from the addition of A and B and one of (A+B) and the carry. With some thinking you can figure out that only one of the carries can be 1, so we can just or them and then feed them back into the machine. The final machine looks like this in that case:
Notice how there's already a zero inside the machine. That's the initial carry needed to perform the very first addition. It's very important as the machine will stall otherwise before even producing its first bit.
At this point we will have to add the dragonscript for all the components (wires/ports) and provide two streams of numbers into the input ports and we'll have ourselves a binary adder.
See it in action
Ofcourse I wouldn't be trying to explain it all if you didn't get a chance to see it in action, so down below you can download the dream and try the various components out yourself.