[HN Gopher] Why is division so much more complex than other arit...
___________________________________________________________________
Why is division so much more complex than other arithmetic
operations?
Author : rongenre
Score : 81 points
Date : 2023-08-11 18:22 UTC (4 hours ago)
(HTM) web link (scicomp.stackexchange.com)
(TXT) w3m dump (scicomp.stackexchange.com)
| Dylan16807 wrote:
| 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 wrote:
| Can 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
| IshKebab wrote:
| He 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
|
| It compiles x/6 to some mad multiplication, bitshift and add.
| ridiculous_fish wrote:
| For 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-
| epis...
| kstrauser wrote:
| Exactly. 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 wrote:
| Yes 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 wrote:
| How do you calculate 1/x without using division?
| codefreakxff wrote:
| Not 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.
| fuzzylightbulb wrote:
| so basically just precompute all the answers you will
| need and then just look up the values later?
| circuit10 wrote:
| There's no lookup needed if the value is constant
| shmerl wrote:
| I 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?
| a_e_k wrote:
| Often, 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.)
| pdonis wrote:
| If 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 wrote:
| Ah, thanks for clarifying.
| [deleted]
| [deleted]
| aidenn0 wrote:
| For integer division, you may find that rounding is not
| identical after multiplying by the reciprocal.
| Findecanor wrote:
| 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?).
|
| 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 wrote:
| > 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.
| nly wrote:
| I.e.
|
| https://libdivide.com/
| thcopeland wrote:
| Dr. Douglas Jones wrote a pretty great article on the subject,
| 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]
| eigenket wrote:
| Its 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 x 3^0 x 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 wrote:
| Nitpick, 50 is 2^1 x 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 wrote:
| Thanks :) I edited my comment so the arithmetic is
| (hopefully) right now
| eigenket wrote:
| By 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 x 3^b x 5^c x 7^d etc), which
| turns out to be mathematically a convenient thing to have.
| voldacar wrote:
| Before mechanical calculators, large tables of logarithms
| were computed by hand and used for exactly this purpose.
| xpe wrote:
| I was going to add a less eloquent comment along these lines,
| but you got here first!
| the-printer wrote:
| Please share it if you can recall. As someone who just
| figured out what Base-2 and Base-10 meant, I'm eager for
| all sorts of Mathematica.
| foota wrote:
| Makes me wonder... Is it known whether there is some
| intermediate representation that makes both fast?
| psychphysic wrote:
| Yeah you store the log of every number.
| foota wrote:
| Could you explain a little more of post a reference?
| psychphysic wrote:
| If A x B = C
|
| then log A + log B = log C
|
| And if D^E = F
|
| then E x log D = log F
|
| Mostly a tongue in cheek comment but if you don't know
| log rules at all check out log tables [0]. And you'll see
| that if you use log values then multiplication and
| division become addition and subtraction and equally
| simply.
|
| Relies on you either having stored the needed data or
| efficiently calculating logirithms and antilogirithims.
|
| https://www.cuemath.com/algebra/log-table/
| foota wrote:
| Ah, I get it now. All we need is a logarithm oracle and
| we're good to go :)
| ithkuil wrote:
| Indeed, with lookup tables, if you've seen one, you've
| seen them all
| eigenket wrote:
| I don't think that anything exists which is going to be
| better than the normal representations we use in anything
| except fantastically niche situations.
| [deleted]
| xpe wrote:
| Stated very broadly, I think of the mathematical "design
| space" as the set {operations, representations}.
|
| Classic examples include:
|
| - time domain / frequency domain
|
| - lookup table / functional form
|
| - traditional binary representation / gray codes
| AnotherGoodName wrote:
| To 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 wrote:
| To 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.
| JonChesterfield wrote:
| It's a slight tangent, but in the general realm of division being
| complicated, divide by zero is a longstanding annoyance. Does
| anyone know (or can refer to) a reasonable definition of
| +,-,*,/,% (in their usual meanings) on rational numbers such that
| A op B always evaluates to a rational?
|
| A/1 divide 0/1 being stored as 1/0 and then propagated around
| seems reasonable but I keep putting off the bookwork of finding
| out what arithmetic relations still hold at that point. I think
| one loses multiply by zero folding to zero, for example A * 0 is
| now only 0 for A known to have non-zero denominator.
|
| Context is a language with arbitrary precision rationals as the
| number type, and all I'm really looking for is a way to declare
| that the type of division is a rational for any rational
| arguments. Searching for this mostly turns up results on the
| naturals or integers which I'm not particularly interested in.
|
| Long shot but worth asking. Thanks
| Bostonian wrote:
| I assume for most programming languages there is no speed
| difference in writing y = x/5.0
|
| vs. y = 0.2 * x
|
| Is that true?
| eesmith wrote:
| I enjoyed the economics answer and comment by Mark Booth:
|
| > 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. ..
|
| > CPU manufacturers would only dedicate a large swath of silicon
| to a low latency floating point divide unit if they couldn't use
| that silicon more effectively to speed up the CPU in other ways.
| Generally speaking though, having more long latency FDIVs are a
| more efficient use of silicon than fewer shorter latency FDIVs
| not2b wrote:
| But you'd have to cram so many levels logic into that single
| cycle that you'd have to decrease the clock frequency to meet
| timing constraints, meaning that code that is not dominated by
| division would slow down. And a multi-cycle division can often
| happen in parallel with other operations.
| all2 wrote:
| Division is a variation of the packing problem which (without
| constraint) is NP Hard.
| slowmovintarget wrote:
| Entropy.
|
| Kind of like recovering the creamer from your coffee, only with
| symbols.
| lotaezenwa wrote:
| It's not closed on the reals
| not2b wrote:
| Computers can't represent reals, and it's closed on IEEE
| floating point values (with Inf and NaN).
| anthk wrote:
| Division it's just the inverse of multiplication, which is
| another multiplication.
| ajross wrote:
| It's actually not more "complicated" in the sense of operation
| count. You divide in the standard algorithm by: shifting your
| divisor so it's within one bit of the dividend (or one "place" if
| you're doing non-binary math), subtracting (or doing a one-digit
| divide for human numbers), and then shifting the result left by
| one place and repeating until you're out of divisor.
|
| Multiplication is completely symmetric: shift off the _lowest_
| bit (digit), multiply (which is just logical AND for binary), add
| to the result, shift the result right, and repeat.
|
| The reason multiplication is _faster_ than division isn 't about
| complexity it's about dependency. The division steps depend on
| the previous iteration, where multiplication can be parallelized.
| pfdietz wrote:
| Division has the same big-O complexity as multiplication.
|
| https://en.wikipedia.org/wiki/Computational_complexity_of_ma...
| marktangotango wrote:
| Adding on to this, and related somewhat, binary addition even
| with look ahead is a multi clock cycle process for non trivial
| word sizes. Arithmetic is not trivial by any means. We all just
| take it for granted.
| taeric wrote:
| By "non-trivial word sizes," I presume you mean larger than a
| single word of most computers? My understanding is that
| modern BDD/ZDD techniques have gone a long way to showing how
| to do the entire operation in a single pass for most sized
| numbers. Such that propagating the carry information isn't
| really how it is done, anymore. (This is a genuine question,
| btw. I have been a long way from my VLSI classes back in
| college.)
| throwaway14356 wrote:
| my ignorant imagination says to look for the sweetspot
| between a lookup table and chunks as large as possible.
| pfdietz wrote:
| Addition can be performed with circuits of depth O(log n),
| where n is the number of bits, and with a little more work
| also of size O(n).
| ithkuil wrote:
| I'm confused. Since O(log n) is faster than O(n) why would
| O(n) require a little more work? Did I misread something or
| did you miswrite?
| pfdietz wrote:
| I'm talking about constructing boolean circuits. The
| usual parallel prefix algorithm yields a circuit of depth
| O(log n) with O(n log n) gates. Using a two level trick,
| however, this can be reduced to O(n) gates, with a
| constant factor increase in depth.
| goalieca wrote:
| Not for cryptographically useful group like elliptic curves.
| Multiplication is defined as additions and can be made fast by
| repeatedly doubling and add. The inverse function, division, is
| incomputable for large curves.
| pfdietz wrote:
| Sorry, I should have specified this was about integer
| multiplication.
| constantcrying wrote:
| Which doesn't imply anything about how fast the operations can
| be implemented for fixed size numbers.
|
| Also, did you even read the article you linked? The lowest
| complexity for Multiplication _is an open question_ , absurd to
| say that it "has the same big-O complexity".
| pfdietz wrote:
| You last point there is nonsense. We can reduce division to
| multiplication, so we can say division is O(M(n)), where M(n)
| is the complexity of multiplication, even if we don't know
| what M(n) is. Note that big-O is an upper asymptotic bound,
| not an exact asymptotic bound (that's big-Theta).
|
| In fact, one can also show that M(n) is O(D(n)) (where D(n)
| is the time needed to divide n bit numbers). So they really
| are big-theta of each other.
|
| (See Aho, Hopcroft, and Ullman, The Design and Analysis of
| Computer Algorithms, 1976, section 8.2)
| phkahler wrote:
| >> We can reduce division to multiplication
|
| How? I mean sure, if taking the reciprocal is O(1) which it
| certainly is not.
| pfdietz wrote:
| See the book referenced. Basically, if you implement
| division by Newton-Raphson, using multiplication as a
| subroutine, the complexity is O(M(n)).
|
| In the other direction, one can use division to do
| multiplication by: (1) doing reciprocal with division,
| (2) doing squaring with reciprocal, and (3) doing
| multiplication with squaring. All these operations
| (division, multiplication, reciprocal, and squaring) turn
| out to be equivalent in complexity up to a constant
| factor. All this is asymptotically in n, the number of
| bits.
| broupannoiffuto wrote:
| And we can reduce multiplication to additions, so
| something does not add up.
| pfdietz wrote:
| Not to a constant number of additions (or, more
| precisely, to a set of additions whose sizes sum to
| O(n)), no that is not known how to do that.
| LegionMammal978 wrote:
| As explained in the Wikipedia article, we use the Newton-
| Raphson method method with O(log _n_ ) steps to find the
| reciprocal of the divisor, then we multiply this
| reciprocal by the dividend. Each step of the reciprocal
| method reqires a single multiplication, with the
| precision doubling at each step. So the steps take M(1),
| M(2), M(4), ..., M( _n_ /2), M( _n_ ) time. Since
| multiplication isn't sublinear, M( _cn_ ) >= _c_ *M( _n_
| ) for _c_ >= 1 and "most" _n_ (very roughly); thus, M(
| _n_ ) + M( _n_ /2) + M( _n_ /4) + ... <= M( _n_ ) +
| 1/2*M( _n_ ) + 1/4*M( _n_ ) + ... <= 2*M( _n_ ). Adding
| the final multiplication, we get an upper bound of 3*M(
| _n_ ), or O(M( _n_ )).
| [deleted]
| constantcrying wrote:
| > We can reduce division to multiplication
|
| And I guess we can reduce divison to multiplication too.
| bryanrasmussen wrote:
| I guess this is some sort of remainder joke? But I don't
| get it.
| throwaway14356 wrote:
| and to subtraction or multiplication and further to
| counting
| pfdietz wrote:
| You don't understand what "reduce to" means in this
| context. In the intended meaning (where, X reduces to Y
| means that if we can do Y in O(T(n)) time, we can do X in
| O(T(n)) time) those aren't known. We can't reduce
| division to a constant number of additions of the same
| size.
| 2OEH8eoCRo0 wrote:
| It should- division is just reverse multiplication.
| broupannoiffuto wrote:
| But "reverse" is a division, and anyway, one operation and
| its "reverse" are not necessarily of symetric complexities.
|
| It is very easy to multiply an integer by itself, not so much
| to compute the square root of an integer.
|
| It is very easy to multiply 3x3x5, no so much to find the
| prime factors of 45.
| xvedejas wrote:
| Some operations have much more complex inverses, in a
| computational sense, so I don't think it's so simple. The key
| to showing this is to reduce the problem to its inverse:
| https://en.wikipedia.org/wiki/Reduction_(complexity)
| Wowfunhappy wrote:
| I find it interesting that the arithmetic operations which are
| more difficult for school children are also more difficult for
| computers (addition/subtraction < multiplication < division).
| finite_depth wrote:
| Multiplication/division include addition as a special case, at
| least if you allow adding 1:
|
| a+b = a + a(b/a) = a(1 + (b/a))
| ashton314 wrote:
| Unless you're talking about floating point in which case it's
| multiplication < addition < division. But your point stands.
| crimsonpowder wrote:
| Probably because add, sub, and mul are int -> int and div is int
| -> real. The fundamental operation maps from 0 to 1, which the
| other operations don't do. Intuitively, the complexity comes from
| this fact.
| Sniffnoy wrote:
| 1. We're discusing here floored integer division, which outputs
| an integer, not something more general like a real.
|
| 2. Even if we were discussing exact division, the ratio of two
| integers is a rational. The rationals are countable. More
| generally, any image of a countable set is countable, and the
| cartesian product of two countable sets is countable; there is
| no way you could get something uncountable from something like
| this.
|
| 3. Aleph_1 is not (necessarily) the same thing as the
| cardinality of the reals, which is 2^(aleph_0). The statement
| that these are the same is known as the continuum hypothesis
| and is undecideable in standard mathematics.
|
| ...and, also, none of this really relates to the complexity of
| performing integer division, even ignoring the fact that these
| statements are false.
___________________________________________________________________
(page generated 2023-08-11 23:01 UTC)