Pairwise Arithmetic / each op each

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
Nidan
Fast Inserter
Fast Inserter
Posts: 227
Joined: Sat Nov 21, 2015 1:40 am
Contact:
Contact Nidan

Pairwise Arithmetic / each op each

Post by Nidan »

I occasionally search for blueprints for doing a combinator operation on two wires rather than two signals, i.e. both inputs being "each". But aside from the well known multiplier they seem hard to find (or nonexistent). To finally have a full set I decided to make a book with solutions for every combinator operation, whether well known or obvious and tried to design the missing ones.

All blueprints have constant combinators at the top for the input, and a wooden pole at the bottom for the output. Throughput is one tick per operation, i.e. input signals may change each tick.

Improvements welcome!
  • + add
    Latency: 0
    Combinators: 0
    The one thing the circuit network does for free, just connect both inputs to the same combinator or wire
  • - sub
    Latency: 1
    Combinators: 2
    Negate one side, then add
  • * mul
    1. Latency: 2
      Combinators: 5
      Limitations: All powers must fit into 31 bits
      The well known rearrangement of the binomial formula (a + b)^2 = a^2 + 2ab + b^2 => a * b = ((a + b)^2 - a^2 - b^2) / 2
    2. Latency: 3
      Combinators: 20
      Avoids the inaccuracies in the simple multiplier by putting the division before the exponentiation and processing the lost bits separately
      By almania
  • / div
    Latency: 12
    Combinators: 113
    Limitations: Inaccurate by ±1, depending on inputs
    Approximates the multiplicative inverse of the divisor, then multiplies that with the dividend. Special handling needed for dividing by 1 and -1.
  • % mod
    Latency: 15
    Combinators: 144
    Limitations: Inaccurate by ±1 depending on inputs, inherited from divider
    Calculates remainder by dividend - (dividend / divisor) * divisor. Thus also produces the result of the division as an intermediate
  • ^ pow
    No blueprint for this. It's certainly doable, I could chain 31 multipliers with logic to feed them the correct inputs, but that's huge. (around 2100 combinators)
  • & and
    Latency: 3
    Combinators: 12
    And, or, and xor all use the same concept: Split the inputs into the individual bits, then add them. For and the result must be 2, for xor it must be 1, for or either is fine. So, test for the correct result and set the corresponding bit in the output. Since addition of two bits will at most produce a two bit result, we can split the inputs into even and odd bit positions and handle them in bulk. For and and or we need some special handling for the upper two bits since overflow both from and into the sign bit are awkward to handle.

    Split even and odd bits, add each pair, then select, shift and merge the top bits of each addition. Special handling for sign bit
  • | or
    Latency: 3
    Combinators: 15
    Split even and odd bits, add each pair, then select, shift and merge the results of each addition. Special handling for sign bit
  • ^ xor
    Latency: 2
    Combinators: 6
    Split even and odd bits, add each pair, then select and merge the low bits of each addition
  • << sll
    Shifting left is the same as multiplying by two. Thus, convert the right side into powers of 2, then use a multiplier.
    One version for each multiplier above
    1. Latency: 4
      Combinators: 13
      Limitations: All powers must fit into 31 bits, inherited from multiplier
    2. Latency: 5
      Combinators: 28
  • >> sar
    Shifting right is not quite the same a dividing by two; also, dividing is complicated…
    1. Latency: 5
      Combinators: 199
      Sort input into groups for each possible shift amount, then do a hardcoded shift
    2. Latency: 7
      Combinators: 70
      Shift right by shifting left. a >> b = a * 2 ^ (32 - b) / 2^32
  • < less, > greater, != not equal
    Latency: 2
    Combinators: 3
    In e.g. x86 assembly, comparison is the same as subtraction but ignoring the result; we can do the same in circuits.
    Subtract, then do the compare against zero.
  • = equal
    Latency: 3
    Combinators: 7
    All signals that are present on either wire, except for those that don't sum to zero.
    The trick for </>/!= doesn't work, since circuits don't distinguish between zero and not present.
  • >= less or equal, >= greater or equal
    Latency: 3
    Combinators: 9
    Combines the circuits for equal with less resp. greater than
