Bay 12 Games Forum

Please login or register.

Login with username, password and session length
Advanced search  

Author Topic: The incredible Multiplication Machine  (Read 1971 times)

Larix

  • Bay Watcher
    • View Profile
The incredible Multiplication Machine
« on: November 06, 2013, 09:23:51 pm »

Hmm, i wonder what's 01100100x01100100 (100x100 in decimal)?

Yep, 0010 0111 0001 0000.

And 1101 0011 x 1011 1001 (211*185)?

After a bit of troubleshooting, the correct result - 39.035.

The basis of multiplication in binary is pretty simple - compare each bit of the first factor with every bit of the second factor, if both bits are on, there's a result - the basic multiplication table is nothing but an AND gate. Of course, when multiplying two eight-bit numbers, that still results in 64 AND gates. I don't know if there's a way to avoid that, i couldn't think of any.

So here you go, bunch of mechanical AND gates generating the basic signals:



The bits 5,6,7 and 8 of the first factor control whether the big eight-tile rollers are on, if they're on and the individual gear assemblies (run by each bit of the second factor) are also on, a signal is generated. What you see is half of the basic signal generation, housing 32 minecarts.

Now, we merely need to add up the signals and we got our result.

Hahaha. The obvious problem is that we can't just throw all those signals at a simple binary adder - it's gonna break when we're having four or more active inputs; and we can have eight of them from basic signals, plus incoming carries (and with that many input signals, we're going to get multiple carries). We actually need to distinguish, for our carry calculation, whether at least two, or at least four, or at least six inputs are on. Clearly a job for...

Load-based mechanical logic!
Yep, the much-maligned technique of slapping load on a circuit until it overloads and stops. Of course, we're not going to overload our main power supply, we're using separate "loadable" power supplies for each circuit. With the help of minecarts, we don't even need to build separate circuits for each possible number of active inputs - we use a cart moved by a roller drawing from the main power supply, and run it into an opposing roller, powered when few enough inputs are on, overloaded and off when too many inputs are live; in the latter case, the cart goes past the roller, activating a "carry" pressure plate _and_ disengaging the roller it just passed over. This already reduces the load on the system, and with some finetuning, the circuit can determine how many inputs are on, counting in pairs (obviously, since we're checking for carries, which spawn at every pair of active inputs).

And just to make things easier on the next circuit, carry No. 1 is sent to the next higher bit, carry No.2 switches that carry back off and sends a carry two bits up, carry No.3 re-activates the next-bit carry...

Of course, it still looks completely insane:


But it works, see above. This one is the eighth-bit carry calculator, there are ten more of these things in total. It uses the northern waterwheel to power the always-on roller (north), all other rollers draw from the southern waterwheel; the eight regular signal inputs and two carry inputs are attached to the e-w roller (using the sideways-connecting roller as "activity sensor"). Currently, four inputs are on, 94 of 100 power are consumed, the top two rollers are switched off and a carry is sent to bit No.10. The load used to keep the power drain in the correct range consists of seven grids of axle, a gear assembly and a millstone.

All the base signals _and_ all the carries are finally fed through XOR-type gates, i.e. single gear assemblies taking all possible inputs generated for the bit. If an odd number of inputs are on, the gear assembly switches off, the cart stops on top of the roller and the bridge corresponding to the bit in question becomes visible.

Total tally: 1510 mechanisms, 192 rollers, a bit over 800 blocks (all track was built on ordinary floor), 400 logs, the main power supply provides 2100 power, 7 additional waterwheels and 18 windmills are used for the carry calculators, 93 active minecarts. As far as i can tell, it takes about 250 turns to come up with the correct result, 200 of which are the reaction delays of the bridges (they all get retracted when powering up the machine, then the "on" bridges re-appear).

