[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