Why is division more expensive than multiplication?

by

CPU’s ALU (Arithmetic-Logic Unit) executes algorithms, though they are implemented in hardware. Classic multiplications algorithms includes Wallace tree and Dadda tree. More information is available here. More sophisticated techniques are available in newer processors. Generally, processors strive to parallelize bit-pairs operations in order the minimize the clock cycles required. Multiplication algorithms can be parallelized quite effectively (though more transistors are required).

Division algorithms can’t be parallelized as efficiently. The most efficient division algorithms are quite complex (The Pentium FDIV bug demonstrates the level of complexity). Generally, they requires more clock cycles per bit. If you’re after more technical details, here is a nice explanation from Intel. Intel actually patented their division algorithm.

More Related Contents:

  1. Why is the loop instruction slow? Couldn’t Intel have implemented it efficiently?
  2. Enhanced REP MOVSB for memcpy
  3. How many CPU cycles are needed for each assembly instruction?
  4. Adding a redundant assignment speeds up code when compiled without optimization
  5. Is performance reduced when executing loops whose uop count is not a multiple of processor width?
  6. Why is Skylake so much better than Broadwell-E for single-threaded memory throughput?
  7. Understanding the impact of lfence on a loop with two long dependency chains, for increasing lengths
  8. How are x86 uops scheduled, exactly?
  9. Why does breaking the “output dependency” of LZCNT matter?
  10. What happens after a L2 TLB miss?
  11. What setup does REP do?
  12. Are there any modern CPUs where a cached byte store is actually slower than a word store?
  13. 32-byte aligned routine does not fit the uops cache
  14. Size of store buffers on Intel hardware? What exactly is a store buffer?
  15. Avoid stalling pipeline by calculating conditional early
  16. Lost Cycles on Intel? An inconsistency between rdtsc and CPU_CLK_UNHALTED.REF_TSC
  17. Why is a conditional move not vulnerable to Branch Prediction Failure?
  18. x86_64: is IMUL faster than 2x SHL + 2x ADD?
  19. Assembly – How to score a CPU instruction by latency and throughput
  20. Latency bounds and throughput bounds for processors for operations that must occur in sequence
  21. atomic operation cost
  22. Cycles/cost for L1 Cache hit vs. Register on x86?
  23. Why are loops always compiled into “do…while” style (tail jump)?
  24. Efficiently compute pairwise squared Euclidean distance in Matlab
  25. Should I use multiplication or division?
  26. Spark: Inconsistent performance number in scaling number of cores
  27. Faster implementation of verbal arithmetic in Prolog
  28. R: speeding up “group by” operations
  29. Ways to improve git status performance
  30. why is data structure alignment important for performance?

Leave a Comment