Errors at finish: one switchable gear assembly attached to the wrong side of a 2x1 roller, two pressure plates linked up wrong (actually caught that during the big link-up session, but that would've been a showstopper), one roller installed the wrong way round, forgot to make the rollers in one carry circuit switchable. I had expected worse.

I recommend not using bridges for output, though: a bit of fluctuation can happen in the adding machinery, which generally irons itself out in at most 200 steps, but intermittent incorrect signals can trigger shortly before the correct signal, and with bridges' long reaction time, that can lead to them getting wedged in the wrong position. In all my tests, the sum engine ended up in the correct state, but e.g. when multiplying 7x15, the bridge at 256 consistently displayed an "on", although the related pressure plate was off. Hatches should guarantee that the displayed result really matches the one the engine actually comes up with.

EDIT: I previously messed around with non-binary calculating, and the first attempt was a multiplier. I think it's a nice piece of dwarfgineering, but, ermm, it's a _bit_ much work for something that can barely calculate 6x6:



The first "factor" activates one of six rollers, sending one minecart up the northern path, where it gets deflected to the side by whichever of _those_ six rollers is on. The cart then bounces back and forth along an e-w track, keeping one of the plates active, which corresponds to the result. Obviously, this takes 36 weight-sensitive pressure plates and six minecarts of significantly different weights. Once the holding roller to the west turns back off, the cart travels south and sorts itself into its original starting bay, by way of weight-sensitive pressure plates switching rollers off.
It might be possible to have twenty different-weight carts, combined with, say, 50 deflecting rollers, you could get results up to 1000; for the paltry cost of 1000 pressure plates just to pick up the results, not to mention input/cart return regulation, and of course 1000+ mechanism linking jobs just to get a result display other than an active pressure plate...
« Last Edit: November 08, 2013, 07:40:24 pm by Larix »
Logged

Aslandus

  • Bay Watcher
  • Slowly descending into madness
    • View Profile
Re: The incredible Multiplication Machine
« Reply #1 on: November 06, 2013, 09:34:15 pm »

I'm confused, where do the ground up goblins come out of?

Raphite1

  • Bay Watcher
    • View Profile
    • Beards and Brimstone
Re: The incredible Multiplication Machine
« Reply #2 on: November 06, 2013, 09:35:59 pm »

Awesome!
*brain explodes*

Amazing work.

Larix

  • Bay Watcher
    • View Profile
Re: The incredible Multiplication Machine
« Reply #3 on: November 07, 2013, 06:58:23 am »

Short update: i performed the two "cornerstone" tests: 0x255 and 255x0, to verify no fake "on" signals are generated, then 255x255 for the maximum number of signals generated. The "null" tests went off without a hitch, the top load one showed another, hopefully final bug - i had overlooked another roller-switchoff to be sent from a carry plate. Took a bit to spot, of course - i had to manually calculate how many carries each sub-calculator had to produce, then go through the list and see which of them gave the wrong number. No.10 was the culprit, and once fixed, the correct result was generated - 1111 1110 0000 0001, i.e. 65025.

So this beast is verified accurate, and gets correct results in ~300 steps. In theory, significantly longer calculation times are possible, up to 1000 steps or so: the number of carries a bit outputs depends, among others, on active carry inputs, and of course, the outputs again influence how many carry-outs higher bits generate. If changed input switches a carry _off_, that takes a hundred steps to register and affect the higher bit(s). Each such case adds at least 100 steps to the total time, i.e. there's a ripple-carry effect taking place.

I'm happy my "resistor carry counter" has passed this test with flying colours, properly generating and propagating 3- and 4- tier carries. This design made the whole thing so fundamentally different from The Great Calculator's multiplication engine that i found it worth building and reporting. It only takes inputs up to 255 (x255), so doesn't reach the full 1000x1000 scope of that work, but has the benefit of being comparatively quick, very fps-friendly (60/40 fps in full operation, in a low-population fort on a 3x5 embark) and relatively compact. It should be expandable to a few bits more, up to 12x12 bits i think. At that point, using a design with fewer carts to pick up the 144 base signals would become prudent - with my 8-bit multiplier, base signal pickup already accounted for 64 minecarts, while the carry calculation took a whopping 13 and the sum calculation 16.
With multiple waterwheels as power feed per resistor circuit and some design changes, up to ~40x40 bits could become possible. It'd take about 25 times as much space and ressources, and time for link jobs, as the multiplier i built. Among others, you'd be looking at 1600 base signals to collect and add up.
Logged

acetech09

  • Bay Watcher
  • Bay Watcher
    • View Profile
Re: The incredible Multiplication Machine
« Reply #4 on: November 07, 2013, 11:23:18 am »

This is awesome.

But if it has no practical use for weaponization, it is but a plaything.

It is time to consider the military implications.
Logged
I challenge you to a game of 'Hide the Sausage', to the death.

zubb2

  • Bay Watcher
    • View Profile
Re: The incredible Multiplication Machine
« Reply #5 on: November 07, 2013, 12:29:51 pm »

If you want weaponozation then use this technology to make dwarf fortress inside your dwarf fortress and drive your dwarves insane with it and unleash them on gobbos.

To OP, way more smarticles than I have available, and cheaper than a walmart calculator.
Logged
(Anyone else have any stories that can compare to a man being beaten to death with his own trousers by a giant gopher?)
(when goblins showed up, I mumbled "Smithers! Release the hounds!" and had the lever pulled.)

Larix

  • Bay Watcher
    • View Profile
Re: The incredible Multiplication Machine
« Reply #6 on: November 07, 2013, 06:30:43 pm »

I hope i can somehow explain this resistor-counter thing, because it really is a pretty interesting bit of machinery:

It measures how many inputs are on by running an incoming minecart through a series of opposing rollers, which may or may not be stopped by excessive load. If the load is too high, the cart passes over the roller _and disconnects the roller it just passed_ - reducing the load, possibly to such a degree that the remainder of the machinery activates and it gets reflected off a later roller.

This device can simply measure "pairs" of active inputs to generate carry output, but it can also count the exact number of active inputs _and_ can distinguish between even and odd numbers, so that this thing can actually be used as a combined carry- and sum calculator. Pathing with two options gets a bit complicated, though:

   

The cart starts in the northeastern corner, off a roller with separate, "un-loaded" power supply. Depending on how many inputs are active, it travels a shorter (at no or few inputs) or longer way (at high numbers of active inputs) along the western track branch to the south. When all ten inputs are live, the cart goes the whole way around the southern loop.

The rightmost branch is the "odd numbers" branch, the one in the middle the "even numbers" one. A sum bit is generated by extending a bridge, so the sum must be collected in reverse - by the northeastern pressure plate, which gets visited only when an even number of inputs are on and retracts the bridge.

The starting roller works N->S, all others S->N.

Because each additional active input adds five points of load, but switching off a roller including the gear assembly and one grid of axle reduces the load by eight, five additional "ballast" gears are required, made connective when the second, fourth, sixth, seventh and ninth pressure plates are active. The input and ballast gears are all attached to a long roller, the cheapest way to build an input acceptor, at a mere two power per tile.



To the north we can see the waterwheel driving the starting roller, to the south the resistor one; the rutile 1x3 bridge is the "sum indicator". The clump of five gears to the southwest of the input-collector roller is the ballast array.

This device has a significant downside: it cannot process inputs going offline during operation[...]

Guess what, i'm just too crafty to get myself held back by such trivialities, so i updated it. See the pair of 3x1 rollers with five gears and an axle sandwiched between them? That's a three-input OR gate(*), consisting of one NOT and two AND gates, and those AND gates consist of a pair each of 10-input XORs. In short, it's condensed awesomeness.

The shakedown is that the "start" roller only has power if one of these three gates transmits power from the waterwheel.

* The NOT gate gets triggered by the pressure plate just south of the starting roller - i.e. it only provides power during the first round the cart runs, after that it's always off and only re-activates if the cart stands still for whatever reason.

* The right-hand gears in the two AND gates are linked to all inputs of the resistor. The left-hand gears are linked to all output pressure plates. The gears in the northern gate are pre-toggled, those in the southern gate aren't. The result? The northern gate transmits power if and odd number of input _and_ an odd number of output signals are active. The southern gate transmits, if both input and output are an even number. If there's a discrepancy between the two, neither gate transmits power.

* I hope you can guess where this is going: on the first round, the cart proceeds to the output plate corresponding to the actual number of inputs which are active, activates all plates up to it and passes over the "return" plate upon finishing the round. From now on, power will only be provided when input and output match with regard to even/odd. If there's a discrepancy, power is cut, the cart stops on the return roller and is only started again when pressure plates start turning off again.

* I've run the test all the way up and down, and now, this circuit registers and processes inputs going offline, as long as they only go out one by one; if a pair of inputs went off during the same round, the device would miss the change; for the purposes of "volume metrics" and multiplication, it should still be adequate. So - no need to introduce artificial delay, this device should take at most 200 steps to multiply two eight-bit numbers.

Ten outputs are the practical maximum to produce - not because of the load (although it does hit the limit of what a single waterwheel can provide), but because of the time needed for the longest possible round. Unless i've been mis-counting, we're dealing with a 48-tile full tour at ten active inputs, which puts the cart's return time at the exact maximum without pressure-plate recovery - 99 steps precisely.

(*) in case you didn't know yet, this is the new state-of-the art design for mechanical OR gates: two rollers of whichever length required, with the OR-required switchable gears between them. Any number of inputs are possible, with a ridiculously simple design - two ten-long rollers can handle ten inputs, at a cost of 40 power (and six mechanisms and two ropes); it looks and works like a simple clutch. I call it the Massive Multi-Parameter OR Gate, or MMPORG.

P.S./Edit: the logical condition of the regulator gate is, with a-k as inputs, a'-k' as outputs and s for starter:
NOT s OR (a+b+c+d+e+f+g+h+i+k=even AND a'+b'+c'+d'+e'+f'+g'+h'+i'+k'=even) OR (a+b+c+d+e+f+g+h+i+k=odd AND a'+b'+c'+d'+e'+f'+g'+h'+i'+k'=odd). The output's odd/even state could be easier measured by simply picking up a signal from the left or right 'return' branch, of course, linking in all output plates is only really required when an even/odd distinguishing pathing/output is not used.
« Last Edit: November 11, 2013, 01:23:58 pm by Larix »
Logged