Minimalist signal filtering device

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.
mmmPI
Smart Inserter
Smart Inserter
Posts: 2675
Joined: Mon Jun 20, 2016 6:10 pm
Contact:

Minimalist signal filtering device

Post by mmmPI »

Based on the wiki article about multiplier : https://wiki.factorio.com/Tutorial:Comb ... s.2FArrays

I have looked at this circuit to try and understand it and i think it can be made with less combinators but maybe i'm missing something.

The original contraption doesn't seem to properly restitute the value of a filtered signal when its value is around 2147483647 in instead show -1 , -2, and my version does the same have i done mistake somewhere ?

multiplier.png
multiplier.png (83.59 KiB) Viewed 6799 times




The math it does is : -1/2 [a²+b² -[a+b]²]

the red wire is used to make a+b before squaring them in the combinator the result is turned negative and summed with the other 2 combinators that does a² and b² this sum is then divided by -2.

It comes from the identity (a+b)²=a²+2ab+b² which is turned into 2ab= (a+b)²-a²-b² or ab=[(a+b)²-a²-b²]/2 or again ab= -1/2 * [a²+b² -[a+b]²] if you mutiply both numerator and denominator by -1.

Code: Select all

 (a+b)²  =   a²+2ab+b²
  2ab    =  (a+b)²-a²-b²
  ab     =  [(a+b)²-a²-b²]/2
  ab     =  -1/2 * [a²+b² -[a+b]²]
What is the purpose
i'm not quite sure yet, i've read that some user consider it very useful to filter signal for example, one constant holds the value iron=4 copper=9 coal=12 green circuit=8, and the other constant, you input only coal =1 and iron=1, and the resulting operation will be a filtering of only the value coal=12 and iron=4 at the end.

You can also use it to multiply a and b :)

gGeorg
Filter Inserter
Filter Inserter
Posts: 387
Joined: Wed Jun 19, 2019 8:06 pm
Contact:

Re: Minimalist signal filtering device

Post by gGeorg »

mmmPI wrote:
Mon Nov 29, 2021 8:23 am
filtered signal when its value is around 2147483647 in instead show -1 , -2, and my version does the same have i done mistake somewhere ?
It is overflow feature. It is there since von Neuman made first machines. :geek:
32 bits: maximum representable value 232 − 1 = 4,294,967,295
https://en.wikipedia.org/wiki/Integer_overflow


Purpose of filtering
is obvious when you try to make a load-unload service train. e.g. a train supplying defence wall, or a build train.
Imagine a situation your train has 20 different products, but you want to unload only those which are missing in the local logistic network. On top you want to quick loading process by stack inserters with "set_stack" feature. Ring a bell ?

Simplification is nice, I have to check it, if it realy works as intended. Perhaps, I could use it for my trains. :idea:

mmmPI
Smart Inserter
Smart Inserter
Posts: 2675
Joined: Mon Jun 20, 2016 6:10 pm
Contact:

Re: Minimalist signal filtering device

Post by mmmPI »

gGeorg wrote:
Mon Nov 29, 2021 8:48 am
It is overflow feature. It is there since von Neuman made first machines. :geek:
32 bits: maximum representable value 232 − 1 = 4,294,967,295
https://en.wikipedia.org/wiki/Integer_overflow
I know about that ( thanks to factorio) but i'm wondering if it's normal than the wiki machine is 'failing' at filtering signals whose value are triggering an overflow.

There is no blueprint on the wiki for that machine, i tried to reproduce it and then make a machine with similar functionnality as my reproduction. My machine seem to have similar output table than the one in the wiki, including the same overflow, but maybe it is because i did a mistake in copying the wiki's machine and then make a faulty machine of my own :D.
gGeorg wrote:
Mon Nov 29, 2021 8:48 am
Purpose of filtering
is obvious when you try to make a load-unload service train. e.g. a train supplying defence wall, or a build train.
Imagine a situation your train has 20 different products, but you want to unload only those which are missing in the local logistic network. On top you want to quick loading process by stack inserters with "set_stack" feature. Ring a bell ?

