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

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. 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.0012 = x >> 3

x * 0.00012 = x >> 4

x * 0.00000012 = 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.

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

``````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;
``````
• Actually I'd say the input range is 201 as both boundaries are included. – jfpoilpret Mar 26 '14 at 14:06
• @jfoilpret, I agree, that's why I said my solution (at least without the rounding) only covers 50..249. – microtherion Mar 26 '14 at 15:47
• 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. – jfpoilpret Mar 26 '14 at 16:55

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`.

• 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. – jfpoilpret Mar 27 '14 at 5:36

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 = { 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.

• This is extremely space inefficient though and only marginally faster than the shift/add which gets very very close. – Cybergibbons Mar 27 '14 at 8:43
• @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.) – Tonny Mar 27 '14 at 10:27
• "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). – Cybergibbons Mar 27 '14 at 12:23
• @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. – Tonny Mar 27 '14 at 15:41