[Ovmsdev] Integer division approximation

Michael Geddes frog at bunyip.wheelycreek.net
Sat Jun 8 23:06:03 HKT 2024


I'm really not sure if this would make enough difference to be useful - but
it's kinda neat.
It's basically a template class that turns    y = m * x / d  into  y = (c *
x) >> n
eg:    fast_int_muldiv<int, 10, 3>::op( x )

it is an approximation only, and the larger PREC value you give, the more
precise it is, and the larger integer it would need.  So a decent precision
would probably need a 64 bit integer.

I would need to do experiments on the ESP32 to really get an idea.  One
thing it does do is turn a  multiply and divide (like for imperial units)
into 2 operations.

//.

  constexpr unsigned floorlog2(unsigned x)
    {
    return x == 1 ? 0 : 1+floorlog2(x >> 1);
    }
  constexpr unsigned ceillog2(unsigned x)
    {
    return x == 1 ? 0 : floorlog2(x - 1) + 1;
    }
  /* Use a multiple and shift (right) to approximate a multiply and divide.
   * T - the intermediate type used.
   * M - The  multiplier (1 is fine)
   * D - The divisor
   * PREC - The precision required for the operation.
   */
  template<typename T, unsigned M, unsigned D, unsigned PREC=100>
  class fast_int_muldiv
    {
  public:
    static const uint8_t shift = ceillog2(D * PREC);
    // Gives the approx multiplier that fits with the chosen shift value .
    static const T mult = M* (((T(0x1) << shift)+(D>>1)) / D);

    // Perform the operation approx (val * M / D)
    static T op(T val)
      {
      // Make sure there is enough space (16bits) for a value.
      static_assert( (8 * sizeof(T)) >= (16 + shift + floorlog2(mult)),
          "Use a larger integer or smaller precision");
      return  ((val * mult) >> shift);
      }
    };
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openvehicles.com/pipermail/ovmsdev/attachments/20240608/f6aaed80/attachment.htm>


More information about the OvmsDev mailing list