Simplification is nice, I have to check it, if it realy works as intended. Perhaps, I could use it for my trains. :-)
I think what you describe can be achieved with less complex combinators circuitry this feels like requiring a tank to kill a rat or a cannon to kill a fly, i don't know what the appropriate comparaison in other langage x)

Also I'm not sure my "simplification" is more simple when you try to use the contraption in practice since both constant are wired with both color of wire. but i hope it works as intended i just tested sets of random value by hand with extreme cases but i wasn't quite sure what to test else x).

gGeorg
Filter Inserter
Filter Inserter
Posts: 387
Joined: Wed Jun 19, 2019 8:06 pm
Contact:

Re: Minimalist signal filtering device

Post by gGeorg »

mmmPI wrote:
Mon Nov 29, 2021 9:18 am
i'm wondering if it's normal than the wiki machine is 'failing' at filtering signals whose value are triggering an overflow.
I understand combinators as raw_math_code_machines so they behave properly. Overflow is inevitable behaviour of numerical machines. Try any clock from wiki, it "suffer" this feature too. Definitely not bug but feature of all devices we have now, include wash machine in your kitchen.
mmmPI wrote:
Mon Nov 29, 2021 9:18 am
I think what you describe can be achieved with less complex combinators circuitry this feels like requiring a tank to kill a rat or a cannon to kill a fly, i don't know what the appropriate comparaison in other langage x)
Well, if you think so then try to make it. I have burned 50+ hours on such train station. It is not as easy as it appears.

mmmPI
Smart Inserter
Smart Inserter
Posts: 2675
Joined: Mon Jun 20, 2016 6:10 pm
Contact:

Re: Minimalist signal filtering device

Post by mmmPI »

gGeorg wrote:
Mon Nov 29, 2021 9:27 am
I understand combinators as raw_math_code_machines so they behave properly. Overflow is inevitable behaviour of numerical machines. Try any clock from wiki, it "suffer" this feature too. Definitely not bug but feature of all devices we have now, include wash machine in your kitchen.
I'm attempting to teach myself those with the help of the internet, and i am my own wash machine too :cry:

i'm often not too sure what i'm doing like maybe in intermediate step of calculus the overflow will make my machine only function with a certain range of value for "a" or "b" due to using a certain math formula instead of another.

which could or not make it impossible/unreliable to use. ( i can't tell since i don't understand the purpose of my creation it's an attempt at replicating something i discovered on the wiki ).

gGeorg wrote:
Mon Nov 29, 2021 9:27 am
Well, if you think so then try to make it. I have burned 50+ hours on such train station. It is not as easy as it appears.
I'm not saying it's easy, it took me more than 200 hours on the demo to understand the rail signal system before i decided to buy the game back in version 12 :lol:

but since then i've spent much much hours in the game say steam (in the middle of the 4 digit number) not counting the time i learn things from youtube and the forum :ugeek:

I don't have to start from nothing, i think in memory i have designs where you can set the value of required item in a constant combinator. Then you substract the value of the logistic network using a wire between a robotport "read logistic content" and arithmetic combinator *-1 and you feed the result for the inserters as "set filter".

It's not very precise and flexible given the restricted amount of filter per inserter at the same time but it does the job with enough time and if the train can supply enough material. You need to be careful on the schedule condition and size of chests.

You can use the overflow method to encode the value in the constant combinator as very high number and addition the quantity in the logistic network so that everything overflow to a negative number except the quantity that are not high enough in the logistic network It removes 1 combinator of the 2. ( this was a time someone explained me how to use overflow :) on this forum ).

If there are more complicated method using the multiplier as filter to offer more possibility/less constraint i maybe avoiding it in my subconscient because of lazyness and knowing 1 method already so i just go with what i know for most circuits, the times i do something different/new is more like puzzle game, logic exercise because i enjoy doing those :).

SoShootMe
Filter Inserter
Filter Inserter
Posts: 472
Joined: Mon Aug 03, 2020 4:16 pm
Contact:

Re: Minimalist signal filtering device

Post by SoShootMe »

mmmPI wrote:
Mon Nov 29, 2021 8:23 am
Based on the wiki article about multiplier : https://wiki.factorio.com/Tutorial:Comb ... s.2FArrays