Bonus blueprints:
  • * mul (long, unsigned)
    Multipliers that also produce the upper half of the result, treating both operands as unsigned
    1. Latency: 5
      Combinators: 72
      By almania
    2. Latency: 7
      Combinators: 66
  • * mul (long, signed)
    Latency: 5
    Combinators: 63
    Multipliers that also produce the upper half of the result, treating both operands as signed
    By almania
  • >> slr
    Latency: 7
    Combinators: 62
    Shift right by shifting left. a >> b = a * 2 ^ (32 - b) / 2^32.
    This is a logic right shift, i.e. the sign bit doesn't "stick"
  • min and max
    Latency: 2
    Combinators: 5 for one, 6 for both
    Calculates the difference and conditionally adds it to one of the inputs
  • Filters
    • Whitelist (non-zero)
      Latency: 2
      Combinators: 7
      Filters left side, only letting through signals which are present on right side
      Author unknown
    • Blacklist (non-zero)
      Latency: 2
      Combinators: 6
      Filters left side, only letting through signals which are not present on right side
      Author unknown
    • Whitelist (negative)
      Latency: 2
      Combinators: 6
      Filters left side, only letting through signals which are negative on right side
      Author unknown
    • Whitelist (boolean)
      Latency: 2
      Combinators: 6
      Limitations: Values on right side must be boolean (0 or 1)
      Filters left side, only letting through signals which are present on right side
    • Blacklist (boolean)
      Latency: 2
      Combinators: 5
      Limitations: Values on right side must be boolean (0 or 1)
      Filters left side, only letting through signals which are not present on right side

Last edited by Nidan on Tue Mar 12, 2024 12:55 am, edited 7 times in total.
Top
mmmPI
Smart Inserter
Smart Inserter
Posts: 2728
Joined: Mon Jun 20, 2016 6:10 pm
Contact:
Contact mmmPI

Re: Pairwise Arithmetic / each op each

Post by mmmPI »

Thanks for sharing all those !

I had a look at the other operation but the division got most of my attention even though that's the one i'm the least likely to ever use in game, it feels like it's the one where there is the most to learn from at first, i hope you don't mind some questionning :
Nidan wrote: ↑
Mon Sep 26, 2022 2:30 am
 / div
Latency: 13
Combinators: 124
Limitations: Inaccuracies for large numbers
I was originally planning to implement the algorithm described in "Hacker's delight", but didn't like the loop in there. Near the end of the section however another algorithm is referenced that's more suitable for hardware

p = W + ceil(log_2(divisor))
m = ceil(2^p / divisor)
dividend / divisor := floor(m * dividend / 2^p)

where W is the word width, 32 for factorio circuits.
I haven't figured out how to do division with numbers that don't fit a single combinator, so the version in the blueprint uses 31 for p, rather than at least 33, which is the reason for the inaccuracies.
Could you explain a little more what you call "large numbers" ? or is there a way to roughly quantify/ estimate those inaccuracies with a rule of thumb ? ( to me it seem from observation to sometimes underestimate the result, never the opposite; observations are limited compared to understanding better the formula though )

The build itself is quite complex and it's not easy to understand where those comes from despite your explanations about p =31 instead of 33.

The 3 line of math are also complicated to understand, how come does this result in a division ? Do i have to find/read "Hacker's Delight" to understand ? or is it not explained there because it's supposed to be a prerequisite already ? :D

I'm asking this because i thought about doing a limited version of this division similar to the multiplier version which needs to have all power fit into 2^31. My goal was to use less combinator and don't really care about inaccuracies while keeping the responsiveness, 1 tick per operation and latency.

I saw the formula "(a/b) = ((a) * (K/b))/K " in the posted you linked , and decided to reuse the 2 different multipliers from your post to test the differences :



This is the version using the non-limited multiplier, for a total of 42 combinators and i think the latency should be counted as 7 ticks .

(edit : new bp string without dummy combinators, count 42 instead of 44 )



This is the version using the smallest multiplier, for a total of 8 combinators, and 5 tick latency if the other is 8.

Now the 2 version do not use the same K in the (a/b) = ((a) * (K/b))/K formula. After trials i ended up choosing 650 000 for the non-limited one and 46340 for the limited one, those are the value hardcoded in the first and last combinator. I started to compare the result with another set of input than the originals one, and notice that all 3 methods are giving different approximation, while the latest attempt with only 8 combinators being not able to compute "high numbers" but sometimes being the more precise/accurate on small number.

As i don't understand where the imprecision come from when looking at the original build, and i'm not able to quantify them in the 2 version i quickly put together, it's loosing a lot of the practicality for me.

