[Project] Binary to Decimal Converter (Double Dabble Method)

[DicemanX]

For me the Holy Grail of Terraria engineering was to find a way to convert from binary to decimal. The search has ended .

After some major inspiration earlier today I finally came up with a way to do the conversion. I posted how to convert from BCD to decimal previously, and I was able to work out a good way of converting from binary to BCD. Here's the entire converter:


Video:

I demonstrate conversion three times in the video. Each time I convert, I input the number in binary in the register first, then pull a lever to initiate the entire process. Once I finish, I pull the other lever to clear everything.



Pictures:

Explanation:

The converter consists of two mechanisms. The first converts from binary to BCD, and the second converts from BCD to decimal.

The process begins with a binary number stored in a register at the bottom right of the mechanism. Lights below the numbers 1, 2, 4, 8, 16, and 32 indicate what number is stored there, so if for instance 32, 8, and 1 are lit up, the number 32+8+1 = 41 is stored in the register.

There is a pair of wall levers near the middle right (to the right of the rightmost black display). The left lever is the clear function, turning off the 7-segment displays and turning off the numbers stored below. The right lever automates the entire conversion process from binary to decimal.

The mechanism to convert from binary to BCD is the double dabble mechanism:

http://en.wikipedia.org/wiki/Double_dabble

The algorithm is as follows:
1) if a number greater than 4 is stored in any of the 4-bit BCD displays after the shift, then 3 is added to that number.
2) double the number stored in the register (effectively shifting what's stored in each bit to the left)

Steps 1 and 2 are repeated N times, where N is the number of bits in the original register. Since my build has a 6-bit register, I need to shift 6 times.

The long track just below the two 7-segment displays is the shift mechanism. below each 7-segment display is a look-up table - if the numbers 5, 6, 7, 8, or 9 are stored in the BCD display for each digit, then 3 is added to those numbers. Each of those five values dictates what path the skeleton will take in the look-up table.

Once the double dabble protocol finishes, the BCD to binary converter kicks in. I presented this mechanism previously:

http://forums.terraria.org/index.ph...ecimal-converter-with-7-segment-display.8763/

The mechanism at the bottom right corner is a counter - it ensures that the skeletons will pass through the converter 6 times.

This converter is fully expandable. More BCD displays can be added to the left, and more BCD coverters can be added directly above as well. The starting register can be likewise expanded easily.



The best way to fully understand what's going on is to download the world that contains this converter and watch it in action.


World Download:

http://www21.zippyshare.com/v/niNq93OZ/file.html



Challenge for the group:

The display needs to be improved. The two 7-segment displays are in awkward positions. If I place them on top of the entire contraption that would allow me to squeeze them closer together but then I'd be too far from some of the skeleton paths and the skeletons would start despawning while the mechanism is running. I'd like to know if this entire mechanism can be improved/compressed.

There is also a slight problem converting any of the digits to a 5. If you download the world you'll see exactly why. There's a transition from one horizontal hoik track to a hoik track above it that results in a slight delay. I want to know if there's a better way to do the transition.

 

[ZeroGravitas]

the Holy Grail

Yes indeedy! By far the most logically complex machine ever made in game and the hardest part of any basic binary computer/calculator. The mechanism to directly shuffle the bits to the left is inspired. I'd been thinking of bouncing back and forth between two temporary registers, but it would have been an ugly mess (that didn't work), or a series of N registers (massive).

I haven't really grokked how the ">4" lookup tables work precisely. Is it a straight case of looking up all eventualities?: i.e. one row for =5, another for =6, =7, =8, =9? And then then the plate line selected dictates the state update for that BCD section? How does this carry out to the next BCD section?

There is also a slight problem converting any of the digits to a 5