I have looked at this circuit to try and understand it and i think it can be made with less combinators but maybe i'm missing something.
The original computes "red * green" while yours needs both red and green wires from two outputs.

Your version has an incorrect output for one tick whenever the input changes, because the "each*-1" combinator changes one tick later than the "each^2" combinators.

For both, I think the maximum value of a signal guaranteed to avoid overflow is floor(sqrt(2^31 - 1) / 2) = 23170. I'm not sure if the final output is the same in all cases where that isn't true.

mmmPI
Smart Inserter
Smart Inserter
Posts: 2675
Joined: Mon Jun 20, 2016 6:10 pm
Contact:

Re: Minimalist signal filtering device

Post by mmmPI »

SoShootMe wrote:
Mon Nov 29, 2021 11:25 am
1)The original computes "red * green" while yours needs both red and green wires from two outputs.

2)Your version has an incorrect output for one tick whenever the input changes, because the "each*-1" combinator changes one tick later than the "each^2" combinators.

3)For both, I think the maximum value of a signal guaranteed to avoid overflow is floor(sqrt(2^31 - 1) / 2) = 23170. I'm not sure if the final output is the same in all cases where that isn't true.
1) i understand this could be quite a limitation, or to restore the same functionnality as the one on the wiki some additionnal combinator would be required and then it means this version doesn't relly require less combinator. I'm not sure how it is supposed to be implemented in-game and if it would matter for all/some purposes.

2) This i had not thought about that's the kind of thing that could make the usage unreliable without additionnal dummy combinator to propagate the signal. I think it can be just 1, i will test in game and update some day :).

3) i have tested cases where it overflows and give the same results, but i'm not sure if the final output is the same for all cases either, i think the math required are function analisis and derivatives which i dislike/ are not intuitive to me.

thanks you for your review

Nidan
Fast Inserter
Fast Inserter
Posts: 225
Joined: Sat Nov 21, 2015 1:40 am
Contact:

Re: Minimalist signal filtering device

Post by Nidan »

mmmPI wrote:
Mon Nov 29, 2021 11:44 am
1) i understand this could be quite a limitation, or to restore the same functionnality as the one on the wiki some additionnal combinator would be required and then it means this version doesn't relly require less combinator. I'm not sure how it is supposed to be implemented in-game and if it would matter for all/some purposes.

2) This i had not thought about that's the kind of thing that could make the usage unreliable without additionnal dummy combinator to propagate the signal. I think it can be just 1, i will test in game and update some day :).

3) i have tested cases where it overflows and give the same results, but i'm not sure if the final output is the same for all cases either, i think the math required are function analisis and derivatives which i dislike/ are not intuitive to me.

thanks you for your review
1) This can be fixed by rewiring the constant combinators. One to top and bottom; the other to middle and bottom, using the other color
2) 1 delay combinator will do, correct. However there is a 5 combinator version for pairwise multiplication: (a^2 + b^2) / -2 + (a+b)^2 / 2. (No pictures as I'm not on a PC currently)
3) Main problem is that all combinator math is done modulus 2^32, i.e. results are truncated to 32 bits. I doubt function analysis as tought in school will help you here.

Tertius
Filter Inserter
Filter Inserter
Posts: 650
Joined: Fri Mar 19, 2021 5:58 pm
Contact:

Re: Minimalist signal filtering device

Post by Tertius »

If you just want to filter something, you don't always need an a*b multiplication. This is a generic solution, but you seldom need generic solutions.

In my experience, if you add and substract values from each other to get some result, at some point during the calculation your desired values are either all positive or all negative, and the undesired values have the opposite sign. At this point link a decider combinator with a EACH >0 or EACH <0 condition to get the desired values only.

If there is really the situation that you have line a with a bunch of signals, and you have line b with a different bunch of signals, and you want to get all signals from a where there is a non null value in b, I would use a custom hack. Slightly generic, but not fully.
Multiply the desired values (b) with some constant, so they are above a threshold. Add a. The desired values are now above the threshold, the not desired values below. This can be filtered, then revert the adding of the desired values.

