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

Scaling calculation

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.

• Cybergibbons: Great answer. I have clarified how you got from the calculator result to the code, hope that is ok.
• microtherion: This is an excellent technique in general, but the original range was 1024, not 1023 (the 0 counts).

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;

• jfpoilpret: Actually I'd say the input range is 201 as both boundaries are included.
• microtherion: @jfoilpret, I agree, that's why I said my solution (at least without the rounding) only covers 50..249.
• jfpoilpret: Ah ok, sorry I misunderstood your statement "output range is 200"; maybe you should add " (instead of the expected 201)" that would clarify your answer.

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.

• jfpoilpret: The problem with division by a number that is not a power of 2 is that the AVR has no instruction for it, hence the compiler has to generate a bunch of instructions for this computation, which makes the formula longer to calculate.

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.

• Cybergibbons: This is extremely space inefficient though and only marginally faster than the shift/add which gets very very close.
• Tonny: @Cybergibbons It is only marginally yes, but the question was about efficiency. If every cycle counts... Space efficiency could be an issue for larger tables, but I already mentioned that in my answer. I mainly posted this as a more generalized answer because many people don't realize that this technique exists at all. And it has far wider application than just Arduino's. (Check your C-library's implementation of isspace(), isalpha(). Most implementations use this technique extensively.)
• Cybergibbons: "both space and time efficient" was the question :). isalpha() certainly doesn't use a lookup table in avr-libc. It's very memory heavy - 1Kbyte of RAM (1/2) or flash (1/32).
• Tonny: @Cybergibbons Embedded Libc do (mostly) things differently, but generic ones often make extensive use of lookup-tables. I have to admit I missed the "space" word in my initial read of the question.