Take the 2-minute tour ×
Arduino Stack Exchange is a question and answer site for developers of open-source hardware and software that is compatible with Arduino. It's 100% free, no registration required.

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.

share|improve this question
add comment

4 Answers 4

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.

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

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;
share|improve this answer
    
Actually I'd say the input range is 201 as both boundaries are included. –  jfpoilpret Mar 26 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 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 at 16:55
    
Thanks for the suggestion. Done. –  microtherion Mar 26 at 18:39
add comment

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.

share|improve this answer
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 at 5:36
add comment

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.

share|improve this answer
    
This is extremely space inefficient though and only marginally faster than the shift/add which gets very very close. –  Cybergibbons Mar 27 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 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 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 at 15:41
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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