Ideally for in game purpose i'd like those 8 or 10 combinators to perform a pairwise division on input that would be of known range, say [0-100 000] maybe more ? so that those correspond to the amount of material i would have in chest, i don't need to divide 500 020 000 / 650 082 precisely :) but knowing (48005/8000 > 6 ) is more the range of number that i use in factorio for trains. Limitations wouldn't be innacuracies as much as range of number instead.

How would you go to propose a simpler division in terms of combinators if you are allowed to discard large numbers ?

Can the precision be 100% in a certain range if numbers outside of this range are discarded ?
Top
Nidan
Fast Inserter
Fast Inserter
Posts: 227
Joined: Sat Nov 21, 2015 1:40 am
Contact:
Contact Nidan

Re: Pairwise Arithmetic / each op each

Post by Nidan »

mmmPI wrote: ↑
Tue Sep 27, 2022 1:09 pm
 Thanks for sharing all those !

I had a look at the other operation but the division got most of my attention even though that's the one i'm the least likely to ever use in game, it feels like it's the one where there is the most to learn from at first, i hope you don't mind some questionning :
Nidan wrote: ↑
Mon Sep 26, 2022 2:30 am
 / div
Latency: 13
Combinators: 124
Limitations: Inaccuracies for large numbers
I was originally planning to implement the algorithm described in "Hacker's delight", but didn't like the loop in there. Near the end of the section however another algorithm is referenced that's more suitable for hardware

p = W + ceil(log_2(divisor))
m = ceil(2^p / divisor)
dividend / divisor := floor(m * dividend / 2^p)

where W is the word width, 32 for factorio circuits.
I haven't figured out how to do division with numbers that don't fit a single combinator, so the version in the blueprint uses 31 for p, rather than at least 33, which is the reason for the inaccuracies.
Could you explain a little more what you call "large numbers" ? or is there a way to roughly quantify/ estimate those inaccuracies with a rule of thumb ? ( to me it seem from observation to sometimes underestimate the result, never the opposite; observations are limited compared to understanding better the formula though )
With my few test inputs I've seen a difference of 2 (from 1G / 1k, see the wood/coal/stone/iron inputs). From there I generalized with what my intuition told me: more significant bits in input -> larger result in multiplier output -> more bits from "m" used for the upper half -> higher chance for inaccuracies. However, looking at it now, the difference of 2 comes from an error in the circuits: adding the lower half of the multiplier output overflows in that case, but the carry gets lost, which accounts for an error of 2. There's also a second bug: In the multiplier the result of the leftmost column should be shifted left by 12 instead of 11.
Generally the error should be within +/-1. Worst case overestimation for m is 1, thus m / divisor < (2^p / divisor + 1) * dividend / 2^p = dividend / divisor + dividend / 2^p. Since p = 31 and dividend <= 2^31, dividend / 2^p <= 1. Thus the input for floor, and therefore also the final result is at most one too large.
The build itself is quite complex and it's not easy to understand where those comes from despite your explanations about p =31 instead of 33.
"those" == errors? The division ceil(2^p / divisor) is inexact since it rounds up ("ceil" as in ceiling).
The 3 line of math are also complicated to understand, how come does this result in a division ? Do i have to find/read "Hacker's Delight" to understand ? or is it not explained there because it's supposed to be a prerequisite already ? :D
I used := to mean "defined as". Fill is the value of m from line 2:
dividend / divisor := floor(ceil(2^p / divisor) * dividend / 2^p) = floor(ceil(2^p / divisor) * dividend / 2^p)
This should look similar to the "(a/b) = ((a) * (K/b))/K" from the other thread, with K being 2^p and some extra rounding
I'm asking this because i thought about doing a limited version of this division similar to the multiplier version which needs to have all power fit into 2^31. My goal was to use less combinator and don't really care about inaccuracies while keeping the responsiveness, 1 tick per operation and latency.

I saw the formula "(a/b) = ((a) * (K/b))/K " in the posted you linked , and decided to reuse the 2 different multipliers from your post to test the differences :



This is the version using the non-limited multiplier, for a total of 42 combinators and i think the latency should be counted as 7 ticks .

(edit : new bp string without dummy combinators, count 42 instead of 44 )



