Editing User:Larix/Adder

Using mechanical logic and applying the principles shown by Jong, an extremely compact full adder can be built which functions similarly to a carry look-ahead adder, but thanks to the immediate operation of mechanisms in Dwarf Fortress can calculate all carries of an arbitrary-size addition in a single tick. 

 O1-SPABC-O2
        X
        c

P = Power

A,B = gear assemblies connected to the A and B inputs, active when the signal is on

C = gear assembly generating the carry output for this bit. The gear is not linked to any inputs and presence of power on it serves as carry input for the next higher bit.

X = a single gear assembly, connected to both A and B inputs, pre-toggled. It transmits power if one and only one of the inputs is on (an XOR gate).

c = carry input from the next lower bit. Like the output, an unconnected gear, presence of power on the gear serves as carry input.

S = the sum calculation, consisting of a single gear, connected to the A and B inputs as well as a signal generated by the carry input, pre-toggled. It transmits power when exactly one or three of the inputs are on. 

O1 = power-to-signal converter or other output device to generate the sum output

O2 = output generating a signal from the carry, required to calculate the next higher bit's sum.

A carry is generated at a bit only when both A-line and B-line input are on. An active carry will be passed to the next higher bit if one and only one of A and B inputs are on; if both A and B are on, the carry will simply be generated again, the "X" gear will be disengaged and will not transport power. This easily prevents higher-bit carries erroneously flowing down the bit chain. All carries are effectively generated by providing power links between the power sources and the carry gears, i.e. they're present the moment the connecting gears get switched, without any further processing required. The logic conditions for an active carry are (A AND B) OR (CARRY_IN AND (A XOR B)). The carry calculation doesn't distinguish between active and inactive carry input when both A-Line and B-Line input are on, and in fact this distinction is irrelevant for carry calculations. Likewise, the sum calculation only checks whether an even or odd number of the inputs (A, B and Carry-in) are active, the exact number doesn't matter and is ignored.

* This adder takes a mere five installed gear assemblies per bit - four for the carry calculation and one for the sum. Additional mechanisms and machinery are required for power supply, signal generation and linkage. 

