Pairwise Multiplication using Squares

This board is to show, discuss and archive useful combinator- and logic-creations.
Smart triggering, counters and sensors, useful circuitry, switching as an art :), computers.
Please provide if possible always a blueprint of your creation.
Post Reply
Eylrid
Burner Inserter
Burner Inserter
Posts: 11
Joined: Sat Jul 02, 2016 4:36 pm

Pairwise Multiplication using Squares

Post by Eylrid » Wed Jul 11, 2018 8:09 pm

Say you have a set of signals on the red wire (iron ore = -85, copper ore = 45, stone = -60, coal = -28) and a corresponding set of signals on the green wire (iron ore = -55, copper ore = -78, stone = -18, coal = -60). Adding each signal from the red wire to its corresponding signal on the green wire is trivial: Just hook both up to the input of a combinator. Doing the same with multiplication is not so straightforward.

We can hack our way to pairwise multiplication using a touch of algebra.

We start with the equation (a+b)^2 = a^2 + 2ab + b^2

Solve for ab: ab = [(a+b)^2 - a^2 - b^2]/2

Now we have something we can calculate with combinators. Use three arithmetic combinators for the squares, one that is connected to both the red and green wire for (a+b)^2, one that is only connected to red for a^2, and one that is only connected to green for b^2. Set all three to each ^ 2 output each. Connect the latter two to an arithmetic combinator set to each * -1 output each. If signal timing is important where you are using this then connect the (a+b)^2 combinator to any combinator that passes every value through (for example each * 1 output each) so it will be delayed the same number of ticks. Connect those to an arithmetic combinator to divide everything by 2. The final result will be each signal on the red wire multiplied by it's corresponding signal from the green wire.

Blueprint:

Code: Select all

0eNrtlm1vgjAQgP/LfVxgEwRx/JXFEV5uegm0pBQzY/rf15bMOUQnbnEm2xdIud5L7znuuoWsbLEWxCTEW6Ccswbipy00tGRpab7JTY0QA0mswAGWVmaVCpKrCiXlbs6rjFgquQDlALECXyH21MIBZJIkYWfQLjYJa6sMhd7whSkHat5obc5MDNqiqzU25nUfajcFCcw7aeCAjloKXiYZrtI1aW2t8mE20eLCmmqM4IVEI5OD861JyFZ/2cXV7XAxzVfmYA0aM8ZWI1OTLd8BXqNIuyjgWWvyVtbtaNtK2ROw7kA2Rs88BBb7maPC+sxJ5C1Ju/SU80k8NVlfCkTWVwz6igvt1DdeBrfPDrerPV/vEP2xECf/DE3lj0ERnodiuourwoLaysVSxyI0j5qXeJTE9Dtxn19rQxEHY4vnzzWAwex6X7aAnyin8LI/e3IrbMy02Idzdx04vf7s9+AEffFpVtFp1LNDa0MoZxdO2pth+TsovXGswvNgRJc1vcmN9ryH67AIj7IYmFPzI6mfj5yQvs28d/6AjIZKQA9Je3OO9y7aDqxRNNbTbB75/tx7nES+Um9PiftC
Caveat: This will only work correctly if all values are in the range -46340 to 46340, including when you add the green signal to the red signal. Anything outside that range will overflow when squared. There are some cases where overflows cancel out and you still get the right answer, but it doesn't always work that way.

If the signals on one wire all have a value of 1 then this can be used to filter signals from the other wire.

(I haven't yet figured out how to get pairwise division. If anybody has any ideas, please let me know.)

User avatar
Lav
Filter Inserter
Filter Inserter
Posts: 380
Joined: Mon Mar 27, 2017 10:12 am

Re: Pairwise Multiplication using Squares

Post by Lav » Fri Jul 20, 2018 2:49 pm

Eylrid wrote:(I haven't yet figured out how to get pairwise division. If anybody has any ideas, please let me know.)
At a glance:

(a/b) = (a) * (1/b)

And since we have integers instead of floats, it's probably more like:

(a/b) = ((a) * (K/b))/K, where K is some constant.

thedarkbunny
Inserter
Inserter
Posts: 42
Joined: Mon Oct 23, 2017 10:46 pm

Re: Pairwise Multiplication using Squares

Post by thedarkbunny » Fri Jul 27, 2018 6:18 am

I took the idea and ran with it. The original design is limited to ±46340 on either input (and the sum of both inputs). I worked around it by breaking each integer into 11-bit chunks and multiplying them in stages. The result is as follows:
MassiveMultiplier.png
MassiveMultiplier.png (712.56 KiB) Viewed 184 times

Just connect one network to the top left combinator, one network to the top right combinator, and read the result from top center. Should take either color on either side.

Pros:
- Can multiply two networks together.
- Can handle any input, so long as the result is within the usual ±2147483648 range.

Cons:
- Uses a whopping 54 combinators.
- Takes six ticks to calculate a result.

Still working on pairwise division, but I can't figure out a way that doesn't result in unacceptable loss of precision.

Post Reply

Return to “Combinator Creations”