[Ovmsdev] Integer division approximation

[Mark Webb-Johnson]

Reminds me of the old way of doing *10

T1 = INPUT << 2
T2 = INPUT << 1
Result = T1 + T1 + T2

If you look in the OVMS v2 code (on that little 8bit PIC microcontroller), you’ll see lots of little kludges like this. Some for performance, and some to keep the calculation similar to other tiny MCUs in the car.

Regards, Mark.

> On 8 Jun 2024, at 11:06 PM, Michael Geddes via OvmsDev <ovmsdev at lists.openvehicles.com> wrote:
> 
> 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);
>       }
>     };
> 
> _______________________________________________
> OvmsDev mailing list
> OvmsDev at lists.openvehicles.com
> http://lists.openvehicles.com/mailman/listinfo/ovmsdev

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openvehicles.com/pipermail/ovmsdev/attachments/20240611/a627bea6/attachment.htm>