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
mrvn
Smart Inserter
Smart Inserter
Posts: 5709
Joined: Mon Sep 05, 2016 9:10 am
Contact:
Contact mrvn

Re: Pairwise Arithmetic / each op each

Post by mrvn »

almania wrote: ↑
Fri Mar 08, 2024 11:02 am
 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.
You are always limited by a loss of percision depending on how large your divisor is. And for exact results you have to mul the answer of the first result and then correct by one. So just for correcting the result that's your 76 gates and 5 ticks latency minimum. And now you need this at every train stop.

It's just not practical nor is it fun.

PS: I'm not sure you actually can (easily) get a result with at most off by one sind the divisior of every signal can be different and you would have to massage the recipricols of each signal differently.
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 »

Train stops is an entirely different game, al beit, the actual game.

But for those masochists thinking of building a computer - who wants to put +/- errors on the operations it offers?

The massaging from memory was just a combinator or two looking at the divisor coming in, adjusting the recipricol on the tick it's outputted to prevent overestimate errors. Nothing major - I tend to figure these out on numpy or pytorch, just trying all combination of inputs for various bit widths. If the math checks out for 4 bits through 12+ bits, it likely does for 32 bits too.

EDIT: At the very least, the MOD operation could be made accurate. It already has the extra delay, after all.
Top
mmmPI
Smart Inserter
Smart Inserter
Posts: 2747
Joined: Mon Jun 20, 2016 6:10 pm
Contact:
Contact mmmPI

Re: Pairwise Arithmetic / each op each

Post by mmmPI »

almania wrote: ↑
Fri Mar 08, 2024 11:02 am
 Signal IDer. For each new signal coming in, assign each a unique ID, including when signals appear in batches.
I know this one exist as part of another contraption, there's a blueprint there :
viewtopic.php?p=602838#p602838
almania wrote: ↑
Fri Mar 08, 2024 11:02 am
 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.
I dont know how good it would look on numpy, like how good would be the distribution but i made this contraption that give you random number between 0 and the boundary you choose as signal B



i tried to implement the following javascript piece which i alrerady made up myself so there's a double layer of inaccuracies x) :

Code: Select all

 
  seed ^= seed << 13;
  seed ^= seed >> 17;
  seed ^= seed << 5;
  return seed < 0 ? ~seed + 1 : seed;
where ^= is the xor operation of factorio
and the last lane was changed to get rid of negative number by doing *1 instead.

I think i had the idea/method reading some math from how it was done like in the 1960's to generate random number good enough for weather forecast model, maybe that's where the 13 17 and 5 value come from, but then i DIY the code because i was not in need of something super precise in distribution.
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 »

Ah that'll work, but not per signal.



This one is stateless, so it doesn't "self-count" - put values on the left, random hashes come out the right. Useful as it makes it easy to reset/reproduce, there's no feedback within it, etc.

It doesn't reduce the range, giving 32bit x 2 out, so you'll want your own bit masking and/or modulo out the right (note half the numbers will be negative).

Fun thought: with 256 signals in it'll produce over 2bn values a day.

EDIT: A Compact Circuits print of that: , ctrl-left click to configure.
Last edited by almania on Sat Mar 09, 2024 3:28 am, edited 1 time in total.
Top
mmmPI
Smart Inserter
Smart Inserter
Posts: 2747
Joined: Mon Jun 20, 2016 6:10 pm
Contact:
Contact mmmPI

Re: Pairwise Arithmetic / each op each

Post by mmmPI »

almania wrote: ↑
Fri Mar 08, 2024 10:42 pm
 Ah that'll work, but not per signal.
Right, the thread is for pairwise operation :roll: so I made a pairwise version using the pairwise Xor from Nidan to implement the same method of bit shifting for pseudo randomness :


almania wrote: ↑
Fri Mar 08, 2024 10:42 pm
 This one is stateless, so it doesn't "self-count"