There are the following realistic restrictions:
- all signals in a and b are positive
- no signal in a exceeds a maximum value. maximum^2 must not exceed 2^31, i. e. 46340. However, this restriction applies to the generic multiplying version as well.

1. #1 arithmetic: multiply b with 46340
2. add a to the output from #1. This makes all not desired values from a < 46340
3. #2 decider: From the sum, select EACH >= 46340
4. #3 arithmetic: multiply the output of #1 with -1
5. add the output from #2 to the output from #3 to revert the addition and get the actual numbers again.

Pro: works perfectly for all values from 0..4630, latency 2 ticks.
Contra: values must be positive and not exceed 46340.
1.png
1.png (43 KiB) Viewed 6718 times

combinator settings


Here is also another, completely different approach - a logic/binary approach with bit operations that allows values up to 2^31-1.

Select the desired values (b) as 1. Shift them 31 bits to the left (the leftmost bit in the combinator registers). This will appear as value -2147483647. Add the existing values (a). Now we have all values from a, and the leftmost bit is set to 1 for all values from b. So select all negative values, because these are the ones that have the leftmost bit set, which acts as filter bit. Then clear the leftmost bit by substracting the value we still have from the 2nd step.

1. #1 decider: create 0/1 from b for <>0 values
2. #2 arithmetic: shift left 31 bits to have a 1 in the leftmost bit for all nonzero values from b
3. add a to the output of #2.
4. #3 decider: filter values <0 from the result of 3., which are the values with the leftmost bit set
5. substract the leftmost bit. This is what we have as output from #2.

Pro: supports arbitrary values in b and positive values up to 2^31-1 in a
Contra: if a value in b changes from zero to nonzero or from nonzero to zero, the output becomes -2^31 for that value for one tick after 3 ticks. Can be avoided with an additional combinator, if necessary.
b.png
b.png (48.25 KiB) Viewed 6718 times

combinator settings
ps. if I had a wish granted to me, I wish 64-bit integer arithmetic in Factorio.

User avatar
DaveMcW
Smart Inserter
Smart Inserter
Posts: 3699
Joined: Tue May 13, 2014 11:06 am
Contact:

Re: Minimalist signal filtering device

Post by DaveMcW »

Tertius wrote:
Mon Nov 29, 2021 2:14 pm
Here is also another, completely different approach - a logic/binary approach with bit operations that allows values up to 2^31-1.
You can avoid the binary explanation by multiplying 1 * -2147483648.

You still need to explain the overflow magic: -4294967296 overflows to 0.

gGeorg
Filter Inserter
Filter Inserter
Posts: 387
Joined: Wed Jun 19, 2019 8:06 pm
Contact:

Re: Minimalist signal filtering device

Post by gGeorg »

Tertius wrote:
Mon Nov 29, 2021 2:14 pm
1. #1 arithmetic: multiply b with 46340


Pro: works perfectly for all values from 0..4630, latency 2 ticks.
Contra: values must be positive and not exceed 46340.
Instead of multiply/divide you could add/subtract value of half of range (e.g. 2^31/2 = 1 073 741 824),
then your working range is 0 ..1 073 741 823

That trick with bit shift is even better, because of double working range.

Tertius
Filter Inserter
Filter Inserter
Posts: 650
Joined: Fri Mar 19, 2021 5:58 pm
Contact:

Re: Minimalist signal filtering device

Post by Tertius »

gGeorg wrote:
Mon Nov 29, 2021 4:22 pm
Instead of multiply/divide you could add/subtract value of half of range (e.g. 2^31/2 = 1 073 741 824),
then your working range is 0 ..1 073 741 823
Of course. Dunno why I didn't come up with adding instead of multiplying in the first place. However, the maximum cannot be 1 073 741 823, because not only a + b must be < 2147483648 but actually the sum of every a + (b + constant) must be < 2147483648, otherwise the intermediate value used for comparing is interpreted as negative. So the maximum value for each a and b as well as the value to add is floor(2147483648 / 3) = 715827882.

This is a blueprint changed accordingly:


With this modification I prefer this variant, because the range is big enough without the glitch of one tick with -2^31. However, if you use the result for chest or inserter filtering, this is irrelevant. On the other hand, you will probably not need to handle more than 715827882 items in a chest or in some network.

