# 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. Apr 29, 2020 at 19:22
• Why not tell us what exactly your problem is, instead of asking for blind guesses? 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. 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. Apr 30, 2020 at 1:21