What's the most efficient implementation of map(x,0,1023,50,250)?

Question

I recently noticed how the map() function in Arduino was bulky in both terms of flash space used and time taken to execute, largely because it deals with long and involves a division and multiplication.

Many times you can replace maps with more basic functions i.e.

output = map(input,0,1023,0,255); 

can become

output = input >> 2;

or

output = map(input,0,1023,1023,0);

can become

output = 1023 - input;

I have one line in some code that says:

backlight = map(LDRreading,0,1023,50,250);

How could this be simplified so that it is both space and time efficient?

I'll allow slight differences in output values if it results in a much better solution.

Answer 1

The screenshot shows a base-2 (i.e. binary) result of calculating the constant part of a mapping. You can approximate this multiplication by a constant by a number of shifts added together. You need to break down each multiplication in the result first:

x * 0.001₂ = x >> 3

x * 0.0001₂ = x >> 4

x * 0.0000001₂ = x >> 7

Then add these together. You are essentially breaking it down into convenient base-2 multiplies (which can always be represented by shifts) and adds - nearly always more efficient.

This doesn't get you right to 250, but pretty close:

>>> for i in range(0, 1024, 34):
...   print (i >> 3) + (i >> 4) + (i >> 7) + 50
... 
50
56
62
   [snip]
235
241
247
>>> print (1023 >> 3) + (1023 >> 4) + (1023 >> 7) + 50
247

Do all your processing with a left-justified int (ADLAR=1) though, to minimize errors. The ADC returns a 10bit result, and ADLAR choses if this is aligned to the left or right of the two result registers.

Answer 2

How about this, mapping to 50..249?

output = ((input * 25) >> 7)+50;

Your input range was 1024 (0..1023). Output range is 200 (In the original specification, it would have been 201, which does not divide as neatly). These have a gcd of 8, so output = (input * (200/8)) / (1024/8) + 50 will do, and the division by a power of 2 can be expressed with a shift. The nice thing is that 1024*25 still fits into a 16 bit integer, so no longs are needed.

If you want full range, you can try throwing in rounding

output = ((input*25+64) >> 7)+50;

Answer 3

You could approximate it quite closely using only two integer operations:

backlight = (LDRreading / 5) + 46;

That effectively maps input range 0 - 1023 onto output range 46 - 250, so it's fairly accurate. If LDRreading is a 2 byte integer type then it should be significantly more efficient (comparatively speaking) than anything which uses long.

Answer 4

If the input range is limited in size and you have the memory for it nothing beats a simple lookup-table.

like
unsigned char map[1024] = { 50, 50, << more entries here >>, 250 } ;

You can pre-compute the content in a part of the program that isn't time-critical or just compute the entire table-content beforehand and put it verbatim in the source-code.

Doing a map is just a read of map[] with the original value as index.

If you input range starts with a non-zero number just decrement all inputs by the lower-bound value so you have a 0-base index for the map array. (That works for negative lower-bounds too !)

At most 1 substract (to adjust for a non-zero lower-bound) and 1 addition to calculate the array-base + index.
And a good compiler will be able to optimize it further.

You can't get more efficient than that, but you do need the space to store the table somewhere.