Edit/Addition:
Ok, not adding but substracting is the final solution. If you substract 2147483648, you have the "full" half range for the intermediate values, because a and b are > 0 as requirement. Then a+b must be < 2147483648 resp. a+(b-2147483648) < 0, which is true for a, b in 0..1 073741823, so you have this as range.
So the changed steps:
1. Arithmetic #1: EACH + -2147483648 (you cannot do - 2147483648, because the GUI changes this to 2147483647)
3. Decider #2 condition: EACH < 0

Last edited by Tertius on Mon Nov 29, 2021 7:20 pm, edited 1 time in total.

gGeorg
Filter Inserter
Filter Inserter
Posts: 387
Joined: Wed Jun 19, 2019 8:06 pm
Contact:

Re: Minimalist signal filtering device

Post by gGeorg »

Tertius wrote:
Mon Nov 29, 2021 5:42 pm
not only a + b must be < 2147483648 but actually the sum of every a + (b + constant) must be < 2147483648, otherwise the intermediate value used for comparing is interpreted as negative. So the maximum value for each a and b as well as the value to add is floor(2147483648 / 3) = 715827882.
Or you can normalize (b) index signal so the range is [ half_of_signed_byte ( - 1) ] , for a cost of a combinator.


Image
Last edited by gGeorg on Mon Nov 29, 2021 7:24 pm, edited 2 times in total.

mmmPI
Smart Inserter
Smart Inserter
Posts: 2675
Joined: Mon Jun 20, 2016 6:10 pm
Contact:

Re: Minimalist signal filtering device

Post by mmmPI »

Nidan wrote:
Mon Nov 29, 2021 1:15 pm
1) This can be fixed by rewiring the constant combinators. One to top and bottom; the other to middle and bottom, using the other color
2) 1 delay combinator will do, correct. However there is a 5 combinator version for pairwise multiplication: (a^2 + b^2) / -2 + (a+b)^2 / 2. (No pictures as I'm not on a PC currently)
1) I updated the wiring and added the dummy combinator where i thought it fit to avoid the 1 tick wrong value during transition. It look like this :
6combinators filter and mutiplier


2) I think i managed to make the 5 combinators version from your formula it look like this:
5combinators filter and multiplier



Tertius wrote:
Mon Nov 29, 2021 2:14 pm
If you just want to filter something, you don't always need an a*b multiplication. This is a generic solution, but you seldom need generic solutions.

I would use a custom hack. Slightly generic, but not fully.

There are the following realistic restrictions:
- all signals in a and b are positive
- no signal in a exceeds a maximum value. maximum^2 must not exceed 2^31, i. e. 46340. However, this restriction applies to the generic multiplying version as well.

Pro: works perfectly for all values from 0..4630, latency 2 ticks.
Contra: values must be positive and not exceed 46340.
Thanks you ! I'm not going into the details of the build but few points ,

1)it does differs from the wiki and my original version for the negative value. (which i started testing after you mention it)
2)if the value exceed 46340 sometimes it appears to still function as a filter but not as a multiplier its not exactly as you say i think.

I called it the 3 combinators version and standardize it with the 6 and 5 version using only green wire when possible adding red only when necessary and using the same set of inputs as the other to make it easier to compare the outputs for various test value.
3combinator signal filter


Tertius wrote:
Mon Nov 29, 2021 2:14 pm
Here is also another, completely different approach - a logic/binary approach with bit operations that allows values up to 2^31-1.

Pro: supports arbitrary values in b and positive values up to 2^31-1 in a
Contra: if a value in b changes from zero to nonzero or from nonzero to zero, the output becomes -2^31 for that value for one tick after 3 ticks. Can be avoided with an additional combinator, if necessary.
This one i expected to be possible since it was mentionned in the other thread that the multiplier was made obsolete due to the introduction of bit operations. I think with your explanation i understand how it functions and added the 4rth combinator because there was no 4 combinator version yet !

This kind of operation i can only watch other people use and think it's cool, it's not coming to me naturally as a tool to solve problems yet :)