I'm not sure what you mean. It seem to me that when your blueprint is stopped it keep track of a state so that it restart from that state, otherwise when being copy pasted it generates always the same sequence. When paused and restarted it is not the same sequence as when first copy pasted. isn't that what is called having (internal) state ?
But you mean it doesn't take part in the random number generation itself ? That i see the difference; your method doesn't need the previous result to compute the next instead it keep track of some form of time so it is faster in latency than the newer version i made which is quite slow. Is this the "self-count" ? To me those are different things but i'm not too sure about the wording.
almania wrote: ↑
Fri Mar 08, 2024 10:42 pm
 It doesn't reduce the range, giving 32bit x 2 out, so you'll want your own bit masking and/or modulo out the right (note half the numbers will be negative).

- put values on the left, random hashes come out the right. Useful as it makes it easy to reset/reproduce, there's no feedback within it, etc.
I don't understand the purpose/ use case of the contraption to be honest, on the previous one half of the combinators were used to filter out the negative numbers because i thought i'd be better but reading your comment it seem you are more interested in keeping them, may i ask why ? I made the new one not remove the negative numbers.

I also added a constant combinator so you can turn off the contraption with a button easily, but that means 1 signal can't be used as input value as it's the control signal to reset. It really RESET the contraption, it does not pause and resume from the previous state. It will generate the same sequence as if just copy pasted. That could be changed to act like yours so that when clicking the button twice it would resume. But i wished to understand the reasons i'd be trying it before.

To decrease latency, one could initialize the contraption not with a set of value, but with a set of 9 fed at different tick because although there is latency the input could be changed every tick without causing problem ( no loops ) This to aim at giving an ouput hash everytick. From 9 different sequences alternating.But I'd rather use your bp at this point because it would make my attempt much bigger footprint, the slow one is the same size already.
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 »

mmmPI wrote: ↑
Sat Mar 09, 2024 1:59 am
 I'm not sure what you mean. It seem to me that when your blueprint is stopped
Ah sorry, my bad - made some last second changes, adding a counter to the left of the mixer to show how it might be used. The actual mixer is the two substations and everything in between.

I also added lamps to go with it, but forgot to include them in the print, they may have made it clearer. Clearly I was struggling this morning.

Edited the post above to include now if you want to try the blueprint again, and if you have Compact Circuits installed, do check the other print ;)
mmmPI wrote: ↑
Sat Mar 09, 2024 1:59 am
 I don't understand the purpose/ use case of the contraption to be honest, on the previous one half of the combinators were used to filter out the negative numbers because i thought i'd be better but reading your comment it seem you are more interested in keeping them, may i ask why ?
Ah, because it's nice to have 32 random bits - far easier to remove than to bring them back. I use it for testing circuits with random data, so it's good to include negatives in that.

To mask out the sign for a 31 bit random number, just add an "EACH & <hold down the 1 key>" arithmetic combinator. When you close the configure screen, the constant will saturate to the largest value, 0x7fff'ffff, masking out the sign bit from all of its inputs.

A sample use of the sign bit: those lamps that I forgot to include, they can have a simple condition of < 0 to turn on. If it came pre-masked, you'd need > 1073741823 or an additional &/% combinator instead, a bit more cumbersome.
mmmPI wrote: ↑
Sat Mar 09, 2024 1:59 am
 To decrease latency, one could initialize the contraption not with a set of value, but with a set of 9 fed at different tick because although there is latency the input could be changed every tick without causing problem ( no loops ) This to aim at giving an ouput hash everytick. From 9 different sequences alternating.But I'd rather use your bp at this point because it would make my attempt much bigger footprint, the slow one is the same size already.
Yeh that'd be a neat trick, would work. Nice work on that. Would be very hard to make it pauseable/on-demand per-signal though.
Top
mmmPI
Smart Inserter
Smart Inserter
Posts: 2747
Joined: Mon Jun 20, 2016 6:10 pm
Contact:
Contact mmmPI

Re: Pairwise Arithmetic / each op each

Post by mmmPI »

almania wrote: ↑
Sat Mar 09, 2024 3:54 am
 Ah sorry, my bad - made some last second changes, adding a counter to the left of the mixer to show how it might be used. The actual mixer is the two substations and everything in between.
No problem , i think it was just me not fully understanding your wordings/blueprint. The RNG you showed doesn't need a state for generating the next value, it was only an ease of use/convenience outside of the stricly necessary logic to constitute the RNG. Whereas with the Xorshift method, it's fundamentally different. Wether or not some convenience combinators are added won't change the fact that it transform previous result to generate randomness.