Which component are you refering to exactly (might manage a look some time, although I'm sure you could figure something out quicker these days ).

All in all, it's very impressive! Far faster and more elegant than your count-up conversion (although infinitely more bewildering and a little less mesmerizing lol). It's great that it looks so simple to extend out from this design (very modular), although, like you say, the despawn problem... May have to bite the bullet and go full NPC on these designs soon, with all the added complications that brings.

 

[DicemanX]

Yes indeedy! By far the most logically complex machine ever made in game and the hardest part of any basic binary computer/calculator. The mechanism to directly shuffle the bits to the left is inspired. I'd been thinking of bouncing back and forth between two temporary registers, but it would have been an ugly mess (that didn't work), or a series of N registers (massive).

Surprisingly the ALU was easier to build because there was at least a blueprint to work from. The converter on the other hand...there was just the algorithm to start with.

That inspiration I mentioned pertained to the shift mechanism. I too was thinking about ways of shuffling between registers, using the method of multiplication from the ALU, but it soon became a nightmare to combine it with the BCD display checker for numbers above 4. It then dawned on me that I shouldn't bother with any of that and just use a simple feedback mechanism.

I haven't really grokked how the ">4" lookup tables work precisely. Is it a straight case of looking up all eventualities?: i.e. one row for =5, another for =6, =7, =8, =9? And then then the plate line selected dictates the state update for that BCD section? How does this carry out to the next BCD section?

Yes, it's a look-up for all possible numbers in the BCD display after a shift (5, 6, 7, 8, 9). Here's the gist:

If neither 8 nor 4 is ON, the skeleton passes straight through horizontally.

If 8 is on, it actuates the bottom hoik at the start, sending the skeleton up and across a horizontal track (topmost track) that switches the number from 8 to 11. If 1 is ON as well, it sends the skeleton to one track lower (2nd from top track) to convert from 9 to 12. If 8 is OFF but 4 is ON, the next bottom hoik tooth is actuated, sending the skeleton up in the next vertical column. Then:

If neither 2 nor 1 is ON, the skeleton moves immediately right and then down, eventually going down the path when neither 8 nor 4 is ON.
If 1 is ON, the skeleton proceeds across the track second from the bottom to convert a 5 to an 8.
If 2 is ON, the skeleton moves to the track 4th from the top to convert the 6 to a 9.
If 2 is ON and 1 is ON, the skeleton moves to the track 3rd from the top to convert the 7 to a 10.

I was going to also try to build an adder instead of a look-up table to see if that would be better, but since the look-up table turned out to be relatively small I refrained from working on this part further.

Here's how the whole converter is chained:

1) The initial pull of the lever sends a skeleton through the counter (bottom right) which will only allow 6 passes through the entire mechanism (since register is 6-bit).
2) From the end of the counter track the skeleton is teleported into the first look-up table (for the TENS BCD display).
3) When the skeleton reaches the end of the first look-up table, it hits a pressure plate that summons a skeleton into the next look-up table (for the ONES BCD display).
4) When the skeleton reaches the end of this look-up table, it activates a pressure plate that summons a skeleton into the shifter (the long horizontal track in the middle of the mechanism).
5) When the skeleton reaches the end of the track it hits a pressure plate to summon a skeleton in the counter, repeating the loop.

Once 6 skeletons pass through the counter, the seventh is prevented from proceeding because it hits a previously out-of-reach pressure plate linked to a teleporter. The seventh skeleton ends up being teleported to a different location, where it activates skeletons to run through the BCD to decimal converters above.

Which component are you refering to exactly (might manage a look some time, although I'm sure you could figure something out quicker these days ).

The problem component is in the BCD to decimal converters, but only if the player is positioned below and to the right of the converters (there's no problem when the player is on the other side).

Specifically, the problem is in the transition from the track 6th from the bottom to the track 5th from the bottom:

If you look at the top two tracks, the actuated blocks with blue wiring that open the path from the track 2nd from the top in the pic to the topmost track are creating an issue. The transition is not smooth - the skeleton hangs momentarily before finally being forced up by an up hoik and then proceeds smoothly to the right along the topmost track.

EDIT: the problem only arises at night. During the daytime all transitions are smooth.

All in all, it's very impressive! Far faster and more elegant than your count-up conversion (although infinitely more bewildering and a little less mesmerizing lol). It's great that it looks so simple to extend out from this design (very modular), although, like you say, the despawn problem... May have to bite the bullet and go full NPC on these designs soon, with all the added complications that brings.

Yeah the next step will be to convert from skeleton to character NPC to make this bigger and to put the 7-segment displays at the top of the BCD converters, not the bottom, so that the displays can be squeezed together. Converting from skeletons to character NPCs is going to be nightmarish to say the least, because teleporting into a hoik can lead to annoying misalignments in look-up tables. Still, it will have to be done at some point.

 

[DicemanX]

OK so the problem with the transition from one horizontal track to the next higher track has been addressed:

Wiring:

On the left is the new transition, and on the right is the old transition. The two blocks above the top hoik can be actuated via the blue wire to change it into an up hoik. All those extra top hoik teeth in the top track seem to be necessary to avoid the skeleton getting stuck daytime or nighttime.

So now there are two things to work on:

1) Expanding the set-up to include more digits (easy)
2) Converting the signaling from skeleton to character NPC (hard)

EDIT: almost done converting from skeleton to character NPC for signaling. Was much easier than I thought - I'll post an updated version once it's done.

 

[ZeroGravitas]

Still, it will have to be done at some point

For 'science'!

the problem only arises at night

When the skeleton AI is set to follow player, where-as they are passive during day. Also they try to jump up platforms at night. I don't know if their movement speed is any different too...?

(Reads next reply...) Arh, you got it. Yeah, I had to use that twin tooth configuration for my hoik switches in my "top-hoik binary counter". Messy, but necessary. The skeletons only get lifted up onto the lower part of the slope in your previous setup, which isn't high enough to reach the next hoik tooth, above. Similar to the down hoik problems.

Converting the signalling from skeleton to character NPC (hard)

....and it's done.

Edit: oh, am I looking at your diagrams the wrong way around, did you say it the correct way around?: left vs right?

 

[DicemanX]

So here's the slightly reworked version for character NPCs:

Works fine with a character NPC. I still have the option of putting an NPC in a house instead of using the King Statue and adding teleporters at the end of the clear and coversion sequences so that the NPC will teleport back to the house.

There are down hoiks which lead to the teleporters below to continue the chain of events, but unfortunately the NPC isn't hoiked all the way to the end. Instead, the NPC has to fall out of the hoik near the end and just fall into the teleporter to avoid issues past the next teleporter. This doesn't affect latency all that much, but it would still be nice to improve that part if possible.

Now the next step is to expand this to include a third digit, and move the 7-segment displays on top of the structure so that they can be squeezed together.

Edit: oh, am I looking at your diagrams the wrong way around, did you say it the correct way around?: left vs right?

Is this in reference to anything specific I mentioned before? I couldn't find any instances where I might have mistaken left/right.

 

[ZeroGravitas]

Is this in reference to anything specific I mentioned before?

On the left is the new transition, and on the right is the old transition.

 

[DicemanX]

Ah I see - yes on the left was the new set-up that worked much better than the set-up on the right.

 

[DicemanX]

OK, managed to accomplish all my starting goals. The updated version:

Without wires:

I expanded the converter to 9 bit, which means it needs to cycle 9 times. I also constructed it so that expansion of the binary to BCD and BCD to decimal can be easily done in seconds in TEdit by extending leftwards. The memory register is also expandable to the right, and along with it the counter in the bottom right corner.

The 7-segment displays can now be side by side in this new set-up as they are meant to be.