It's using the same test input as the others again to make it easy to spot the differences in output.
4combinators signal filter



For easier comparaison i also remade the original from the wiki as a blueprint with the same set of inputs but without changing the wiring.
7combinators signal filter and multiplier




Now i need more time to process the other feedback where i can read -2147483648 and 2^31/2 = 1 073 741 824 and the "overflow magic" it is becoming seemingly more and more complex as you reduce the number of combinators

thanks you for sharing :)

mrvn
Smart Inserter
Smart Inserter
Posts: 5682
Joined: Mon Sep 05, 2016 9:10 am
Contact:

Re: Minimalist signal filtering device

Post by mrvn »

Tertius wrote:
Mon Nov 29, 2021 5:42 pm
Ok, not adding but substracting is the final solution. If you substract 2147483648, you have the "full" half range for the intermediate values, because a and b are > 0 as requirement. Then a+b must be < 2147483648 resp. a+(b-2147483648) < 0, which is true for a, b in 0..1 073741823, so you have this as range.
So the changed steps:
1. Arithmetic #1: EACH + -2147483648 (you cannot do - 2147483648, because the GUI changes this to 2147483647)
3. Decider #2 condition: EACH < 0
If your range is 0 .. 1_073_741_823 then you could adjust your constant and shift the range to -536_870_912 .. 536_870_911. Would need an extra combinator at the end to shift the result back to negative numbers. Still better than the multiplicating version with it's range of +-46k.

It would be great if you could add both constructs (full positive range and adjusted for negatives) with your explanation to the wiki.

mmmPI
Smart Inserter
Smart Inserter
Posts: 2675
Joined: Mon Jun 20, 2016 6:10 pm
Contact:

Re: Minimalist signal filtering device

Post by mmmPI »

mmmPI wrote:
Mon Nov 29, 2021 7:07 pm
This one i expected to be possible since it was mentionned in the other thread that the multiplier was made obsolete due to the introduction of bit operations. I think with your explanation i understand how it functions and added the 4rth combinator because there was no 4 combinator version yet !
DaveMcW wrote:
Mon Nov 29, 2021 4:11 pm
Tertius wrote:
Mon Nov 29, 2021 2:14 pm
Here is also another, completely different approach - a logic/binary approach with bit operations that allows values up to 2^31-1.
You can avoid the binary explanation by multiplying 1 * -2147483648.

You still need to explain the overflow magic: -4294967296 overflows to 0.
I mixed up several things here, what Tertius made is a not a multiplier (supposed to be used a signal filter in practice), it a signal filter for practical use ( which doesn't act as multiplier though), which can be done without the bit operation and instead multiplying the different 1 value from combinator 1 by *-2147483648 inside combinator 2, the overflow magic mentionned by DaveMcW is allowing the sum of 2 number close to -2147483648 to overflow to value close to 0 at the last step ( 5). [if i'm understanding correctly]

What i expected to be possible is a multiplier less complex than the one in the wiki that is using seven combinators, my corrected version uses 6 but the version made with Nidan's formula uses only 5.