This is the version using the smallest multiplier, for a total of 8 combinators, and 5 tick latency if the other is 8.
I count 7 and 4 ticks.
Now the 2 version do not use the same K in the (a/b) = ((a) * (K/b))/K formula. After trials i ended up choosing 650 000 for the non-limited one and 46340 for the limited one, those are the value hardcoded in the first and last combinator. I started to compare the result with another set of input than the originals one, and notice that all 3 methods are giving different approximation, while the latest attempt with only 8 combinators being not able to compute "high numbers" but sometimes being the more precise/accurate on small number.

As i don't understand where the imprecision come from when looking at the original build, and i'm not able to quantify them in the 2 version i quickly put together, it's loosing a lot of the practicality for me.
If my bp has the larger error that's probably due to the bug mentioned above. Generally, every division introduces an error, worst case the error is (b-1) / b, or about one too small. a * (K/b - 1) / K = a/b - a/K, so a/K is your worst case underestimation (or +/-1, since circuit division always rounds down).
Ideally for in game purpose i'd like those 8 or 10 combinators to perform a pairwise division on input that would be of known range, say [0-100 000] maybe more ? so that those correspond to the amount of material i would have in chest, i don't need to divide 500 020 000 / 650 082 precisely :) but knowing (48005/8000 > 6 ) is more the range of number that i use in factorio for trains. Limitations wouldn't be innacuracies as much as range of number instead.

How would you go to propose a simpler division in terms of combinators if you are allowed to discard large numbers ?

Can the precision be 100% in a certain range if numbers outside of this range are discarded ?
As long as b is smaller than K (otherwise K/b == 0), and a is limited such that a * K (in case b == 1) doesn't overflow the multiplier, the error is probably small. I wouldn't expect exact results, but +/-1 should be the norm.

I have to play around with it some more, but seems like as long as b < K and no overflows the result should be within +/-1.
Top
mrvn
Smart Inserter
Smart Inserter
Posts: 5703
Joined: Mon Sep 05, 2016 9:10 am
Contact:
Contact mrvn

Re: Pairwise Arithmetic / each op each

Post by mrvn »

This would be so much simpler and faster if combinators had 2 extra virtual signals: "each red" and "each green" (as has been proposed for ages).

The wire signals are carried on different wires and are accessible from LUA and visible on a power pole. So clearly the game does have a notion of where a signal comes from. How hard can it be to extend the "each" virtual symbol to have flavors that only look at the red or green wire?
Top
Nidan
Fast Inserter
Fast Inserter
Posts: 227
Joined: Sat Nov 21, 2015 1:40 am
Contact:
Contact Nidan

Re: Pairwise Arithmetic / each op each

Post by Nidan »

Do i have to find/read "Hacker's Delight" to understand ?
I know it primarily for the division algorithm and mentioned it since it's basically my source. It contains quite a few tricks for optimizing specific operations or doing something efficiently when your CPU doesn't feature the required instructions (thus the name). Today it's probably most useful to someone building optimizing compilers or programming in assembly. Some parts might also be interesting for hardware designers. Considering factorio's circuit network also sits in that general area, there are probably more useful things to be found.
or is it not explained there because it's supposed to be a prerequisite already ? :D
The book gives proofs for most algorithms but they tend to be somewhat math-y, so they may, depending on your background, be harder to follow.
mrvn wrote: ↑
Tue Sep 27, 2022 9:44 pm
 This would be so much simpler and faster if combinators had 2 extra virtual signals: "each red" and "each green" (as has been proposed for ages).

The wire signals are carried on different wires and are accessible from LUA and visible on a power pole. So clearly the game does have a notion of where a signal comes from. How hard can it be to extend the "each" virtual symbol to have flavors that only look at the red or green wire?
I've seen quite a few suggestions/requests for this over the years, but personally I don't think Wube will implement it. But who knows? Maybe 1.2 will bring a pleasant surprise. At least we're now allowed to have each on the right input. Without that some of these operations are probably impossible.
Top
mrvn
Smart Inserter
Smart Inserter
Posts: 5703
Joined: Mon Sep 05, 2016 9:10 am
Contact:
Contact mrvn

Re: Pairwise Arithmetic / each op each

Post by mrvn »

Nidan wrote: ↑
Tue Sep 27, 2022 11:59 pm
mrvn wrote: ↑
Tue Sep 27, 2022 9:44 pm
 This would be so much simpler and faster if combinators had 2 extra virtual signals: "each red" and "each green" (as has been proposed for ages).

