# Design Algorithms and Data Structures Around a Lack of Fast Integer Division

I had begun scouring my code for optimization opportunities (execution speed, data parallelism, workload parallelism) yesterday when I noticed that there are very few opportunities for speeding up integer divisions. Integer division is heavily used in a hot spot area. Not only is it slow relative to the bit shifts, it’s possibly a showstopper for vectorization (data parallelism). If I want to use SSE/AVX as the design currently stands, the easiest way is to sacrifice some range so that all the intermediate calculations fit in 53-bits—the precision of a `double` since there are no instructions for integer division. The lack of integer division support is also apparent with “division-free” being a frequent selling point such as for specialized algorithms in the compression/encoding space.

How common or relevant is it in decision-making processes to pursue (or consider) division-free algorithms and data structures that will end up in hot spot areas of applications? It’s still pretty early in the design process for me so there’s opportunity to consider future needs like parallelization and CPU-architecture-dependent performance characteristics.

• Any solution is as "common or relevant" to a problem as it fits to the problem. And optimization must always match the specific problem. Sorry, but I think without knowing exactly the problem you want to solve and the specific algorithm you want to implement for this goal, it makes not much sense to guess around if "division-free algorithms and data structures" might be of help. Commented Apr 29, 2020 at 19:22
• Why not tell us what exactly your problem is, instead of asking for blind guesses? Commented Apr 29, 2020 at 20:02
• If you have a small number of constant divisors, you can pre-compute the inverse such that multiplying by the inverse will give you the quotient, modulo the word size. This is a technique often used on old mini- and micro-computers for converting from binary to decimal. Commented Apr 29, 2020 at 20:37
• The subject matter may be more suitable for Computational Science Stack Exchange site. (Note: it is different from the Computer Science site.) Refer to their on-topic guideline for details. Commented Apr 30, 2020 at 1:21

Division always has been and always will be one of the slower operations for CPUs, no matter if integer or floating point. This has to do with the very nature of that operation. You can also see that by the fact that all clever compilers will optimize `f / 4.0` to `f * 0.25` and `i / 4` to `i >> 2` (f = floating point value; i = integer value), as there is no guarantee that this will be faster for sure but can you show me just one CPU where this will be slower? I don't know of any, so you can only win by this optimization. There used to be times where multiplication also was among the slower operations (still much faster than division, though) but today it is almost as or even equally fast as addition. And bit shifting has always been among the fastest operation a CPU would offer.