8 ms·
Ideal divisors: when a division compiles down to just a multiplication
- whalesalad 6y agoI have been seeing this Wordpress theme a lot lately and it is so bad the way the content is pushed so far to the right. On my 27" monitor the left margin of the text is essentially the center of the display.
- jlarocco 6y agoI have a 27" monitor also, and it looks fine to me.
- tachyonbeam 6y ago27" monitor on Chrome here. Looks pretty far to the right.
- tzs 6y agoHow about if the browser window is maximized? What I get in that case is 23 cm for the darkish blue left sidebar and 36 cm for the light blue right area that contains the article. Within that right area, the article is in 19 cm white rectangle with just under 2 cm margins. So, starting from the left here is what I see: 15 cm empty dark blue background, 6 cm of sidebar text on dark blue background, 2 more cm of empty dark blue background, 2 cm of empty light blue background, A tad under 2 cm of empty white background, About 14.5 cm of text on white background, A tad under 2 cm of empty white background, 15.5 cm of empty light blue background. It really is quite ugly. It looks like something I would do because I completely suck at CSS.
- dhosek 6y agoI almost never¹ run a browser maximized on anything bigger than my 16" laptop screen (and even that not so much). Most of the time, I have browser windows that are 1/2 (on my 24" monitor) or 1/3 (on my ultrawide monitor) of the width and the full height (2/3 width on my laptop)). 1 The exception being browser windows to run sites like Netflix where I'm really using it as a video interface.
- tyingq 6y agoOne thing that often works in this situation with chrome is the "Emulate CSS Media Type: Print" option from the rendering tab in Dev Tools. The theme appears to be the wordpress default theme from 2015, so you should see less of it as times goes on.
- omgJustTest 6y agoFloating point, while convenient does have substantial drawbacks in the implementations of circuits that we have today. Efficiency gains like this somewhat expose facets that are normally hidden. It will be interesting to see the transition to either analog NN or quantum computers, which inherently have better representations of continuous values. Edit: Additionally the serial vs parallel processing paradigm shift is a main advantage of the switch too! Queued systems seem to have severe scheduling limitations, which the real-world does not always inherently have.
- svat 6y agoThe linked article is about integer division and has nothing to do with floating point, and in fact I can't see how this idea could be applied to floating-point arithmetic. Can it?
- wizzwizz4 6y agoNot directly, no. The underlying mathematics kind of can, but you'd need dedicated circuitry (or bit-hacking) for it because of the floating point parts, and it would fall over around subnormals.
- dahart 6y agoI’m not certain, but while reading I was feeling like there potentially is a relationship. It was reminding me of the algorithm where you can approximate a reciprocal square root using a single subtraction from a magic number constant. https://en.wikipedia.org/wiki/Fast_inverse_square_root https://en.wikipedia.org/wiki/Fast_inverse_square_root
- svat 6y agoIf you've never seen it before, this is a beautiful blog post on related matters: "Optimising pointer subtraction with 2-adic integers" http://blog.sigfpe.com/2010/05/optimising-pointer-subtraction-with-2.html http://blog.sigfpe.com/2010/05/optimising-pointer-subtractio...
- kevinventullo 6y agoA few months back I wrote a blog post very much inspired by Dan’s post, though a little more academic: https://kevinventullo.com/2020/12/21/2-adic-logarithms-and-fast-exponentiation/ https://kevinventullo.com/2020/12/21/2-adic-logarithms-and-f... The idea is to exploit deeper structures in p-adic number theory to develop useful and novel algorithms with unsigned integer arithmetic, e.g. fast integer exponentiation. Feedback welcome! (Warning: math heavy)
- svat 6y agoThis was a nice post, thank you! I don't yet have an intuition for how to think about these 2-adic exponentials and logs (e.g. what does it mean to say that log_2(5) =6713115954038056572) but clearly the mathematics works out and even leads to faster code, so it's very cool and I hope to read it again and understand it better. (As a sidenote on the motivation, I do wonder how common/useful it is to compute x^y mod (2^64) for random 64-bit integers x and y (so they'd be close to 2^63 on average)... from this perspective, the promised future post about computing the k-th root of a perfect k-th power integer sounds very interesting!)
- kevinventullo 6y agoThanks, that serves as good motivation to complete that post! As far as the statement that log_2(5) = 6713115954038056572, really that number is only an approximation; it is the last 64 bits of the “true” log_2(5), which has infinitely many bits. That is, the above equation in binary would be log_2(5) = 101110100101001110001110110010010000000011100100010011001111100. In the true 2-adic world, log_2(5) = ...101110100101001110001110110010010000000011100100010011001111100, where there are infinitely many leading bits. (Classical positive integers embed into the 2-adic world as numbers with all but finitely many bits set to 0, and similarly classical negative integers have all but finitely many bits set to 1.)
- chrchang523 6y agoSee also https://libdivide.com/ https://libdivide.com/ , when you need to repeatedly divide by a constant that isn't known until runtime.
- oh_sigh 6y agoHonestly if you're not familiar with the nitty gritty details of division, this sounds similar to those nodejs packages for "left padding a string"
- jvickers 6y agoIn JavaScript (specifically node / V8) if dividing multiple values by the same divisor, is it fastest to calculate the reciprocal and then multiply it? How about other languages (and compiler systems)? Are there binary tricks worth knowing about to quickly calculate reciprocals?
- brrrrrm 6y agoIt's typically faster to calculate a reciprocal (especially at compile time) and then multiply it, but this is often at the expense of precision. In C++, for example, the -O3 flag on gcc will still emit a division (divss) to preserve compliant floating point precision in this example: https://godbolt.org/z/PY3Wjno4P https://godbolt.org/z/PY3Wjno4P However, when we enable `-ffast-math`, we permit the compiler to do a bit more aggressive optimization in this domain (trading off precision), and we see multiplication (mulss) is emitted: https://godbolt.org/z/KEb1nc43z https://godbolt.org/z/KEb1nc43z
- dahart 6y ago> Are there binary tricks worth knowing about to quickly calculate reciprocals? Yes! You can calculate an approximate reciprocal with a single subtraction and some type-casting or bit manipulation. The accuracy isn’t great (relative error of up to ~5%), but it might be good enough for many applications. The method is famous for being used to normalize 3d vectors in Quake https://en.wikipedia.org/wiki/Fast_inverse_square_root https://en.wikipedia.org/wiki/Fast_inverse_square_root This same method for calculating 1/x^2 can also be used to calculate 1/x by using a different magic constant and skipping the shift-right by one bit.
- layoutIfNeeded 6y ago>I call the corresponding divisors ideal Not a particularly good name, as “ideal” already has an established meaning in algebra: https://en.m.wikipedia.org/wiki/Ideal_(ring_theory) https://en.m.wikipedia.org/wiki/Ideal_(ring_theory)
- gowld 6y agoIt's not an ideal name, even though it's ideal.
- withinboredom 6y agoThis is computer science, not algebra.
- Tainnor 6y agoalgebra plays a huge role in CS, e.g. cryptography
- dahart 6y agoDidn’t “ideal” have an established meaning in English before ring theory existed? Curious, why’d you pick that specialization of this word, out of all that are available? https://en.wikipedia.org/wiki/Ideal https://en.wikipedia.org/wiki/Ideal
- layoutIfNeeded 6y agoWhen shown on a 7-segment display, the only numbers whose images don't contain a little square are 1, 2, 3, 4, 5, and 7. I call them "square-free numbers". Oh, you're saying "square-free" has an established meaning in mathematics? https://en.wikipedia.org/wiki/Square-free_integer https://en.wikipedia.org/wiki/Square-free_integer Well, you see, "square" already had an established meaning in English before number theory existed. Curious, why’d you pick that specialization of this word, out of all that are available? :)
- dahart 6y ago
- tragomaskhalos 6y agoGenuine question: why would any compiler bother to optimise division with such obtuse dividends, other than a purists' satisfaction ?
- warkdarrior 6y agoDivision is orders of magnitude slower than multiplication.
- Tuna-Fish 6y agoLess than one order of magnitude these days. On Tiger Lake, integer multiply is 3 cycles, while integer division is 12 for 32-bit integers and 15 for 64-bit. Of course, the multiply is fully pipelined while the division is only partially, but even that leaves only a 10-fold difference. Division is much faster these days than it used to be. It's still worth it to have compiler optimizations for it, but it's not important to avoid it anymore.
- gowld 6y agoWhy do some people assume decimal ten as the base of the orders of magnitude when discussing binary arithmetic?
- cma 6y agoTimespan/cycle count is almost always denoted in base 10 in conversation.
- mmoskal 6y agoCortex-M4 (think $2) has 1 cycle multiplication and 2-12 cycle division (with early termination). If you go down to Cortex-M0 (think $0.50) then you get software division which is indeed orders of magnitude slower. Of course lower down the line there isn't even hardware multiplication. Interestingly, the ARM11 in original RPi and RPi0 doesn't have hardware integer division (despite being 10x faster than typical M4 and typically having 10000x RAM), but it does have floating point division.
- andrewfromx 6y agoi'd like to find these numbers for base9 vs base10. see https://stackoverflow.com/questions/67226727/is-there-a-way-to-divide-two-base9-ints-in-golang https://stackoverflow.com/questions/67226727/is-there-a-way-... if you look at that sample golang code, is that the right way to go about this? Or is there a much simpler way already built into a high level language like go?
- deleted 6y ago[deleted]
- lamontcg 6y agoFor floating point math is this why I see "/2" written as "*0.5" all the time, and is that really necessary and can't compilers figure that out?
- kevin_thibedeau 6y agoThey don't necessarily produce the same result and strict IEEE conformance prohibits such transformations. With GCC, --ffast-math enables optimizations like this.
- lamontcg 6y agoThat makes sense. I typically have to worry about larger relative tolerances anyway so I think I can start using that trick.
- SuchAnonMuchWow 6y agoIn this specific example, they do produce exactly the same result: `a / b` is completely equivalent to `a * (1 / b)` when both b and 1/b are perfectly representable in floating point without rounding, which is the case for 2 and 0.5