* Linking an extra lever to all inputs of the "A" line in the carry computation allows to use this adder for subtraction as well. In this case, the logical conditions for a carry are (NOT-A AND B) OR (CARRY_IN AND (A NXOR B)): if the A-Line (Diminuend) input is off (zero) and the B-Line (Subtrahend) input on (one), the carry output is active, regardless of the status of the carry input (the possible results at the bit are 0-1-0 = -11 and 0-1-1 = -10, and the carry output only tracks whether the result is positive or negative; both possible results are negative, so the carry-in status simply doesn't matter). If the carry input is active and A and B have the same value, the carry is passed on (0-0-1 = -11 and 1-1-1 = -11).
Negative results can be displayed either in the standard computing convention of reserving the highest bit for the negative numbers, wrapping around from 11..11 = -1 to 00..00 = 0, or by sending an additional "minus one" signal to the circuit and reversing the logic of all sum calculators apart from the lowest-bit one by sending an extra signal to generate the binary complement.

Forum post featuring this adder:
http://www.bay12forums.com/smf/index.php?topic=15096.msg4600870#msg4600870

less economical "fully mechanical" version:
http://www.bay12forums.com/smf/index.php?topic=15096.msg4602227#msg4602227

P.S.: Further optimisation is possible, to make it even more space- and power-economical. The carry gear can be replaced by a roller running a minecart-based power-to-signal converter, saving three points of power requirement and removing the need for a dedicated "output" machine - a single-tile roller transmits power in all four compass directions on the same z-level, which is all we need here. The power train can consist mostly or entirely of rollers and axles. The track for minecart power-to-signal converters can be carved/laid under gears and axles without hindrance, allowing to minimise space consumption. The smallest, least power-hungry construction i've managed to install can add and subtract 16-bit numbers and takes up 205 tiles of open floor, plus 32 for required surrounding walls which could be shared with neighbouring adders and has a nominally installed power pull (before establishing the actual links) of 459; when properly linked and operational, the theoretical maximum consumption is 379. This breaks down to 14 tiles and 24 power per bit in an optimal configuration. The adder is contained on a single z-level and all sum and carry signals are generated within the mentioned area.
@@ Line 1: / Line 1: @@
+Using mechanical logic and applying the principles shown by Jong, an extremely compact full adder can be built which functions similarly to a carry look-ahead adder, but thanks to the immediate operation of mechanisms in Dwarf Fortress can calculate all carries of an arbitrary-size addition in a single tick.
-I do not claim credit for the concepts presented here. I may have been the first to actually build the first schematic and fully optimised the second, but used ideas and concepts worked out by others, of special note being Jong.
-=== Optimised for performance ===
-The core design can be used to build a mechanical adder that instantly generates the correct sum output, without intermediate steps. All credit for that achievement has to go to Jong (and maybe other posters for discussion input). The incredibly clever trick is that the sum at each bit can also be calculated as:
-A = B and Carry-in
-or
-A != B and no Carry-in
-The basic gear pattern is capable not only of calculating all carries and providing them as power output, but also of calculating all "no-carries", and similarly outputting power if no carry is sent. This evidently requires two carry-calculation assemblies, one for positive and one for negative, sending power or no power to two separate input-operated "summation gears". The gear which is driven by the carry input is engaged when A and B input have the same value, the gear taking power (if present) from the no-carry input is engaged when A and B inputs have different values. Both summation gears can work on the same power-to-signal converter.
-This design generates the actual sum of the addition instantly, at the cost of a significantly higher component count. But for the central adding machine of a substantial dwarven computer, instant results should be worth the price.
-'''Jong brought up and in fact finalised this design.''' The complete schematic can be found on page 18 of Jong's dwarfputer design document, although it was not used in his dwarven computer:
-https://docs.google.com/document/d/1b7NN-ZGpBMggiVSkSpW499MdCNCpwccL-RA9HKLZ5NU/edit?pli=1
-=== Optimised for minimum size ===
-Alternatively, an extremely compact full adder can be built. All carries are calculated instantly, the sum output is correct after about 120 steps, since the design uses internally-generated signals as summation input and regularly triggers temporary false positives.
   O1-SPABC-O2
@@ Line 46: / Line 25: @@
 * This adder takes a mere five installed gear assemblies per bit - four for the carry calculation and one for the sum. Additional mechanisms and machinery are required for power supply, signal generation and linkage.
-* The adder can easily be expanded to also serve for subtraction. It only requires inverting all inputs from A in the carry chain. Converting numbers into their binary complement can also be included into the device, mainly by additional switch logic; the only additional building required is one gear assembly for the entire machine.
+* Linking an extra lever to all inputs of the "A" line in the carry computation allows to use this adder for subtraction as well. In this case, the logical conditions for a carry are (NOT-A AND B) OR (CARRY_IN AND (A NXOR B)): if the A-Line (Diminuend) input is off (zero) and the B-Line (Subtrahend) input on (one), the carry output is active, regardless of the status of the carry input (the possible results at the bit are 0-1-0 = -11 and 0-1-1 = -10, and the carry output only tracks whether the result is positive or negative; both possible results are negative, so the carry-in status simply doesn't matter). If the carry input is active and A and B have the same value, the carry is passed on (0-0-1 = -11 and 1-1-1 = -11).
+Negative results can be displayed either in the standard computing convention of reserving the highest bit for the negative numbers, wrapping around from 11..11 = -1 to 00..00 = 0, or by sending an additional "minus one" signal to the circuit and reversing the logic of all sum calculators apart from the lowest-bit one by sending an extra signal to generate the binary complement.
+Forum post featuring this adder:
+http://www.bay12forums.com/smf/index.php?topic=15096.msg4600870#msg4600870
-Further optimisation is possible, to make it even more space- and power-economical. The carry gear can be replaced by a roller running a minecart-based power-to-signal converter, saving three points of power requirement and removing the need for a dedicated "output" machine - a single-tile roller transmits power in all four compass directions on the same z-level, which is all we need here. The track for minecart power-to-signal converters can be carved/laid under gears and axles without hindrance, allowing to minimise space consumption. Optimising for minimal space and power consumption, i built an adder/subtracter working on 16-bit numbers, which takes up 205 tiles of open floor, plus 32 for required surrounding walls which could be shared with neighbouring adders and should not pull more than 380 power in operation. This breaks down to 14 tiles and 24 power per bit. The adder is contained on a single z-level and all sum and carry signals are generated within the mentioned area.
+less economical "fully mechanical" version:
+http://www.bay12forums.com/smf/index.php?topic=15096.msg4602227#msg4602227
-Demonstrated in its full cluttered glory here: http://www.bay12forums.com/smf/index.php?topic=135141.msg4884365#msg4884365
+P.S.: Further optimisation is possible, to make it even more space- and power-economical. The carry gear can be replaced by a roller running a minecart-based power-to-signal converter, saving three points of power requirement and removing the need for a dedicated "output" machine - a single-tile roller transmits power in all four compass directions on the same z-level, which is all we need here. The power train can consist mostly or entirely of rollers and axles. The track for minecart power-to-signal converters can be carved/laid under gears and axles without hindrance, allowing to minimise space consumption. The smallest, least power-hungry construction i've managed to install can add and subtract 16-bit numbers and takes up 205 tiles of open floor, plus 32 for required surrounding walls which could be shared with neighbouring adders and has a nominally installed power pull (before establishing the actual links) of 459; when properly linked and operational, the theoretical maximum consumption is 379. This breaks down to 14 tiles and 24 power per bit in an optimal configuration. The adder is contained on a single z-level and all sum and carry signals are generated within the mentioned area.
-Compared with older efforts, it is remarkably more compact per-bit than the smallest full-adder designs posted on this wiki, and has subtraction and binary complement generation (for the display of negative subtraction results) fully installed already.