I use a King Statue for now, but I can also very easily add a player house and teleport the character NPC from the house directly, and return the NPC to that house via teleporters at the end of both the clear function and the converter function (currently the NPC is left stuck at the end of both, because it isn't necessary to teleport them anywhere - the King statue retrieves the NPC wherever it is in the world).

I'm really happy with the final product, but now I want to see if it can be improved. Maybe some compression is still possible, and maybe the conversion can be sped up especially at the drops into teleporters in all of the look-up tables. It's really risky to use a down hoik straight into a teleporter, since it might push the NPC into the ground and cause it to be stuck, but maybe there's a way to do it so that it works consistently.

Quick note about the counter: it is essentially a very compact MQ register that is set to repeat an action 9 times. However, it can also be altered so that you can input how many times you want the function repeated. It works through a basic feedback mechanism - when the NPC passes through the track the first time, it hits a pressure plate at the end and gets teleported to the rest of the mechanism. That pressure plate also switches a top hoik to a bottom hoik earlier in the track, which means the second time through the counter the NPC will be able to hit a pressure plate immediately before the final pressure plate. That second-to-last pressure plate that is now activated the second time through flips between another top hoik/down hoik pair, allowing access to the third-to-last pressure plate. Eventually, access is granted to a pressure plate that teleports the NPC away without allowing it to go down the rest of the track.

So, mission accomplished - we now have a full binary to decimal converter that can be as large as we want.

Next major project: converting from decimal to binary.



World download:

http://www18.zippyshare.com/v/ZA7vqIdf/file.html

(The current set-up is to the left of the spawn point - I still have many previous iterations all over that world just in case).

 

[ZeroGravitas]

Next major project: converting from decimal to binary.

What, this isn't naturally reversible?! What twaddle! Give people miracles and they'll take them for granted.

So. You could use the sequential counter as a type of progress bar, as it directly indicates how many more steps left in the conversion, right?

Regarding the down hoiks (in the display drivers, right?): you've opened up space to the side to allow the NPCs to drop, rather than get jammed, right? (Because the length is fairly long and they walk out to the side, as I've observed.) Can you just put a single horizontal hoik step (to the right) in half way down the length, to reset the NPC's alignment? (Lengthening all the lower lookup tables one step to connect.)

Then also have a horizontal last step to the teleporter? (Or would that not help?)

