3 ms·
Division has the same big-O complexity as multiplication. https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations https://en.wikipedi
by pfdietz 3y ago
Division has the same big-O complexity as multiplication.
https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations https://en.wikipedia.org/wiki/Computational_complexity_of_ma...
- marktangotango 3y agoAdding 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 3y agoBy "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 3y agomy ignorant imagination says to look for the sweetspot between a lookup table and chunks as large as possible.
- pfdietz 3y agoAddition 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 3y agoI'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 3y agoI'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 some trickery, however, this can be reduced to O(n) gates, with a constant factor increase in depth. https://en.wikipedia.org/wiki/Prefix_sum https://en.wikipedia.org/wiki/Prefix_sum https://en.wikipedia.org/wiki/Adder_(electronics) https://en.wikipedia.org/wiki/Adder_(electronics)
- constantcrying 3y agoWhich 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 3y agoYou 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)
- deleted 3y ago[deleted]
- constantcrying 3y ago> We can reduce division to multiplication And I guess we can reduce divison to multiplication too.
- bryanrasmussen 3y agoI guess this is some sort of remainder joke? But I don't get it.
- throwaway14356 3y agoand to subtraction or multiplication and further to counting
- pfdietz 3y agoYou 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 3y agoIt should- division is just reverse multiplication.
- xvedejas 3y agoSome 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) https://en.wikipedia.org/wiki/Reduction_(complexity)
- broupannoiffuto 3y agoBut "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.
- goalieca 3y agoNot 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 3y agoSorry, I should have specified this was about integer multiplication.