7

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.

Improve this question

4 Answers 4

Reset to default
9

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

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

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

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.

Improve this answer
1
  • 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. Commented Mar 27, 2014 at 5:36
2

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.

Improve this answer
4
  • This is extremely space inefficient though and only marginally faster than the shift/add which gets very very close. Commented Mar 27, 2014 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.) Commented Mar 27, 2014 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). Commented Mar 27, 2014 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. Commented Mar 27, 2014 at 15:41

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.