The wire signals are carried on different wires and are accessible from LUA and visible on a power pole. So clearly the game does have a notion of where a signal comes from. How hard can it be to extend the "each" virtual symbol to have flavors that only look at the red or green wire?
I've seen quite a few suggestions/requests for this over the years, but personally I don't think Wube will implement it. But who knows? Maybe 1.2 will bring a pleasant surprise. At least we're now allowed to have each on the right input. Without that some of these operations are probably impossible.
That limitation has to be lifted too. For most stuff it would be enough to allow "each red" op "each green" or the other way around. But there is no reason not to allow "wood" / "each" = "each". Even "each green" / "each" = "water" could make sense to the user.
Top
Nidan
Fast Inserter
Fast Inserter
Posts: 227
Joined: Sat Nov 21, 2015 1:40 am
Contact:
Contact Nidan

Re: Pairwise Arithmetic / each op each

Post by Nidan »

mrvn wrote: ↑
Wed Sep 28, 2022 12:23 am
Nidan wrote: ↑
Tue Sep 27, 2022 11:59 pm
 At least we're now allowed to have each on the right input. Without that some of these operations are probably impossible.
But there is no reason not to allow "wood" / "each" = "each".
That one is allowed, it gets used frequently in the blueprints in this thread. (I should have written "would have probably been impossible".)
Top
mmmPI
Smart Inserter
Smart Inserter
Posts: 2728
Joined: Mon Jun 20, 2016 6:10 pm
Contact:
Contact mmmPI

Re: Pairwise Arithmetic / each op each

Post by mmmPI »

Nidan wrote: ↑
Tue Sep 27, 2022 7:34 pm
 I have to play around with it some more
Same here !

Thank you for your math explanations ( and correcting my latency calculation ), i had not recognized the similarities and differences between the formula using log2(n) 2^n and the one using a K factor.

Ceil and Floor i wasn't sure that they are written because you do the operation on purpose to make the formula valid, or if you wrote them because that's what the game does with your circuit, and is a way to implement a division, despite the limitations of the numerical system used by combinators that floor and ceil when there are decimal part. I think it could be both or not as clear as 1 or the other as it was represented in my mind before.

It seem clearer for me now that the formula show where the inaccuracies come from. And that there is no rounding in the end result coming from the log_2(divisor). The K= 650 000 correspond to 2^19 or p = 19 as log_2(650 000) = 19.31... the discarded 0.31 would just represent K being a bit higher or smaller, but K doesn't appear in the end result. 19<31<33, the result is then less precise with only 19 compared to 31. But with the limited method, using more than 19 means most numbers will overflow if b is small, when doing the a*(K/b) part. (K =2^19).

The formula " (a/b) = ((a) * (K/b))/K " doesn't contain "floor" and "ceil" but i think it should because in the implementation it is happening, rewriting the formula to account for how combinators behave in game would be a/b ~= floor((a * floor(K/b))/K) and then it follows the same convention as the original formula ?

I searched for other algorithm to implement division and found some using bit shifting and subtraction, that seem pretty comon as google gives plenty hit with different langages, however to implement them in factorio is not straightforward if the 1 tick per operation is the rule because they require a loop, with up to 32 cycles if the numbers are up to 32 bits. This would mean 32 circuit in parralel and a sync mechanism. And is unlikely to result in less than 120 combinators from my quick attempt as each loop require several operation and x32 it scales very quickly to add 1 operation to such loop. I think it has similarity with what you refered to as the loop you didn't like from the "Hacker's Delight" first described algo but maybe i'm wrong.

It makes me curious about the >> operation, i need to learn with those some more :)

If you consider things such as : you can "easily" do pairwise operation using those blueprints, then it becomes a game of finding what are the new opportunities :D and it's quite easy to find some system such as [logistic content] / [ quantity 1 chest can store of 1 particular material] = number of lamp to light. for iron it would be 2400 to set up on a constant combinators. then when you read 24000 on the logistic content it would light up 10 lamps 1 brain for all item.

It could be used with 10*[number of open outpost] / [number of outpost] to yield between 0 and 10 lamps lighting up for 0 to 100% available outpost. ( replace open outpost with non-limited outpost in case ).

I will play with those too !
Top
Tertius
Filter Inserter
Filter Inserter
Posts: 667
Joined: Fri Mar 19, 2021 5:58 pm
Contact:
Contact Tertius

Re: Pairwise Arithmetic / each op each

Post by Tertius »