There are still wordings i'm not familiar with like : MUL/MULUH/MULSH.

But i was able to find a proper source for the "Xorshift" value of 17 13 and 5, it's actually those used to illustrate on the wikipage. There are informations on others algo on the page of the discoverer too and i suppose also the information i lacked to know how to evaluate the distribution of random numbers with good methodoly. I didn't remember i was the one who discarded negative numbers, so i am more certain now that not removing them isn't going to break the logic :)
almania wrote: ↑
Sat Mar 09, 2024 3:54 am
 Ah, because it's nice to have 32 random bits - far easier to remove than to bring them back. I use it for testing circuits with random data, so it's good to include negatives in that.
That's a use case for me too now ! I had not thought about that but it is often the case that i manually input random value to test things. This would allow to test bigger quantities for artifacts, not just single entry points for early test. To bring negative number back one could always use a RNG that do only positive number to randomly multiply another positive randomly generated number by 1 or *-1. That doesn't sound too hard to me :D but i see now how it would make no sense if you could just keep the negative numbers in the first place for that use case.
almania wrote: ↑
Sat Mar 09, 2024 3:54 am
 To mask out the sign for a 31 bit random number, just add an "EACH & <hold down the 1 key>" arithmetic combinator. When you close the configure screen, the constant will saturate to the largest value, 0x7fff'ffff, masking out the sign bit from all of its inputs.
I'm not familiar with hexadecimal, but i understand what you meant, triggering overflow in the combinator box, i used it to change the way negative number are filtered on the not-pairwise version of the xorshift rng. It saves some combinators :) The use case i had for positive numbers only was to pick a choice amongst options for animations to make random walks or select variant of images that's not in factorio but still it's the RNG that made me curious because of that.

almania wrote: ↑
Sat Mar 09, 2024 3:54 am
 Yeh that'd be a neat trick, would work. Nice work on that. Would be very hard to make it pauseable/on-demand per-signal though.
Thank you but to be fair it was somewhat of an accidental discovery ; if you turn on/off the constant with the initial value instead of the control constant, you can mess up with the current cycle and reduce the latency by initiating new sequences mid cycle, it was uncontrolled but it doesn't need be i thought, before realizing how bigger it would make it.
To store the state, I think it would require an additionnal memory cell to store 1 tick worth of random output until another 1 red signal is detected. I think it's doable if you intercept them before they go in the decider combinator that currently check for the presence of 1 red signal to allow the loop. But maybe one has to restrict the input signals by 1 additionnal channel. So that would be 1 thread less for the computer you described. And it would be even (unecessarily) bigger.

The design you made also provide values on green and red wires. So that's 2 set, whereas it's only 1 for the Xorshift i made. I added it in my library !
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 »

mmmPI wrote: ↑
Sat Mar 09, 2024 10:23 am
There are still wordings i'm not familiar with like : MUL/MULUH/MULSH.
Okay, so think of each 32 bit number as a "digit".

When you multiply two digits together, eg -5x7, you may get a two digit result (-35). The -3 there is the overflow, and the same happens in binary.

In two's complement notation, the low word (5) works out the same whether you treat the operands as signed or unsigned, so it's simply MUL.

But the high operand contains the sign representation, so whether it's a -3 or a 3 is significant.

That's MULSH vs MULUH, mul unsigned high word vs mul signed high word.

One treats the operands as signed, the other unsigned. Each returns that high digit, the one that would otherwise be discarded.

For 8 bit maths, the difference is 0x80*1 = 0x00'80 (unsigned) vs 0xFF'80 (signed).

Why is this useful? Fixed point maths, eg multiplying by reciprocals or floating point maths.

There, you may want to treat a number as a fraction, eg a range of [-1, 1). Here the largest possible number is "almost 1", and so multiplying a number by it should give almost the same number. For that, you need to do a large shift after the multiply, and for that, you need that upper digit.

So being able to produce the high result in 5 cycles means, effectively, that you can multiply by a fraction in 5 cycles - which is pretty useful.

