Faster way to convert a number from range to another range

Question

According to this SO question, it is possible to convert a number range to another (linear conversion) by calculating:

NewValue = (((OldValue - OldMin) * NewRange) / OldRange) + NewMin

However, I want to know if there is another faster way to do this.

Consider a microcontroller with no division instruction, converting massive amount of a ranges to another ranges (i.e. 24-bit color/pixels from image file to 18-bit color/pixels for the LCD display) would take sometime. I was thinking is there any way to optimze this.


Show source
| C   | optimization   | performance   | math   | c++   2017-01-02 04:01 2 Answers

Answers ( 2 )

  1. 2017-01-02 05:01

    24 bit color is usually 8 x 3 (3 components, 8 bits per).

    18 bit color is 6 x 3.

    A simple >>2 converts the range of 8 bit values to 6 bit values, "rounding down". And shift operations are fast on most hardware.

    Rounding to nearest is harder mainly because of overflow. Starrt with this:

    (x+2)>>2
    

    in a 16 bit value. The result is a value from 0 to 2^6, not 0 to 2^6-1 like you want. You'll have to detect that last case.

    If you can afford the ROM, a lookup table can be used. 256 entries isn't all that many. This may be more worth considering if you want to apply gamma or other corrections.

    But really, just >>2 and/or mask each component, then shift and mask into place.

    int32 r = ((pix>>2)&(0x3F<<0))|((pix>>4)&(0x3F<<6))|((pix>>6)&(0x3F<<12));
    

    Where pix is a 32 bit value storing your 24 bit pixel and r stores the 18 bit result.

    This kind of optimization requires profiling in as close to a real environment as possible.

  2. 2017-01-02 08:01

    Due to normal mathematical operator precedence the brackets in the formula are not needed except for one pair.

    Therefore your formula

    NewValue = (((OldValue - OldMin) * NewRange) / OldRange) + NewMin
    

    is the same as

    NewValue = (OldValue - OldMin) * NewRange / OldRange + NewMin
    

    or

    NewValue = (OldValue - OldMin) * (NewRange / OldRange) + NewMin
    

    If the values for the ranges are constant and known at compile time you could shortcut the division:

    NewValue = (OldValue - OldMin) * RangeFactor + NewMin
    

    But beware: This should only be used for floating point types. If you are using integers you will probably get larger rounding errors than with your formula.

◀ Go back