@Nidan, could you please check the blueprint you posted? If I try to use it, Factorio says: "Decompression failed. Input is invalid or incomplete".
Top
mmmPI
Smart Inserter
Smart Inserter
Posts: 2728
Joined: Mon Jun 20, 2016 6:10 pm
Contact:
Contact mmmPI

Re: Pairwise Arithmetic / each op each

Post by mmmPI »

Maybe it is required to have the mod text plate ? I had it in my game when importing the blueprint book and blueprints contains text plate with the name of the operation
Top
Nidan
Fast Inserter
Fast Inserter
Posts: 227
Joined: Sat Nov 21, 2015 1:40 am
Contact:
Contact Nidan

Re: Pairwise Arithmetic / each op each

Post by Nidan »

Tertius wrote: ↑
Thu Sep 29, 2022 10:33 am
 @Nidan, could you please check the blueprint you posted? If I try to use it, Factorio says: "Decompression failed. Input is invalid or incomplete".
mmmPI wrote: ↑
Thu Sep 29, 2022 11:16 am
 Maybe it is required to have the mod text plate ? I had it in my game when importing the blueprint book and blueprints contains text plate with the name of the operation
I was under the impression factorio could handle blueprints with missing modded entities gracefully, guess that only applies to the blueprint library then. Will update them to vanilla-only later today, in the meantime you can use the Textplates mod.
Top
Tertius
Filter Inserter
Filter Inserter
Posts: 667
Joined: Fri Mar 19, 2021 5:58 pm
Contact:
Contact Tertius

Re: Pairwise Arithmetic / each op each

Post by Tertius »

This hasn't anything to do with textplates - even with that mod, I'm unable to import the blueprint from the OP. The blueprint is just defective. Try it yourself, I bet it doesn't work for you as well. May be you edited the OP and broke the code, and mmmPI copied it before the edit.

By the way, you can show any extracted blueprint json like this (blueprint data in file "bp"):

Code: Select all

$ cat bp | tail -c +2 | base64 -d |openssl zlib -d | jq
Top
Nidan
Fast Inserter
Fast Inserter
Posts: 227
Joined: Sat Nov 21, 2015 1:40 am
Contact:
Contact Nidan

Re: Pairwise Arithmetic / each op each

Post by Nidan »

Tertius wrote: ↑
Thu Sep 29, 2022 3:10 pm
 This hasn't anything to do with textplates - even with that mod, I'm unable to import the blueprint from the OP. The blueprint is just defective. Try it yourself, I bet it doesn't work for you as well. May be you edited the OP and broke the code, and mmmPI copied it before the edit.

By the way, you can show any extracted blueprint json like this (blueprint data in file "bp"):

Code: Select all

