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: 17
Joined: Sat Jul 02, 2016 4:36 pm
Contact:

Pairwise Multiplication using Squares

Post by Eylrid »

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: 384
Joined: Mon Mar 27, 2017 10:12 am
Contact:

Re: Pairwise Multiplication using Squares

Post by Lav »

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: 46
Joined: Mon Oct 23, 2017 10:46 pm
Contact:

Re: Pairwise Multiplication using Squares

Post by thedarkbunny »

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 4122 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.

yobeeb
Manual Inserter
Manual Inserter
Posts: 1
Joined: Thu Nov 19, 2020 6:52 pm
Contact:

Re: Pairwise Multiplication using Squares

Post by yobeeb »

If I know one of my inputs is always just 0 or 1 is there a way to optimize further?


Thanks, that's brilliant!

I have a supply train station for outposts that requests items to be unloaded per values on some constant combinators. Most of the items (belts, pipes, etc.) I just want to have on hand in case I need to rebuild or expand something. But I also wanted to bring fuel for trains--in my case, solid fuel. And I didn't want the supply train to make a whole extra trip every time the solid fuel drops below the requested 200 just to bring a handful to top it off. So I added a sort of latch with another constant combinator to specify a bias N (when the request is unsatisfied, unload an additional N of these items beyond the original request). Now it waits until it's below 200 and then refills up to 400. Yay!

I really needed the "each times each" sort of logic, so the ab = [(a+b)^2-(a^2+b^2)]/2 strategy is a pretty elegant solution. Since I'm talking about a few cargo wagons worth of items, I won't run into overflow problems. I guess I could specify double the amount for the bias and save myself the divide-by-2 arithmetic combinator at the end.

I'm wondering since I know one of my inputs (from the decider) is always just 0 or 1 is there a way I could optimize this further?

blueprint:

Code: Select all

0eNrtW1tzozYU/i88dswW3RDkob+ib53Ug41sq4uB4ZJuZsf/vRJ2DMYC6ZDdODPbF2fsoE9H37lKR3z3Nlkrykrmjff03ZPbIq+9p7++e7Xc50mmf2teS+E9ebIRR2/l5clRf6uKTVEWVeOdVp7MU/HNe0KnlX1YIrPBEHx6Xnkib2QjxXna7svrOm+PG1EpzPsJV15Z1GpAketZ9LyIr7xX78nnITppGUYY2AUDo1kM4oTBZjHoFWMj977IxLap5NYvi0zMglETGBtQmiaVCSD60svzhZlAQhC7jCvFKftoqiJbb8QheZFFpZ+qRJKuNUKzrpukUYpsqlasvORFaTvZZGKdFXtZN3K7LtqmbNVj81by9rjfgWp76aG0gSr4rRbREW445A3yvJRcdD/Weig6LyUdmqFU3zA6PZ9M7PHrBGrV26++zGtRNcKkCxRfdcGUWtTkqazOcyu7MGBHV+yjSGV7tJtLcDuDATMGY3IrJgquoOJbWYm69psqyWttS/5GZI2FDD4mIzRN0keBncwUw65Uh3dUry4I52DzFrimDe/6DJ61pmeT1BggNUafRWoCkTr4LFJTuBkOhXczQ7ZgEgSdJITwTz4L/xwiNf4sUkcLFIqhCo0XTEKAk+A+DCtwmft1U5Sm4PhW5bAxqDmzb2W1bWWjk256BdrJqjbk3BdZNa36pc+K3RN+kr82B5nvvXPKVblSl5qB/nIskypp9FTeH92/L9OJvEv1qaz137dyohZ5um6KdbdC72mXZLX6tfu21ustReou1Z+QEoDHugRY6Tx/JsHz9NjsUv50q9l3n5vuM1GfX2gcBSTGiKk/iIYkxCSgYcSNeRQjaHJGg+RMOxtxXMzQfrrFsZ54/X2q3MH43gm3B1ErK253O2suZuYCApOFuZ0aIsecCR+LVKyL3booRXXRIgIUgXTEGg6naKKQBUUPWxAZm0E8tSC2sI754AWN7RpPLihcWOJ88ILYeEFkakEc7JnDZU15ZgRHRXbUeGGl8GDyCZ4gnwRwmoiVJoLgqNiOihcWlx9Mfjwmn06RT+A0MTtNkBA+xPtYmpRJjmiKpmhi4K0/vV2VCRQURvnDWIpGLNFgiqUFYZTbjSmC0BQ+jKZxgUOmChwSw2kKrTTRAELTw8omMq4y6FReoAsieGSnCRTBH1YuKx8b0TRlTXRBBLfvKiiFBjyCrAGPMrCoxF5mUUgYJQ+rRqftfDJqqj15leyNZNsLIBq5n64TYtddvEBKe0HFAoCU2ColQwukpHYpMUBKe+JnZIGU9qqLUYCUzC4lWyClPU+xcAGsvUpggGYSCe2Lh3gPt8OBW0cksoKGQ9+pErk/NH7XHp47tiS3IQ+bcJE7LoHgYndcBsEl7rgcgkvdcWMILnPGxSC9he64IL1xd1yQ3iJ3XJDeYndciN64u78RiN64u78RiN64u78RiN64u78RiN64u78RkN56f0sq2RyOoss5xXEj8655Mt8bQE5FYo/c93rqBc0ekWwPupNTCw2z7vs9vrKSQeXp/aaGTt3emAeHXt1YeXi2rWOivA9FqdjKVBXl83zHUL4vsD+G7Lmu2lKWNVD5quRr82a9q4rjWuYK5tJ2g/bOpnUQIbfuE+fgI6zBriAwlyA8uu0ZKw7nFT087Asc91/DdrblolJdZDL1d63IzgpotU5xEAyu2D1PML+vhMjvyMWO5ILrO9RvE2gE6T7iwNJ+HB9q3nXetHPeLur2/9G4sxWF4xnMLEQBONAOGh40/hyBFt/G2b8/Is4anHjlbpEzwSF0s98IwTUX/K+59Gzzc87EDb4zoy/HqwQRhusL/3r6MnoQH/cz7lX4Q1REgKlxUHPS8MenRmNe6pMkC0DX0O8vYBuhsAPUNpO7nS++lZki5EXUN5n7isRd7saLMpGVXybbr2aQyAGklOVwMWhQPMQOwy+HWL7S94QQKHCAmbjpZpYLIQBiq8ZU+0qhpGPMoQ1gAGRdZrLRZ2NmKOIAZe4HmPmjkzWcuXoeefu4HIr4lAdTqAfHP9WD3179MFmAE8X53j8kakDan2Yu9trBLcmhSFcM4vgui395xqhq6gqyPXTSzEAxJ4aUeotGBaHhmq4QoQPELmvVBuTfZK9U3mNQYBhTCMpw3hGFusQ3B4ICiBPd7wimLkpE7F1bAP4Ln7WM9wDjfdy48sc/pvIP31VJ8k9ZSf7+iMr/Tl8Moq/Jo7SIv6OOZD8hCw3eW7wP+wiS668vp93jOBWOhrcUlqci/Q6gcTh1q/pyocJ+Nsw+sOQzajMaE3PojDO+CWGE48AcMGGg0TvKpJ9goLqA95vCP9e4y7c4ZXsszbWEi3EWu119KCrhT8MQRyH+mdzPuJimOaobLd3FTA3H+Uas0NWBR+ZiBHOpmqxHvxHI2s8XZp9X51meBi95r7wXZYnnblOEKKcxDzkKQhaeTv8BUD2scw==

Post Reply

Return to “Combinator Creations”