HTH.
Top
Qon
Smart Inserter
Smart Inserter
Posts: 2118
Joined: Thu Mar 17, 2016 6:27 am
Contact:
Contact Qon

Re: Pairwise Arithmetic / each op each

Post by Qon »

almania wrote: ↑
Fri Mar 08, 2024 11:02 am
 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.
Signal ID is just
[each] != 0 => [each] 1
or combinassembly syntax
and then multiply [each] by the ID of each signal type, from constant combinators or my blueprint. It's quick and non-colliding.
almania wrote: ↑
Fri Mar 08, 2024 11:02 am
  • Circuit tester. Using the RNG, run 15k random OPs/s through two circuits, trapping if the signals don't match.
For trapping, just use my mod https://mods.factorio.com/mod/PauseCombinator if it's just for testing. Don't make a convoluted pausable circuit when you can just pause the game on a circuit condition.
almania wrote: ↑
Fri Mar 08, 2024 11:02 am
  • 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.
Similar RAM design as I'm using?

Code: Select all

.global mem 10
at https://qon.github.io/combinassembly/ for bp (ignore instruction pointer hardware at the bottom)
almania wrote: ↑
Fri Mar 08, 2024 11:02 am
  • Using the above or similar techniques: A queue.
Fixed length queue is trivial of course.
A variable length queue is trickier but shouldn't be too hard, just a variant of RAM and a stack with added hardware for shifting values in parallel on each memory cell. Should maybe be possible to complete both shift and push operations in 1 tick, otherwise a 2 tick latency with operations each tick.
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: ↑
Sat Mar 09, 2024 10:23 am
 There are still wordings i'm not familiar with like : MUL/MULUH/MULSH.
It has already been answered, but I'll add my 2c as well:
MUL, like in my first post, is obviously multiply. For the other two, it depends on which variant of assembly/abbreviations you currently work with. I was first trying to read MULUH as "multiply upper half", i.e. returning the upper half of the full/mathematical multiplication result (with "MUL" or "MULLH" giving the lower half); but then MULSH wouldn't fit. After a bit of thinking what it could be instead: a letter switching between U and S often means "unsigned" resp. "signed", which leads to "multiply (un)signed high".

almania: I suggest you write the full name of the instruction the first time you use them, since they'll be interpreted differently depending on what the reader is used to and completely ununderstandable for someone unfamiliar with assembly, like mmmPI.

almania wrote: ↑
Fri Mar 08, 2024 11:02 am
 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):

If that bp is supposed to be a normal multiplier ("32x32->32" bit?), why does it look like it has 4 input wires? I've tried to connect the same colored inputs to get down to two inputs, however the results are different to the multiplier from the OP, so there's a mistake somewhere…
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 »

Qon wrote: ↑
Sat Mar 09, 2024 4:31 pm
 Similar RAM design as I'm using?

Code: Select all

.global mem 10
at https://qon.github.io/combinassembly/
on my phone, but I can't see a blueprint there? Gives source code.

Possibly though, how have you done w/ R/W latencies?
Nidan wrote: ↑
Sat Mar 09, 2024 4:49 pm
 If that bp is supposed to be a normal multiplier ("32x32->32" bit?), why does it look like it has 4 input wires? I've tried to connect the same colored inputs to get down to two inputs, however the results are different to the multiplier from the OP, so there's a mistake somewhere…
Possible mistake, I'm pretty bad at pasting blueprints it seems.

I try to offer all 3 input combos where possible: GRN/RED on the same input connection, or GRN/GRN or RED/RED across two.

Feel this is good when possible, as it's useful when you're pulling from a source where you can't side swap without adding latency or duplication (registers/memory), as you can just wire up whatever wires you've got.

If you used GRN on one and RED on the other, I'd suspect you'd get nothing out - if you shorted them together, (A+B)^2 maybe. Does that fix it?
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 »

almania wrote: ↑
Sat Mar 09, 2024 5:03 pm
 I try to offer all 3 input combos where possible: GRN/RED on the same input connection, or GRN/GRN or RED/RED across two.
I see. Accounting for that makes the output identical, and since it is a straight improvement (-2 ticks, -19 combinators) over the one from the OP, I'll be stealing this one.
Top
Qon
Smart Inserter
Smart Inserter
Posts: 2118
Joined: Thu Mar 17, 2016 6:27 am
Contact:
Contact Qon

Re: Pairwise Arithmetic / each op each

Post by Qon »

almania wrote: ↑
Sat Mar 09, 2024 5:03 pm
Qon wrote: ↑
Sat Mar 09, 2024 4:31 pm
 Similar RAM design as I'm using?

Code: Select all

.global mem 10
at https://qon.github.io/combinassembly/
on my phone, but I can't see a blueprint there? Gives source code.
If you paste the code there (replace the demo prefill) and then press assemble you get the BP

https://fbe.teoxoy.com/?source=0eNrtnd9 ... 8DN/UP7w==
almania wrote: ↑
Sat Mar 09, 2024 5:03 pm
 Possibly though, how have you done w/ R/W latencies?
If you read on the tick after write you get the old value. I'm guessing you are combining the write wire with the read wire somehow to bypass the memory cell not having propagated the updated value? Maybe I should do the same for my RAM?
Top
Tertius
Filter Inserter
Filter Inserter
Posts: 671
Joined: Fri Mar 19, 2021 5:58 pm
Contact:
Contact Tertius

Re: Pairwise Arithmetic / each op each

Post by Tertius »

mmmPI wrote: ↑
Sat Mar 09, 2024 10:23 am
 I'm not familiar with hexadecimal
Think of hexadecimal as an abbreviation of binary notation. To inspect the inner working of 32-bit integer arithmetic as it is used in Factorio, you will often want to write all bits explicitly, for example for 123456 you write 00000000000000011110001001000000 or 0000 0000 0000 0001 1110 0010 0100 0000. I created groups of 4 bit for readability. Now each of these 4 bit represent a number of 0..15 on its own, and the hexadecimal number system (base 16) has conveniently one digit for 0..15. We use 0..9 for 0..9 and A..F for 10..15.

Take again the binary notation of 123456 with groups of 4 bit:
bin → dec → hex
0000 → 0 → 0
0000 → 0 → 0
0000 → 0 → 0
0001 → 1 → 1
1110 → 14 → E
0010 → 2 → 2
0100 → 4 → 4
0000 → 0 → 0

So instead of 0000 0000 0000 0001 1110 0010 0100 0000 each group of 4 bit gets 1 hexadecimal digit and you write the much shorter 0x0001e240. The 0x prefix tells this is a hexadecimal number.

Learn this table by heart (for programmers as important as the multiplication tables from 1..10 * 1..10 you learn as a child):
dec → bin → hex
0 → 0000 → 0
1 → 0001 → 1
2 → 0010 → 2
3 → 0011 → 3
4 → 0100 → 4
5 → 0101 → 5
6 → 0110 → 6
7 → 0111 → 7
8 → 1000 → 8
9 → 1001 → 9
10 → 1010 → A
11 → 1011 → B
12 → 1100 → C
13 → 1101 → D
14 → 1110 → E
15 → 1111 → F

Now if you read something like 0x0001e240, you immediately know that this "E" in that number for example is a 1110 and you can directly translate between hex and bin. Since you often work with single bits in programming, the preferred notation for programming is hexadecimal, because you can directly see which bits are 0 and which are 1 without needing a calculator. Most important is usually the MSB (most significant bit, 0x80000000) and the LSB (least significant bit (0x00000001). Seeing a hexadecimal number, you immediately see whether these bits are set or not.

(sorry for the little digression).
Top
mmmPI
Smart Inserter
Smart Inserter
Posts: 2747
Joined: Mon Jun 20, 2016 6:10 pm
Contact:
Contact mmmPI

Re: Pairwise Arithmetic / each op each

Post by mmmPI »

almania wrote: ↑
Sat Mar 09, 2024 3:23 pm
 That's MULSH vs MULUH, mul unsigned high word vs mul signed high word.
One treats the operands as signed, the other unsigned. Each returns that high digit, the one that would otherwise be discarded.
Up to this point i can make sense of what you say , but then it start sounding esoteric.
almania wrote: ↑
Sat Mar 09, 2024 3:23 pm
 For 8 bit maths, the difference is 0x80*1 = 0x00'80 (unsigned) vs 0xFF'80 (signed).
Why is this useful? Fixed point maths, eg multiplying by reciprocals or floating point maths.
There, you may want to treat a number as a fraction, eg a range of [-1, 1). Here the largest possible number is "almost 1", and so multiplying a number by it should give almost the same number. For that, you need to do a large shift after the multiply, and for that, you need that upper digit.
So being able to produce the high result in 5 cycles means, effectively, that you can multiply by a fraction in 5 cycles - which is pretty useful.
HTH.
I read that several time , and thank you for your attempt at explaining but you may have overestimated my starting level x) I have never used floating point maths, I only learned binary thanks to factorio, which i play a lot more than diablo 2 i was a kid back then and that consituted my biggest exposure to hexadecimal because to edit the savegame you had to modify some value that look like what you used, I didn't know it was also called 8 bit math. Maybe it will take a few days for " you need to do a large shift after the multiply" to make sense for me or some actual practice with 8bit notations. Maybe learning with the colors , from RGB to hex, as a starter, keep the fraction and operation for later :)
Nidan wrote: ↑
Sat Mar 09, 2024 4:49 pm
 It has already been answered, but I'll add my 2c as well:
MUL, like in my first post, is obviously multiply. For the other two, it depends on which variant of assembly/abbreviations you currently work with.
Always welcome and appreciated ! I'm even less familiar with assembly abreviations than hexadecimal, i tried to google the terms but "MULSH multiplication" was mostly about the increasing number of people using "mulch" for their trees. And those were not even math trees. I'm not really working anyway, i was really inspired by the last FFFs and i decided to try to code some things using randomness. I have no use case for assembly langage currently , but knowing it works with hex value is a brick i have in mind now. I know there are some mods that always looked like next level for me with assembly instructions. But i gotta learn step by step x).
Tertius wrote: ↑
Sat Mar 09, 2024 5:51 pm
 Now if you read something like 0x0001e240, you immediately know that this "E" in that number for example is a 1110 and you can directly translate between hex and bin
(sorry for the little digression).
Thank you for that digression, i am a child half of the time, have tendancies to get drawn in arguments, and i'm not an experimented programmer, but your explanations managed to adress all those angles to still provide insights that are accessible. And maybe that's just me being an ignorant proud of that newly acquired common knowledge that i was the only one missing there, but i think it will be helpful for other person too :) It's like all the dots are connected now ! There's not always the 0x in front though right ? like for HTML colors it's #F43203 , this is a real color, but #F432031 is a mistake because that wouldn't fit as 3 x 255 for RGB or #E4FG63 is not a color because G is not representing any quadbit in hex notation. Now i think i understand how to make gradiants with hex colors. That would be an introduction to operation already. It was not in vain !

Now fractions sound a lot more complex, could be of real use for probabilities but i don't know if it would be a digression or not. I don't even know if it would differ in binary notation that just "non-integers" and how difficult it would be to do some pairwise operation showing a decimal parts in the results.
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 »

almania wrote: ↑
Fri Mar 08, 2024 11:02 am
 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
You could have mentioned the technical reason for the division by 4. At first glance this looks like a similar version to the common

Code: Select all

a * b = ((a + b)^2 - a^2 - b^2) / 2
. After some playing around with it I see it now: The interesting part here is that you avoid the division (and thus the introduction of inaccuracies) by moving it to the front and then fixing up the result.

Even if they're not presentable currently, I'd like to see your long multipliers (or MULUH, MULSH as you called them). Improvements will benefit division and right shifts as well.


Incorporated your multiplier into the collection, left shift also got a bit smaller a consequence. I also found and removed some redundancy in the divider.
Updated the OP.
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 »

mmmPI wrote: ↑
Sat Mar 09, 2024 10:19 pm
Now fractions sound a lot more complex, could be of real use for probabilities but i don't know if it would be a digression or not. I don't even know if it would differ in binary notation that just "non-integers" and how difficult it would be to do some pairwise operation showing a decimal parts in the results.
As you're getting the hang of hex, you may surprise yourself. You may need windows calculator in programming -> Hex mode though.

Code: Select all