$ cat bp | tail -c +2 | base64 -d |openssl zlib -d | jq
I fear the corruption happened on your side. Clicking the blueprint button and pasting it into a file gives me the same content as reexporting the book from factorio. (Also I hadn't edited the OP at that point.)
Here's a checksum of the blueprint

Code: Select all

$ sha512sum each\ op\ each.*
801404185c168f7077ae2064fd10304608513d1ba9d43644e0865ddb69b5110fa12e5775151b9d599f93a53a7e5e1db2053f81d58bd40eb728694d0b991014d9  each op each.blueprint
$ wc -c each\ op\ each.*
23206 each op each.blueprint
In any case…



Updated the OP, fixing the bugs found in the divider. Managed to to so without needing an extra tick, and only one extra combinator since I could remove some in other places.

Checksum and length of the updated blueprint, just in case:

Code: Select all

sha512: c9edd05d584bb3084264c5bf0efd642aff21cd32758bc9152eed0efd70888d8fa7aad16a9cf7b0ab2bb8d925812a1bdd137a99a5410890635a2782d2f3fe74a1
wc -c: 23374
Top
Tertius
Filter Inserter
Filter Inserter
Posts: 667
Joined: Fri Mar 19, 2021 5:58 pm
Contact:
Contact Tertius

Re: Pairwise Arithmetic / each op each

Post by Tertius »

Nidan wrote: ↑
Thu Sep 29, 2022 5:37 pm
 I fear the corruption happened on your side.
OMG, you're right. You never believe what was the cause. It's a Chrome browser extension that was changing website text. It's supposed to change some specific annoying gender notation in German language webpages (extension called "No Gender"). It's supposed to work with the German language, but it also triggered on some of the "random" base64 characters.
I apologize for all the confusion.

You made some very interesting combinator setups. Takes time to get to the bottom of them. Especially MIN and MAX is cool, although it's not very high-level if you think about it. All just simple math.
Top
User avatar
MEOWMI
Filter Inserter
Filter Inserter
Posts: 309
Joined: Wed May 22, 2019 12:21 pm
Contact:
Contact MEOWMI

Re: Pairwise Arithmetic / each op each

Post by MEOWMI »

This seems very useful. I've wanted to do several of these on more than once occasion but they're such a pain to make on the spot. And like you said, hard to find as well... Big thanks! Well done making them have full throughput, as well as cataloguing their latencies!

It is somewhat sad that mere division ends up being 125 combinators large... it's hilariously large really, but that's not your fault.
Top
mrvn
Smart Inserter
Smart Inserter
Posts: 5703
Joined: Mon Sep 05, 2016 9:10 am
Contact:
Contact mrvn

Re: Pairwise Arithmetic / each op each

Post by mrvn »

There is one more operation that could be added: select / filter.

Output all signals of the green wire that are present on the red wire. If the red wire has signals = 1 then you can multiply green * red and it takes an extra decider combinator and extra tick to normalize the red input. But maybe there is a better way?
Top
Nidan
Fast Inserter
Fast Inserter
Posts: 227
Joined: Sat Nov 21, 2015 1:40 am
Contact:
Contact Nidan

Re: Pairwise Arithmetic / each op each

Post by Nidan »

Tertius wrote: ↑
Thu Sep 29, 2022 6:10 pm
 OMG, you're right. You never believe what was the cause. It's a Chrome browser extension that was changing website text. It's supposed to change some specific annoying gender notation in German language webpages (extension called "No Gender"). It's supposed to work with the German language, but it also triggered on some of the "random" base64 characters.
Das erklärt dann natürlich warum da "BsIn" bei rauskommt.

MEOWMI wrote: ↑
Fri Sep 30, 2022 12:31 pm
 This seems very useful. I've wanted to do several of these on more than once occasion but they're such a pain to make on the spot. And like you said, hard to find as well... Big thanks! Well done making them have full throughput, as well as cataloguing their latencies!

It is somewhat sad that mere division ends up being 125 combinators large... it's hilariously large really, but that's not your fault.
Considering division and modulus are the slowest operations on a modern CPU out of those supported by combinators, them also being comlpex ingame seems par of the course. The big outliers are the shifts which are rather simple in hardware, but I had to resort to workarounds in factorio.

mrvn wrote: ↑
Fri Sep 30, 2022 2:18 pm
 There is one more operation that could be added: select / filter.

Output all signals of the green wire that are present on the red wire. If the red wire has signals = 1 then you can multiply green * red and it takes an extra decider combinator and extra tick to normalize the red input. But maybe there is a better way?
At some point I found a blueprint book which also contained setups for filtering.

Sadly, I forgot where I found it. From my div blueprint you can also extract adaptions that only work with 0/1 inputs on the filtering side.
Top
Nidan
Fast Inserter
Fast Inserter
Posts: 227
Joined: Sat Nov 21, 2015 1:40 am
Contact:
Contact Nidan

Re: Pairwise Arithmetic / each op each

Post by Nidan »

Expanded the OP a bit, mainly extracting stuff I already had built for the divider into individual blueprints. That's an unsigned multiplier producing the full result and the filters already mentioned in my last post. And with the unsigned long multiplier lying around, I might as well create the signed version of it… so I did. With those two done, there's another option for shifting right: shifting left and then taking the upper half of the result. Depending on which multiplier gets used this implements either an arithmetic right shift or a logic right shift.
All six new blueprints are contained in OP's blueprint book.
Top
User avatar
Hares
Fast Inserter
Fast Inserter
Posts: 127
Joined: Sat Oct 22, 2022 8:05 pm
Contact:
Contact Hares

Re: Pairwise Arithmetic / each op each

Post by Hares »

I've recenently managed to design almost-fully-functinoal vector to vector divisor. It has some flaws (i.e., it likes off-by-one errors due to calcuations precision), but it generally works for larger numbers.

Properties:
  • Latency: 4 (minimal) to (5 for safe/isolated version)
  • Constant Combinators: 0 (fixed presision) to 3 (configurable presision)
  • Arithmetic Combintarots: 6 (minimal) to 10 (safe, synchronized, isolated, configurable)
Limitations:
  • Requires pre-setting a special constant. The bigger the constant, the more accurate results are.
  • If that constant is not a multiple of divisor, off-by-one error may be present. The more factors that constant has the better.
  • If that constant is low enough, higher error will be present. That constant MUST be greater than any potential value in the denominator.
  • If that constant is high enough, the result will be 0.
  • I haven't tested yet for the factorial-like (pun unintended) numbers, but looks like these should behave better. In my playthrough I used powers of 10, and they didn't behave well enough: evaluating 40 / 40 resulted in 1, but 28 / 28 resulted in 0.
  • Looks like 2^4 * 3^3 * 5^4 * 7 * 11 = 20,790,000 might be a good number.
How it works:
  1. Divide a very big constant by a denominator
  2. Use vector multiplication to multilply a nominator by the result of previous operation
  3. Divide the result by that big constant

Code: Select all

R = A / B - what wee need to find
C - Constant

R = A / B = A * (1/B) = A * C/C * (1/B) = (A * (C/B)) / C
Screenshots Gallery
Version for Compact Circuits mod
Vanilla
Top
almania
Burner Inserter
Burner Inserter
Posts: 16
Joined: Sat Aug 11, 2018 6:11 am
Contact:
Contact almania

Re: Pairwise Arithmetic / each op each

Post by almania »

Ahh this is my pet obsession, glad to see others bit by the same bug. Well, kinda, actual goal is to build a per-signal computer some day, such that each signal is effectively its own core, independent programs, memory etc. Maybe I'm not alone there?

It is complicated though, as the variable latency of these kind of ops encourages speculative execution or at least somewhat requires stalls, I keep on getting stuck in the trap of putting it aside for months before revisiting. Ultimate goal I have is to produce the mandelbrot set someday, with each core working on its own pixel - this is something that used to be slow for PCs to do, let alone a 60Hz many-core in-game processor, so naturally seems reasonable to do.

That aside, some notes/spoilers:
  • DIV can be made accurate via computing MOD at the same time, and adjusting each if > the denominator, as you've got the result +/- 1 already. With some massaging of the recipricol, you can get it +0/-1, which makes it a bit easier.
  • SAR can be implemented the same as SLR, just use MULSH instead of MULUH.
  • MUL can be implemented in 3 cycles, 20 combinators. Hint: Try the identity:

    Code: Select all

    ab=((a + b)^2 - (a - b)^2) / 4
    Solution:
    ab=(a/4 + b)^2 - (a/4 - b)^2
    ab=((a>>2) + b)^2 - ((a>>2) - b)^2 + (a&2)*b + (a&1)*b
  • MULUH and MULSH can be computed at once, the adjustment between them is given in Hacker's Delight "High-Order Product Signed from/to Unsigned"
  • MUL/MULUH/MULSH can all be computed in a shared circuit of 76 combinators, latency 5. What I have is too much of a birdsnest to publish, but I'd be impressed to see the latency matched, beaten is likely impossible. I don't actually know how I achieved this, not any more.
  • FMUL and FDIV can be easily built on the above. FADD, not so much. Floating point is quite weird like that.

    Other wonky things that I like to have:
    • Signal IDer. For each new signal coming in, assign each a unique ID, including when signals appear in batches.
    • Variable delay line - take a count and value, emit the value after count cycles. Nice for quickly matching circuits (Compact Circuits is a godsend).
    • RNG per signal - this one's easy enough, use the above + a counter based RNG https://arxiv.org/abs/2004.06278. I do a much cruder version than this, but it looks good enough in numpy.
    • Circuit tester. Using the RNG, run 15k random OPs/s through two circuits, trapping if the signals don't match.
    • RAM - I have a really nice memory cell that I use, similar to your filtering blueprints. R/W has 2 cycle latency on the address, 1 cycle on the value (ie, a value can come in on a write, and out on the read on the very next cycle). It's really nice, and I suspect optimal.
    • Using the above or similar techniques: A queue.
    I don't mean to be a tease, just it's so many disorganised parts of things I've tried - a lot very birdsnesty. Here's the 32x32->32 multiply though, in case anyone wants to use it for inspiration (big spoiler):


    It is of course also possible that I have none of the above, but I'd like to see what people come up with - so do post designs
Last edited by almania on Sat Mar 09, 2024 12:50 am, edited 1 time in total.
Top
Post Reply

Return to “Combinator Creations”