5 ms·
It's worth noting that you can generally divide much faster if you know the divisor ahead of time, because you can turn it into a multiplication problem. But d
by Dylan16807 3y ago
It's worth noting that you can generally divide much faster if you know the divisor ahead of time, because you can turn it into a multiplication problem. But doing this takes some effort, as compared to turning subtraction into addition which is trivial.
- Iulioh 3y agoCan you explain what do you mean with: >It's worth noting that you can generally divide much faster if you know the divisor ahead of time Division is just multiplication with 1/x so i don't understand
- kstrauser 3y agoExactly. If you know you’re going to later be dividing by 23.7, you can precompute 1/23.7 and store that as a constant. Then you can later multiply by it.
- MaxMatti 3y agoYes but 1/x is just another division, so it only helps to speed up the final division of you're able to calculate 1/x beforehand.
- shmerl 3y agoHow do you calculate 1/x without using division?
- codefreakxff 3y agoNot being snarky, at the simplest level by knowing x ahead of time you can change your code from y = n/2 into y = n * 0.5. Not wildly important by itself, but in a loop - maybe… I suspect compilers optimize for that already.
- shmerl 3y agoI still don't get it. How do you know that 1/x = 0.abc... without performing the division? I mean in general case, not in something matching binary tricks. Such as 1/3 for example. Unless you mean you somehow know the value of 1/x ahead of time. But where does it come from?
- deleted 3y ago[deleted]
- pdonis 3y agoIf you know the divisor x ahead of time you can pre-compute 1/x at compile time, so that your actual compiled code never does the division--only your compiler does. Your actual compiled code just does the multiplication by a pre-computed constant (and the compiled code doesn't have to know that that constant was pre-computed as the reciprocal of x).
- shmerl 3y agoAh, thanks for clarifying.
- a_e_k 3y agoOften, you can amortize a division or reciprocal by calculating it once and then reusing it. Frequently the divisor is dynamic, but reused locally. For example, if you want to normalize a 3D vector you could do: mag = sqrt(x*x + y*y + z*z) x /= mag y /= mag z /= mag That's three divisions with the same divisor. But you could instead do: invMag = 1.0 / sqrt(x*x + y*y + z*z) x *= invMag y *= invMag z *= invMag There's still a single division (or reciprocal) done here. But you've eliminated at least the other two. (And it's even better if you have an rsqrt function.)
- fuzzylightbulb 3y agoso basically just precompute all the answers you will need and then just look up the values later?
- circuit10 3y agoThere’s no lookup needed if the value is constant
- deleted 3y ago[deleted]
- aidenn0 3y agoFor integer division, you may find that rounding is not identical after multiplying by the reciprocal.
- Findecanor 3y agoDoesn't the risk of lack of precision apply to both floating point and fixed-point? I'd think the reciprocal would need to be exactly represented in the type, or to have more bits than the original type to produce a correct result in the last bit (or two bits?). Also, with integers, a signed right shift is rounding down (towards negative infinity), whereas the division operator/instruction in many languages/hardware is rounding towards 0. To adjust the rounding, you'd add the sign-bit to the first fractional bit before shifting the last step. Let's say that 'x' is a signed long, and a signed long has 64 bits, then: result = ((x >> amount-1) + ((unsigned long)x >> 63)) >> 1;
- aidenn0 3y ago> Doesn't the risk of lack of precision apply to both floating point and fixed-point? I'd think the reciprocal would need to be exactly represented in the type, or to have more bits than the original type to produce a correct result in the last bit (or two bits?). Yes, but this was historically okay on an x87 FPU which had more precise representation than the common external formats.
- IshKebab 3y agoHe is talking about the fact that compilers can turn division by a constant into multiplications and bit shifts which are much faster. Here's an example: https://godbolt.org/z/8vG637fb5 https://godbolt.org/z/8vG637fb5 It compiles x/6 to some mad multiplication, bitshift and add.
- ridiculous_fish 3y agoFor flooring integer division with a bounded dividend and known constant, the idea is to multiply by a scaled reciprocal. For example with 32 bit division by 3, you might precompute 2^32 / 3, multiply by that, and then flooring-divide by 2*32 (right shift). It gets tricky because 2^32/3 is not an integer, so you must round it. This introduces error; the idea is to show that the error is wiped out by the flooring divide. I did the monster math here: https://ridiculousfish.com/blog/posts/labor-of-division-episode-i.html https://ridiculousfish.com/blog/posts/labor-of-division-epis...
- AnotherGoodName 3y agoTo dive into this a bit more without using too much math jargon, under modulo every integer division is a trivial integer multiplication but the number you multiply by has to figured out before hand. The above is also not true of factors of the modulo itself but then that's just a right shift so that part is easy. eg. Under mod 35 if i want to divide by 3 i can just multiply by 12 since 12x3 = 1 under mod 35. eg2. Under mod 35 if i want to divide by 11 i can just multiply by 16 since 16x11 = 1 under mod 35. I can do this for any number that doesn't share factors with 35 since there's always a multiple to that number that will give 1. I could also create base 2 examples similarly. It's called the multiplicative inverse.
- ridiculous_fish 3y agoTo clarify, there are two separate notions of division-as-multiplication discussed here. Modular division is straightforward to convert to a multiplication; however this is mainly for specialized applications, like cryptography and number theory. It's uncommon to want divide-by-2 to make the value larger. Ordinary flooring division can also be converted to a multiplication problem when the dividend is bounded. This uses the "magic number" approach where you multiply by a rounded scaled reciprocal, and then do some work to correct the error from rounding.
- thcopeland 3y agoDr. Douglas Jones wrote a pretty great article on the subject, https://homepage.cs.uiowa.edu/~jones/bcd/divide.html https://homepage.cs.uiowa.edu/~jones/bcd/divide.html. Depending on the divisor it can be a bit messy, since reciprocal multiplication sometimes needs extra precision. For example, on an 8-bit machine, x/6 == (x*42>>8), which is nice because 42 fits in 8 bits. But x/105 == (x*313>>15) needs 9 bits to hold 313. On some systems (thinking 8-bit AVR), it'd probably be faster to branch on the 3 cases rather than perform a full 16-bit multiplication.
- deleted 3y ago[deleted]
- eigenket 3y agoIts worth noting that this asymmetry between addition and multiplication happens because our usual representations of numbers (i.e. on a piece of paper or in a a computer) favour addition over multiplication. You can come up with different representations of rationals, for example you could store prime exponents as integers so the number 20 gets stored as (2,0,1,0...) because its 2^2 × 3^0 × 5^1, or 5/6 would be (-1, -1, 1,...). With a representation like this, or just by taking logs if you like, you can come up with a representation where multiplication and division are very cheap but addition and subtraction are more expensive.
- vikingerik 3y agoNitpick, 50 is 2^1 × 5^2, not the other way around. But anyway, thanks a ton for this post, I felt my brain shift at a new way of thinking about numbers, seriously. I have to wonder what serious and useful implementations of this method might have been done somewhere.
- eigenket 3y agoThanks :) I edited my comment so the arithmetic is (hopefully) right now
- eigenket 3y agoBy the way, if you're wondering if anyone has done anything useful with the method of describing numbers as prime exponents I mentioned the answer is yes, depending on your definition of "useful". The encoding in terms of prime exponents is known as the Godel encoding, and its a fairly important step in proving things like Godel's incompleteness theorems and the undecidability of the Halting problem. Essentially it's a one-to-one map between natural numbers and finite sequences of natural numbers (since you can encode (a,b,c,d...) as 2^a × 3^b × 5^c × 7^d etc), which turns out to be mathematically a convenient thing to have.
- xpe 3y agoI was going to add a less eloquent comment along these lines, but you got here first!
- nly 3y agoI.e. https://libdivide.com/ https://libdivide.com/