0x01 * 0x80 = 0x0080 (1 * 128 = 128)
0x02 * 0x80 = 0x0100 (2 * 128 = 256)
0x03 * 0x80 = 0x0180 (3 * 128 = 384)
0x04 * 0x80 = 0x0200 (4 * 128 = 512)
0xFF * 0x80 = 0x7F80 (255 * 128 = 32640)
That's normal multiplies. Now I think you'd agree, even though these are integers, there could be a "decimal point" after each number. That 0x80 and 0x80.0 are the same number (even if it looks/feels weird).

All fractional stuff is doing, is moving that decimal point left. So now we have:

Code: Select all

0x01 * 0x.80 = 0x00.80 (1 * 0.5 = 0.5)
0x02 * 0x.80 = 0x01.00 (2 * 0.5 = 1.0)
0x03 * 0x.80 = 0x01.80 (3 * 0.5 = 1.5)
0x04 * 0x.80 = 0x02.00 (4 * 0.5 = 2.0)
0xFF * 0x.80 = 0x7F.80 (255 * 0.5 = 127.5)
0.8 is to hex what 0.5 is to decimal (8 being half way to 16).

So by multiplying numbers by 128, and keeping track of where the decimal point is, we've been able to divide by two.

This is known as "fixed point" maths, as we're using values with decimal points in a fixed position. In the example above, I'd put the decimal point 8 bits to the left.

With "floating point" maths, the computer tracks where the decimal point is for each number, so that you don't have to try and figure out where to place it for your maths. It "floats" around, giving the numbers a lot more dynamic range, and making calculations easier.

But it's not always necessary, you can do a lot without the computer explicitly tracking it for you, when you want/need to.
The multiplier:
Here, I've attached a demo, including the "very fast multiplier" for those that might want to borrow it :)

You can enter a "number to count to" (Limit) for as many signals as you like in one combinator. In the other combinator, enter how many seconds each count should take (Period). There's many ways this could be done, but here, we're going to use a fractional multiply.

So what we're going to do is have each signal count from 0x00000000 to 0xFFFFFFFF, or [0..1), and call it "Position". Each tick, we're going to add (2^32 / (PERIOD * 60)) to the Position, the 60 being due how many ticks are in a second.

With that done, Output = (Position * Limit) / 2^32, or MULHU.

NB: I'm using MULHU/MULHS now, it's more common parlance and I like to add to confusion.

Anyway, enjoy - maybe you can find some use for it :)

Fractional multiply demo
A very fast multiplier
Top
mmmPI
Smart Inserter
Smart Inserter
Posts: 2747
Joined: Mon Jun 20, 2016 6:10 pm
Contact:
Contact mmmPI

Re: Pairwise Arithmetic / each op each

Post by mmmPI »

almania wrote: ↑
Sun Mar 10, 2024 4:07 am
 As you're getting the hang of hex, you may surprise yourself. You may need windows calculator in programming -> Hex mode though.
I guess i would need to make my own tool for it to stick in my head, thank you for you time explaining, i was under the misrepresentation that floating point = non integers in binary, but it's not the case, fixed point binary or fixed point hex are also a thing. For now that doesn't seem too complicated, at least much less than what i stumbled upon before. Though i suppose it gets more complicated when you don't divide by 2 or multiply by 0.5 but try to divide by 7 or 13 instead.

Thanks for sharing the blueprints too, i will use them the first at least to try and understand what's going on in the fractionnal multiply, but no guarantee. I'll fall back on trying to understand the other one in case.

You say you like to add confusion, which i don't think is necessary given my current actual level of confusion. But on the other hand you explain quite a bit which is not confusing in itself on the contrary. So why say you like to add confusion ? that's confusing even more :)
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 »

almania wrote: ↑
Sun Mar 10, 2024 4:07 am
Thanks for the blueprints, I incorporated them where I could. div and especially mod got a bit smaller and faster as result.
The right shifts using your multipliers are currently the same speed as the ones I had previously, but using more combinators. Maybe there are ways to make them smaller, but I don't currently see places where I can cut combinators using the knowledge that one operand only has a single bit set.
Arithmetic right shift is at 7 ticks, 76 combinators .
Logic right shift uses 7 ticks, 83 combinators .
Top
Post Reply

Return to “Combinator Creations”