Alternatively, simple have teleporters at the end of each row, on a single wire, as they should all send to the most distant connected pad. Cut out the down hoik altogether. (If you're going to use them, make the most.)

 

[DicemanX]

Alternatively, simple have teleporters at the end of each row, on a single wire, as they should all send to the most distant connected pad. Cut out the down hoik altogether. (If you're going to use them, make the most.)

Brilliant mate! I should learn my lesson and not try to down hoik when I can just use teleporters. I scrapped all down hoiks and replaced them with teleporters and now the conversion is even faster. Good suggestion! I'll post the updated version in a little bit.

So. You could use the sequential counter as a type of progress bar, as it directly indicates how many more steps left in the conversion, right?

Yes, I could engineer that too by connecting a set of lights to the plates in the counter. For now I just monitor the progress in the minimap, watching the little NPC whiz around .

EDIT:

Here it is:

Latency improved quite a bit - it takes about 15 seconds to do any conversion, so that's around 1.6 seconds per cycle. Now it's just a question of whether a further compression is possible. Your reset mechanism certainly helps in this build!

I left the down hoik in the final BCD to decimal converter because by that point the NPC has nowhere else to be. When I use a house then I'll add the teleporters so that the NPC can be shifted back to the house.


World download:

http://www11.zippyshare.com/v/6qiwC4RN/file.html

 

[ZeroGravitas]

a question of whether a further compression is possible

Have you experimented with over-compressing the look-up lines vertically? This may sound like madness, but only one plate can be hit per tick, and it should always be the top one (I think). So, offset all the plates one tile to the right (in line with the gap between teeth), then move them all up one into those gaps (and the solid block below, of course). You would then need to have dummy plates in every position too (to stop the plate below getting triggered when there isn't one above), and determine their logic by extending a wire to them, or not.

I think I might have suggested something line this before...? Just try testing it, even though re-constructing the row selector might be a bit of a pain thereafter (or practically impossible)...

Also, for a slight speed-up, you could bridge the 5-6 step spaces between logic on the bit-shift line with teleporters...

All in all, it's looking really pretty good. Well laid out in modules that you can point to and label their functions fairly succinctly.

 

[DicemanX]

Have you experimented with over-compressing the look-up lines vertically? This may sound like madness, but only one plate can be hit per tick, and it should always be the top one (I think). So, offset all the plates one tile to the right (in line with the gap between teeth), then move them all up one into those gaps (and the solid block below, of course). You would then need to have dummy plates in every position too (to stop the plate below getting triggered when there isn't one above), and determine their logic by extending a wire to them, or not.

What about the up hoiks? Wouldn't I need to maintain a spacing of 2 blocks in between teeth? I know that you can mix 1 and 2 spaces and have it still work but is there a way to to compress the entire look-up table so that every track is two spaces high? And yeah the track selection might be a pain but if I can get the up hoiks to reach every possible horizontal track then I can proceed to work on track selection.

Also, for a slight speed-up, you could bridge the 5-6 step spaces between logic on the bit-shift line with teleporters...

Yes, I'll do that at some point, as it should save a couple of seconds overall.

All in all, it's looking really pretty good. Well laid out in modules that you can point to and label their functions fairly succinctly.

Yeah the layout turned out nicely. I was really worried the converter would end up being huge after seeing the converters in minecraft. It's pretty remarkable that for all the extra tools and extra dimension in minecraft we're still able to do certain things more compactly in Terraria .

 

[ZeroGravitas]

What about the up hoiks? Wouldn't I need to maintain a spacing of 2 blocks in between teeth?

Like you say, you can do alternate: 2, 1, 2, etc, and perhaps other fiddly tricks.

I remember now proposing doing a similar over compression trick with vertical lookup columns (making them 1 tile wide), or did I? (Because there's no way to selective wire plates vs dummy plates... Yeah.)

So anyway have you given it a go yet? No rush of course.

 

[DicemanX]

Like you say, you can do alternate: 2, 1, 2, etc, and perhaps other fiddly tricks.

I remember now proposing doing a similar over compression trick with vertical lookup columns (making them 1 tile wide), or did I? (Because there's no way to selective wire plates vs dummy plates... Yeah.)

So anyway have you given it a go yet? No rush of course.

I put it on hold for the moment, since I decided to work on uniting the converter to the ALU. I also removed the King statue and constructed an NPC house so I could move the whole thing into my main world. Now I'm just trying to improve the looks of the whole thing before I shoot the video.

I added two neat mechanisms to the whole set-up:

1) Wire color converter (uses my version of the reset mechanism; I needed this because the ALU accumulator register uses same color wires and the converter uses alternating colors)
2) NPC house with built-in teleporter selector (the NPC gets hoiked to a different teleporter depending on the input; necessary to enable both a clear function and conversion function)

A quick preview:

 

[DicemanX]

Had a brainwave - managed to connect the converter to not just the accumulator register, but also to the MQ register. This means that I can display the outputs of multiplication, addition, and subtraction from the accumulator register, AND division from the MQ register. Idea came right in the middle of video editing, so now I need to shoot a new video. Here's a pic of the set-up:

Hideously complex wiring, which I'll show once the video + guide are up! The ALU is also pretty small compared to the binary-to-decimal converter. Still, I'm pretty happy with the outcome, especially that everything is fully automated - once the lever is pulled to start a calculation it culminates with the answer displayed in decimal on the big board.

EDIT:

OK, video + guide have been posted!

http://forums.terraria.org/index.ph...ed-computer-binary-to-decimal-converter.9965/