https://scicomp.stackexchange.com/questions/187/why-is-division-so-much-more-complex-than-other-arithmetic-operations Stack Exchange Network Stack Exchange network consists of 183 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers. Visit Stack Exchange [ ] Loading... 1. + Tour Start here for a quick overview of the site + Help Center Detailed answers to any questions you might have + Meta Discuss the workings and policies of this site + About Us Learn more about Stack Overflow the company, and our products. 2. 3. current community + Computational Science help chat + Computational Science Meta your communities Sign up or log in to customize your list. more stack exchange communities company blog 4. 5. Log in 6. Sign up Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It only takes a minute to sign up. Sign up to join this community [ano] Anybody can ask a question [ano] Anybody can answer [an] The best answers are voted up and rise to the top Computational Science 1. Home 2. 1. Public 2. Questions 3. Tags 4. Users 5. Companies 6. Unanswered 3. Teams Stack Overflow for Teams - Start collaborating and sharing organizational knowledge. [teams-illo-free-si] Create a free Team Why Teams? 4. Teams 5. Create free Team Teams Q&A for work Connect and share knowledge within a single location that is structured and easy to search. Learn more about Teams Why is division so much more complex than other arithmetic operations? Ask Question Asked 11 years, 8 months ago Modified 3 years, 1 month ago Viewed 21k times 53 $\begingroup$ I recently encountered a case where I needed an integer division operation on a chip that lacked one (ARM Cortex-A8). While trying to research why that must be, I found out that in general division takes many more cycles than addition, subtraction or multiplication on pretty much any integer (or fixed-point) architecture. Why is this the case? Is it not representable with a two-layer AND-OR logic like everything else? * computer-arithmetic Share Cite Improve this question Follow edited May 4, 2012 at 19:38 Phonon asked Dec 2, 2011 at 19:59 Phonon's user avatar PhononPhonon 63311 gold badge55 silver badges88 bronze badges $\endgroup$ 1 * 4 $\begingroup$ Division is fundamentally harder wrt boolean circuit depth: dl.acm.org/doi/pdf/10.1145/800057.808714 $\ endgroup$ - user14717 Apr 30, 2020 at 10:43 Add a comment | 2 Answers 2 Sorted by: Reset to default [Highest score (default) ] 38 $\begingroup$ Division is an iterative algorithm where the result from the quotient must be shifted to the remainder using a Euclidean measure, see 2; whereas, multiplication can be reduced to a (fixed) series of bit manipulation tricks. Share Cite Improve this answer Follow edited Dec 3, 2011 at 21:52 answered Dec 2, 2011 at 20:13 aterrel's user avatar aterrelaterrel 3,5842222 silver badges2626 bronze badges $\endgroup$ 11 * 4 $\begingroup$ It used to be that both multiplication and division were slow operations. Nowadays multiplication is a bit faster (but slightly slower than addition/subtraction), but division still is slower than the others. I believe Newton-Raphson is still used internally by most for reciprocating a number. $\ endgroup$ - J. M. Dec 3, 2011 at 0:36 * 19 $\begingroup$ (Off-topic: "Inverse operations are usually hard. Just look at integration versus differentiation." - depends on whether what you're doing is symbolic or numeric. Differentiation is symbolically easy, but numerically hard; integration is symbolically hard, but numerically easy.) $\endgroup$ - J. M. Dec 3, 2011 at 0:37 * 1 $\begingroup$ Okay, I'll cop out by saying that cubature is a different can of worms; but at least in the one-dimensional case, quadrature is easier than differentiation. $\endgroup$ - J. M. Dec 3, 2011 at 2:32 * 2 $\begingroup$ In any case, inverses always come in pairs. Why would you call one the "operation" and the other the "inverse"? $ \endgroup$ - David Ketcheson Dec 3, 2011 at 4:33 * 3 $\begingroup$ Neither iteration nor inverse makes it harder. Hardness of division comes from the fact that you have to shift the result from quotient to remainder using a Euclidean measure. See the division algorithm theorem. $\endgroup$ - user182 Dec 3, 2011 at 21:42 | Show 6 more comments 28 $\begingroup$ While all current CPU's appear to use an iterative approach as aterrel suggests, there has been some work done on non-iterative approaches. Variable Precision Floating Point Division and Square Root talks about a non-iterative implementation of floating point division and square root in an FPGA, using lookup tables and taylor series expansion. I suspect that the same techniques may make it possible to get these operations down to a single cycle (throughput, if not latency), but you are likely to need huge lookup tables, and thus infeasibly large areas of silicon real-estate to do it. Why would it not be feasible? In designing CPU's there are many trade-offs to make. Functionality, complexity (number of transistors), speed and power consumption are all interrelated and the decisions made during design can make a huge impact on performance. A modern processor probably could have a main floating point unit which dedicates enough transistors on the silicon to perform a floating point division in a single cycle, but it would be unlikely to be an efficient use of those transistors. The floating point multiply made this transition from iterative to non-iterative a decade ago. These days, single cycle multiply and even multiply-accumulate are commonplace, even in mobile processors. Before it became an efficient use of transistor budget, multiply, like division, was often performed by an iterative method. Back then, dedicated DSP processors might dedicate most of their silicon to a single fast multiply accumulate (MAC) unit. A Core2duo CPU has a floating point multiply latency of 3 (the value comes out of the pipeline 3 cycle after it went in), but can have 3 multiplies in flight at once, resulting in a single-cycle throughput, meanwhile it's SSE2 unit can pump out multiple FP multiplies in a single cycle. Instead of dedicating huge areas of silicon to a single-cycle divide unit, modern CPU's have multiple units, each of which can perform operations in parallel, but are optimised for their own specific situations. In fact, once you take into account SIMD instructions such as SSE or the CPU integrated graphics of the Sandy Bridge or later CPU's, there may be many such floating-point divide units on your CPU. If generic floating point division were more important to modern CPU's then it might make sense to dedicate enough silicon area to make it single cycle, however most chip makers have obviously decided that they can make better use of that silicon by using those gates for other things. Thus one operation is slower, but overall (for typical usage scenarios) the CPU is faster and/or consumes less power. Share Cite Improve this answer Follow edited Jun 25, 2020 at 18:05 Community's user avatar CommunityBot 1 answered Dec 5, 2011 at 13:21 Mark Booth's user avatar Mark BoothMark Booth 2,3961818 silver badges3131 bronze badges $\endgroup$ 6 * $\begingroup$ To my knowledge, no chips have single-cycle divide latencies for floating point. For example, Agner Fog's instruction tables for Intel, AMD, and VIA CPUs lists DIVPS (SSE packed floating-point divide) as 10-14 cycles. I can't find any hardware with single-cycle divide instructions, but I'd be willing to be proved wrong. It's not common as far as I can tell. $\endgroup$ - Bill Barth Dec 6, 2011 at 15:06 * 1 $\begingroup$ @Bill - Thanks, you're right. I'm sure I've seen single-cycle division operations in DSP chips before, so assumed it would have made it's way to the desktop, just as single-cycle multiply did, but I can't find any references now. I've updated my answer and added some relevant information on non iterative methods which might allow it in the future though. It's amazing to think that division is no more efficient per cycle now than back when I was using transputers. $\endgroup$ - Mark Booth Dec 6, 2011 at 19:48 * 3 $\begingroup$ I think DSPs do that by limiting the range in which they are accurate. This is the same strategy used for lookup+interpolation for square root. $\endgroup$ - Matt Knepley Dec 7, 2011 at 11:27 * 1 $\begingroup$ I am not sure what the latency of such a division would be, though. At 4 GHz, making a round-trip to the look-up table within N cycles severely limits the potential size of said table (for example, the L1 caches have been stagnating at 32K each). Going 3D would help increasing this (but is challenging wrt. cooling). Do you have any idea what latency could be reached for modern 4GHz/5GHz CPUs? $\endgroup$ - Matthieu M. Jan 11, 2017 at 13:59 * 1 $\begingroup$ For divps / divpd vs. mulps / mulpd latency and throughput numbers, see Floating point division vs floating point multiplication. I took data from Agner Fog's instruction tables and formatted it into a summary across uarches of div and mul throughput and latency, for single vs. double and for different SIMD vector widths. (Intel chips typically have a SIMD divider that's only half the width of the other vector ALUs.) $\endgroup$ - Peter Cordes Nov 27, 2018 at 23:32 | Show 1 more comment Your Answer [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] Thanks for contributing an answer to Computational Science Stack Exchange! * Please be sure to answer the question. Provide details and share your research! But avoid ... * Asking for help, clarification, or responding to other answers. * Making statements based on opinion; back them up with references or personal experience. Use MathJax to format equations. MathJax reference. To learn more, see our tips on writing great answers. Draft saved Draft discarded [ ] Sign up or log in Sign up using Google Sign up using Facebook Sign up using Email and Password Submit Post as a guest Name [ ] Email Required, but never shown [ ] Post as a guest Name [ ] Email Required, but never shown [ ] Post Your Answer Discard By clicking "Post Your Answer", you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct. Not the answer you're looking for? Browse other questions tagged * computer-arithmetic or ask your own question. * Featured on Meta * Our Design Vision for Stack Overflow and the Stack Exchange network * Moderation strike: Results of negotiations Related 13 In floating point arithmetic, why does numerical imprecision result from adding a small term to a difference of large terms? Hot Network Questions * What aspect ratios are used in Oppenheimer? * Why is research grade ethanol seemingly exempted from excise duties while pure ethanol ment for consumption isn't? * "There, but for the grace of God, go I" - Breaking this down grammatically * Why do we stick to single valued functions? * Is China actively trying to undermine Israel? * Did the IBM ServiceFree really reach 80 MIPS in 1975? * Do on-wall air conditioners, mini splits, need expert installation or water replacements? * Parallel Accumulate * Does the editorial board of a journal have the ethical right to refuse publication for insulting the reviewer? * What is the meaning of "saved" in Acts 15:1? * Bash reads quotes inside a varible as text, not quotes? Is "Implicit quoting" a thing in Bash? * How much of the axiom of choice do you need in mathematics? * Gimp: how do you save a modified png image? * Relay "latches" (doesn't turn off) after being turned ON for a very long time * Deleting outliers prior to data splitting or only in the training set? * Evenly spread values * How can I blend these two meshes perfectly together without wrinkles? * date - Can't Go Back More Than 115 Years or Can't Go 5879565 Years Into the Future * If we have full copies of the Torah in an unchanged form (Dead Sea Scrolls,) why don't we revert out Torah scrolls back? * Fitting a power law on linear and log scale * USB peripheral: connecting USB shield to GND? * Science fiction short story about a man who was a god of rain * Is there something "morally weird" about social media sites with downvote functions? * Insulating an open window with air conditioning pipe through it more hot questions Question feed Subscribe to RSS Question feed To subscribe to this RSS feed, copy and paste this URL into your RSS reader. [https://scicomp.stac] * Computational Science * Tour * Help * Chat * Contact * Feedback Company * Stack Overflow * Teams * Advertising * Collectives * Talent * About * Press * Legal * Privacy Policy * Terms of Service * Cookie Settings * Cookie Policy Stack Exchange Network * Technology * Culture & recreation * Life & arts * Science * Professional * Business * API * Data * Blog * Facebook * Twitter * LinkedIn * Instagram Site design / logo (c) 2023 Stack Exchange Inc; user contributions licensed under CC BY-SA. rev 2023.8.10.43574 Your privacy By clicking "Accept all cookies", you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy. Accept all cookies Necessary cookies only Customize settings