However none of those uses bit operation which may even reduce that number further. ( it wouldn't be "just" a signal filter but the more generic logic "a*b")

but then i named the topic "signal filtering device" which is not a good title it could have also been "multiplier". or maybe as I'm interested in both "multiplier and other signal filtering device" :)

Tertius
Filter Inserter
Filter Inserter
Posts: 650
Joined: Fri Mar 19, 2021 5:58 pm
Contact:

Re: Minimalist signal filtering device

Post by Tertius »

The "overflow magic" in my example happens when 1 << 31 = -2147483648 = binary 1000 0000 0000 0000 0000 0000 0000 0000 is added to a value with binary 1xxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx.
You do (this is binary, only 0 or 1. 1+1 is 10):

Code: Select all

  1xxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx
+ 1000 0000 0000 0000 0000 0000 0000 0000
-----------------------------------------
1 0xxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx

becomes due to overflow:
  0xxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx
The leftmost 1+1 become 10, and because we don't have a 33th bit to the left, the leftmost 1 ist lost and we simply get 0xxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx, which is the original value from a.

If you want to design something that depends on the bit-representation of the values, you need to think in binary values. And you need to know the representation of negative numbers (two's-complement) and why this is used. And if you cannot think in binary (I cannot, too many digits), you need to write all the 32 bits in 0 and 1 on paper and use the paper for thinking.

mmmPI
Smart Inserter
Smart Inserter
Posts: 2675
Joined: Mon Jun 20, 2016 6:10 pm
Contact:

Re: Minimalist signal filtering device

Post by mmmPI »

Tertius wrote:
Mon Nov 29, 2021 7:41 pm
The "overflow magic" in my example happens when 1 << 31 = -2147483648 = binary 1000 0000 0000 0000 0000 0000 0000 0000 is added to a value with binary 1xxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx.
You do (this is binary, only 0 or 1. 1+1 is 10):
I figured this out that's where you can multiply by -2147483648 instead of doing the bit shifting, it has the same consequences. the output will be the same in binary.

i think this is a particular case since all initial value are exactly 1. It wouldn't be the case if some of the b value were =10 for example, then 10<<31 = 0, and the filter is broken. (same with 10*-2147483648=0 )

This is where it differs from a multiplier which would requires the value from b to be not only 1 if i'm following this correctly. some data is lost before the bit shifting to make all b value =1, because otherwise you can't use <<31.

It it is more intuitive to me to call it overflow when it happens due to an operation that result in a very large number rather than when you do 1<<31 which for me is still a bit mysterious since it require thinking about the binary form of the number and i'm not used to it. Where for the large number it's easier for me to picture the numbers written on a cylinder of paper and starting over after a large number.

still 10*-2147483648=0 is not intuitive none of that is x).

mmmPI
Smart Inserter
Smart Inserter
Posts: 2675
Joined: Mon Jun 20, 2016 6:10 pm
Contact:

Re: Minimalist signal filtering device

Post by mmmPI »

Tertius wrote:
Mon Nov 29, 2021 7:41 pm
If you want to design something that depends on the bit-representation of the values, you need to think in binary values. And you need to know the representation of negative numbers (two's-complement) and why this is used. And if you cannot think in binary (I cannot, too many digits), you need to write all the 32 bits in 0 and 1 on paper and use the paper for thinking.
on a joke side : I think i have an idea to replace paper by 32 or 64 lamps. Also i would need a contraption that convert my base 10 number into binary. this way less writing :d

i have seen couple basic explanation on two's complement, but haven't used much because either no purpose for me personnaly for what i've been doing or maybe when i could use it i didn't recognize it.

It would be the number that is represented by the opposite of the 32 lamps in my idea i think, if a number is represented with 32 lamps on or off, then you imagine the lamp that are on are instead off and vice versa. or you just plug in a unary not gate as pictured on the wiki to every lamp :)

Tertius
Filter Inserter
Filter Inserter
Posts: 650
Joined: Fri Mar 19, 2021 5:58 pm
Contact:

Re: Minimalist signal filtering device

Post by Tertius »

mmmPI wrote:
Mon Nov 29, 2021 8:11 pm
i think this is a particular case since all initial value are exactly 1. It wouldn't be the case if some of the b value were =10 for example, then 10<<31 = 0, and the filter is broken. (same with 10*-2147483648=0 )
To understand, write down the binary representation of a result, i. e. 1 * 2147483648 and 10 * 2147483648.

1 * 2147483648 is 2147483648, which is binary 1000 0000 0000 0000 0000 0000 0000 0000 (32 bit)

10 * 2147483648 is 21474836480, which is binary 101 0000 0000 0000 0000 0000 0000 0000 0000 (35 bit).
Since the combinator cannot store bits 33-35, these bits are lost ("overflow") and what remains are the rightmost 32 bit: 0000 0000 0000 0000 0000 0000 0000 0000, which happens to be all 0, which is 0 in decimal.

For converting to binary notification, I recommend the Windows 10 calculator app. It has a "Programmer" mode, where you can very easily enter and convert decimal and binary values and always see their binary representation. Unfortunatly it is 64-bit, so you need to take only the rightmost 32 bit.

Post Reply

Return to “Combinator Creations”