Apple’s M1 has a monstrously fast divide instruction.
There are some benchmarks here: https://ridiculousfish.com/blog/posts/benchmarking-libdivide...
I noticed it is very fast when I was experimenting with algorithms for unbiased bounded random numbers https://dotat.at/@/2022-04-20-really-divisionless.html - the fancy nearly and really divisionless algorithms had much less advantage on an Apple M1 than on an old Intel CPU.
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.
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
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.
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
Remember the Cray-1. It had no division instruction but could perform reciprocals. Division was performed as 1 reciprocal and 2 or 3 multiplications (depending on the precision needed). Thus division was only a little more complex than multiplication. (A reciprocal instruction took about twice the time of a multiply.)
See https://www.ed-thelen.org/comp-hist/CRAY-1-HardRefMan/CRAY-1...
So really, it's tradition that division (which is needed relatively rarely) is not performed quickly in hardware. The old time versus silicon tradeoff strikes again - you can have it quick but it will be expensive, how much do you want it?
Re the original question - (almost) anything can be done in enough silicon. Both multiplication and division could be done as very fast "ROM" lookups, but that would use an enormous amount of silicon.
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).
Division is a variation of the packing problem which (without constraint) is NP Hard.
If you set up a logarithmic number system, division would be easy but addition and subtraction would be very difficult, worth noting that difficulty is a function of the representation.
I assume for most programming languages there is no speed difference in writing
y = x/5.0
y = 0.2 * x
Division it's just the inverse of multiplication, which is another multiplication.
Entropy.
Kind of like recovering the creamer from your coffee, only with symbols.
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.
It’s not closed on the reals
Division has the same big-O complexity as multiplication.
https://en.wikipedia.org/wiki/Computational_complexity_of_ma...