title: Optimized modulo by a constant at runtime
body: <p>Compilers often have various methods for optimizing division and modulo by a constant into other operations. This is described in <a href="http://www.hackersdelight.org/divcMore.pdf" rel="nofollow noreferrer">hackers delight</a> (see also <a href="http://www.hackersdelight.org/magic.htm" rel="nofollow noreferrer">this page</a>).</p>
  
  <p>There is also some discussion regarding hash maps and how slow the modulo instruction is, and how to best map many large numbers into buffers of various sizes. One example is <a href="https://probablydance.com/2018/06/16/fibonacci-hashing-the-optimization-that-the-world-forgot-or-a-better-alternative-to-integer-modulo/" rel="nofollow noreferrer">found here</a>.</p>
  
  <p>The question is: can we, at runtime, precompute the needed constants for such an optimized modulo operation, such that it can be used to compute the modulo operation faster than using the modulo instruction?</p>
  
  <p>The linked hackers delight article focuses more on division than remainder, although of course remainder could be computed using rem = n - m*div where n/m = div + rem/m.</p>
  
  <p>One thing that worries me regarding this is that when it's done with the compiler, the constants are actual constants in the instructions, while if done at runtime, they would also be references to memory. I don't know if it's possible to generate executable instructions at runtime to overcome this.</p>