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;


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.


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.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
>>> print (1023 >> 3) + (1023 >> 4) + (1023 >> 7) + 50

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.

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

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;
  • 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. 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.

  • 1
    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.

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.

  • This is extremely space inefficient though and only marginally faster than the shift/add which gets very very close. 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). 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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.