this post was submitted on 13 Sep 2024
83 points (100.0% liked)
chat
8197 readers
393 users here now
Chat is a text only community for casual conversation, please keep shitposting to the absolute minimum. This is intended to be a separate space from c/chapotraphouse or the daily megathread. Chat does this by being a long-form community where topics will remain from day to day unlike the megathread, and it is distinct from c/chapotraphouse in that we ask you to engage in this community in a genuine way. Please keep shitposting, bits, and irony to a minimum.
As with all communities posts need to abide by the code of conduct, additionally moderators will remove any posts or comments deemed to be inappropriate.
Thank you and happy chatting!
founded 3 years ago
MODERATORS
you are viewing a single comment's thread
view the rest of the comments
view the rest of the comments
it's when you ask "okay but how does division work on a fundamental level, it's definitely physically intuitive yeah but what's the maths behind it, like multiplying is adding a number to itself x amount of times, dividing is unmultiplying by a number, but it's not subtracting a number multiple times, at least not one that's always present in the equation, what's going on here, how did this happen" and it all goes downhill from there
I'm too stoned for this
isn't it, though? subtract 4 from 12 three times and you're left with the additive identity
exactly, it's anti-multiplication – you find how many times you need to subtract out a number from a product to get another number, but it’s hard to compute comparatively due to that abstraction. Reason I reference this is that for a fundamental operation of math, computers absolutely suck at it on a basic level compared to multiplication
i see. yes, that is weird. now that you've experienced gnosis, why do you think it's so much harder to compute?
because the fundamental definition of divisibility is whether or not the chosen divisor—
b—can be multiplied by any number within the set of numbers you are working with—c—to get the dividend—a.The output of division is
c. Therefore, the brute force way of dividing a number would be to iterate through the entire set of possible numbers and return the number that, when multiplied by what you are dividing, outputs the value you want to divide from—or, to have the multiplication table as a persistent hash map in memory, pre-computing all possible products.It’s not implemented like this because that would be horrifically slow/bloated. See Low Level Learning’s 5 minute video computers suck at division (a painful discovery) to see how it’s implemented in modern processors—it’s very, very unintuitive.
huh, yeah, i guess that's kinda how humans do long division?
he's hopping right past the most interesting part, though. sure, doing math with byte logic is tricky, so you have to make approximations. so in order to divide by 9 the processor does some fixed point math and says to divide by 9 we're actually going to multiply by 2^33 / 9 which equals that long number. but how does the processor know what 2^33/9 equals? how's it doing that? sounds like it's very good at division, because it would take me a while to work out that value even if i started with trying to find 8589934592/9, y'know?
more to the point, how does it do 0b1000000000000000000000000000000000 / 0b1001 = 0b111000111000111000111000111001 so quickly?
You should understand that "computers very bad at division" is a relative term, on modern desktop x86 chips a single 64-bit division takes somewhere on the order of 20-40 clock cycles (which seems pretty fast when you think about how they're running at like 4 billion cycles per second, but these same chips can do integer multiplication in 2-3 cycles so division is painfully slow by comparison).
The reason multiplying by 2^33 / 9 is faster is because you don't have to actually compute what 2^33 is and then divide by 9 every single time - the compiler can compute that value the "slow" way a single time and bake that into the machine code, and then when the program is running it only has to deal with multiplication.
While we don't know exactly what techniques are being used in a modern Intel/AMD chip, as far as I know the current best approach is basically just long division.
EDIT: The reason long division is slow is that all the partial results depend on the results of previous steps. This means that your division circuit ends up being a really long line of comparator circuits chained end-to-end, and long circuits are bad because it takes a long time for the signal to actually reach the end. Multiplication is fast by comparison because you can compute all the partial products in parallel, and then add them together in a kind of tree shape. The end result is a circuit which is super wide, but the "propagation delay" (the time it takes until the last input signal reaches the end) is pretty low since there's no path which passes through more than a few adders.
I found a YouTube link in your comment. Here are links to the same video on alternative frontends that protect your privacy: