How map() loses precision and how to fix it

[PhoenixWilliams]

I noticed the built-in function map() loses precision when toMin > toMax, and so I derived map() from first principles to see how it works and what might be done to fix it. Turns out the fix is trivial (but see attached analysis).

map() as currently implemented:

long map(long x, long in_min, long in_max, long out_min, long out_max) {
  return (x - in_min) * (out_max - out_min) / (in_max - in_min) + out_min;
}

The term out_min at the end is an 'implicit' division. The term out_min is the simplified form of
out_min * (in_max - in_min) / (in_max - in_min) .

If map() were using floating-point arithmetic, dividing through to get out_min works, but map() doesn't use floating-point arithmetic - it uses integer arithmetic - and herein lies the problem: under certain circumstances the two forms produce values that differ by 1. This is due to truncation errors implicit in using y_min directly. Bad idea where that 1 might mean the difference between your code working or not - and more often than not it is a subtle bug to find. So, we need a map() function that delivers results we expect:

map() version 2:

long map2(long x, long in_min, long in_max, long out_min, long out_max) {
  return ((x - in_min) * (out_max - out_min) + out_min * (in_max - in_min)) / (in_max - in_min);
}

This second version produces results identical to a version of map() that uses floating-point arithmetic internally to compute its result and then casting the return value as (long).

As a rule of thumb when working with integer arithmetic that involves division operations: to preserve precision, do as much of the work in the numerator as possible before dividing through.

I've attached screen-grabs of my analysis in Microsoft Word. I've also attached the Word doc directly.

map2.doc (182 KB)

[Coding_Badly]

A topic that has been hashed a few times already. Example...
http://forum.arduino.cc/index.php?topic=46546.0

But, it is always good to see another perspective.

[PhoenixWilliams]

Thanks. Yes, map() has been brought up quite a few times, but none (at least, none that I have seen) address map()'s loss-of-precision.

As a trivial example, say you need to map the range [0,7] to [0,1] (there are better ways of mapping these two particular ranges, but I'm using them here as a simple example). map(), as implemented, gives two different outputs depending on the order of the argument values supplied.

According to map()'s documentation, it shouldn't matter, ie, map(x,0,7,1,0) should simply reverse the mapping that map(x,0,7,0,1) produces, but it doesn't, and it doesn't because map() does an 'implicit division' (see attached analysis in OP). This isn't addressed in any of the posts that I have seen.

Here is the output map() produces for all four arrangements of the above input values, ie, where
in_min < in_max, out_min < out_max
in_min > in_max, out_min < out_max
in_min < in_max, out_min > out_max
in_min > in_max, out_min > out_max

Testing map(x,0,7,0,1) over interval x=[0,7]
(asterisk (*) marks values of x within specified bounds)
x: 0, y: 0  *
x: 1, y: 0  *
x: 2, y: 0  *
x: 3, y: 0  *
x: 4, y: 0  *
x: 5, y: 0  *
x: 6, y: 0  *
x: 7, y: 1  *

Testing map(x,7,0,0,1) over interval x=[0,7]
(asterisk (*) marks values of x within specified bounds)
x: 0, y: 1  *
x: 1, y: 0  *
x: 2, y: 0  *
x: 3, y: 0  *
x: 4, y: 0  *
x: 5, y: 0  *
x: 6, y: 0  *
x: 7, y: 0  *

Testing map(x,0,7,1,0) over interval x=[0,7]
(asterisk (*) marks values of x within specified bounds)
x: 0, y: 1  *
x: 1, y: 1  *
x: 2, y: 1  *
x: 3, y: 1  *
x: 4, y: 1  *
x: 5, y: 1  *
x: 6, y: 1  *
x: 7, y: 0  *

Testing map(x,7,0,1,0) over interval x=[0,7]
(asterisk (*) marks values of x within specified bounds)
x: 0, y: 0  *
x: 1, y: 1  *
x: 2, y: 1  *
x: 3, y: 1  *
x: 4, y: 1  *
x: 5, y: 1  *
x: 6, y: 1  *
x: 7, y: 1  *

Note the difference? map()'s output is mostly ones when out_min and out_max are reversed, but mostly zeros otherwise. Even more noteworthy is that (theoretically, anyway) the output of the first and the last tests should be identical; reversing the order of one pair or reversing the order of the other pair should reverse the mapping, but when you reverse both pair you are effectively reversing the mapping twice. In other words, you should get the same results as if you hadn't reversed either one.

map2() preserves precision for integer division and so does not have this sensitivity to input-value order:

Testing map2(x,0,7,0,1) over interval x=[0,7]
(asterisk (*) marks values of x within specified bounds)
x: 0, y: 0  *
x: 1, y: 0  *
x: 2, y: 0  *
x: 3, y: 0  *
x: 4, y: 0  *
x: 5, y: 0  *
x: 6, y: 0  *
x: 7, y: 1  *

Testing map2(x,7,0,0,1) over interval x=[0,7]
(asterisk (*) marks values of x within specified bounds)
x: 0, y: 1  *
x: 1, y: 0  *
x: 2, y: 0  *
x: 3, y: 0  *
x: 4, y: 0  *
x: 5, y: 0  *
x: 6, y: 0  *
x: 7, y: 0  *

Testing map2(x,0,7,1,0) over interval x=[0,7]
(asterisk (*) marks values of x within specified bounds)
x: 0, y: 1  *
x: 1, y: 0  *
x: 2, y: 0  *
x: 3, y: 0  *
x: 4, y: 0  *
x: 5, y: 0  *
x: 6, y: 0  *
x: 7, y: 0  *

Testing map2(x,7,0,1,0) over interval x=[0,7]
(asterisk (*) marks values of x within specified bounds)
x: 0, y: 0  *
x: 1, y: 0  *
x: 2, y: 0  *
x: 3, y: 0  *
x: 4, y: 0  *
x: 5, y: 0  *
x: 6, y: 0  *
x: 7, y: 1  *

Another question about map() that was brought up in several posts concerns how it doesn't uniformly map an input range to an output range. Various ad hoc fixes were proposed to address this, none of them with much success. The closest one addresses only those cases where the slope is positive, but gives spurious results when it is negative. Ideally, the mapping should be insensitive to value order apart from the reversing the mapping as appropriate.

I've written a mapping function that addresses this concern, one that maps intervals. I'll write more about it in a later post but, briefly, this is how it uniformly maps the two intevals mentioned above.

This new function is called mapIntervals():

Testing mapIntervals(x,0,7,0,1) over interval x=[0,7]
(asterisk (*) marks values of x within specified bounds)
x: 0, y: 0  *
x: 1, y: 0  *
x: 2, y: 0  *
x: 3, y: 0  *
x: 4, y: 1  *
x: 5, y: 1  *
x: 6, y: 1  *
x: 7, y: 1  *

Testing mapIntervals(x,7,0,0,1) over interval x=[0,7]
(asterisk (*) marks values of x within specified bounds)
x: 0, y: 1  *
x: 1, y: 1  *
x: 2, y: 1  *
x: 3, y: 1  *
x: 4, y: 0  *
x: 5, y: 0  *
x: 6, y: 0  *
x: 7, y: 0  *

Testing mapIntervals(x,0,7,1,0) over interval x=[0,7]
(asterisk (*) marks values of x within specified bounds)
x: 0, y: 1  *
x: 1, y: 1  *
x: 2, y: 1  *
x: 3, y: 1  *
x: 4, y: 0  *
x: 5, y: 0  *
x: 6, y: 0  *
x: 7, y: 0  *

Testing mapIntervals(x,7,0,1,0) over interval x=[0,7]
(asterisk (*) marks values of x within specified bounds)
x: 0, y: 0  *
x: 1, y: 0  *
x: 2, y: 0  *
x: 3, y: 0  *
x: 4, y: 1  *
x: 5, y: 1  *
x: 6, y: 1  *
x: 7, y: 1  *

mapIntervals() is especially useful in applications where you're mapping say, for example, a potentiometer shaft-angle to a 10-LED bargraph display. Your application splits the total rotation angle (most pots are typically 270 degrees stop-to-stop) into ten sectors of 27 degrees each. Using map() will not work because it will light the tenth LED only when the analog value reaches 1023 (worse, noise on the analog pin may cause the display to flicker between LED 9 and LED 10). Not what you want. mapIntervals() maps the last 27-degree sector the same as it maps the other nine, ie, any angle within the last 27 degrees will light LED 10 just as the previous 27 lit LED 9.

For example: led_num = mapIntervals(analog_val,0,1023,1,10) maps the intervals:

analog_val       led_num  vals/interval
0 thru 102       1        103
103 thru 204     2        102  
205 thru 307     3        103
308 thru 409     4        102
410 thru 511     5        102
512 thru 614     6        103
615 thru 716     7        102
717 thru 819     8        103
820 thru 921     9        102
922 thru 1023   10        102
                          -----
                          1024

I'll post more about mapIntervals() later along with its theoretical treatment.

-PW

[Coding_Badly]

A version that works the same as mapIntervals with one multiplication and one division. It's a minor improvement over the one from the link in reply #1.

long map3( long x, long in_min, long in_max, long out_min, long out_max )
{
  long out_range;
  long in_range;

  out_range = out_max - out_min;
  if ( out_range > 0 )
    ++out_range;
  else if ( out_range < 0 )
    --out_range;
  else
    return( 0 );

  in_range = in_max - in_min;
  if ( in_range > 0 )
    ++in_range;
  else if ( in_range < 0 )
    --in_range;
  else
    // Is actually infinity but long has no such thing.  The least negative long is another choice.
    return( 0 );

  return (x - in_min) * (out_range) / (in_range) + out_min;
}

Some test code...

long map3( long x, long in_min, long in_max, long out_min, long out_max )
{
  long out_range;
  long in_range;

  out_range = out_max - out_min;
  if ( out_range > 0 )
    ++out_range;
  else if ( out_range < 0 )
    --out_range;
  else
    return( 0 );

  in_range = in_max - in_min;
  if ( in_range > 0 )
    ++in_range;
  else if ( in_range < 0 )
    --in_range;
  else
    // Is actually infinity but long has no such thing.  The least negative long is another choice.
    return( 0 );

  return (x - in_min) * (out_range) / (in_range) + out_min;
}

long map2(long x, long in_min, long in_max, long out_min, long out_max) {
  return ((x - in_min) * (out_max - out_min) + out_min * (in_max - in_min)) / (in_max - in_min);
}

void TestIt( long lft, long rgt, long in_min, long in_max, long out_min, long out_max )
{
  long x;
  long y1;
  long y2;
  long y3;

  for ( x = lft; x <= rgt; ++x )
  {
    y1 = map ( x, in_min, in_max, out_min, out_max );
    y2 = map2( x, in_min, in_max, out_min, out_max );
    y3 = map3( x, in_min, in_max, out_min, out_max );
    
    Serial.print( x );
    Serial.write( '\t' );
    Serial.print( y1 );
    Serial.write( '\t' );
    Serial.print( y2 );
    Serial.write( '\t' );
    Serial.print( y3 );
    Serial.println();
  }
}

void setup() 
{
  Serial.begin( 115200 );

  Serial.println( F( "Testing (x,0,7,0,1) over interval x=[0,7]" ) );
  TestIt( 0, 7,  0, 7, 0, 1 );

  Serial.println();
  Serial.println( F( "Testing (x,7,0,0,1) over interval x=[0,7]" ) );
  TestIt( 0, 7,  7, 0, 0, 1 );

  Serial.println();
  Serial.println( F( "Testing (x,0,7,1,0) over interval x=[0,7]" ) );
  TestIt( 0, 7,  0, 7, 1, 0 );

  Serial.println();
  Serial.println( F( "Testing (x,7,0,1,0) over interval x=[0,7]" ) );
  TestIt( 0, 7,  7, 0, 1, 0 );

  Serial.println();
  Serial.println( F( "Testing (x,0,1023,1,10) over interval x=[0,1023]" ) );
  TestIt( 0, 1023,  0, 1023, 1, 10 );

/***
  Serial.println();
  Serial.println( F( "Testing (x,0,7,-1,0) over interval x=[0,7]" ) );
  TestIt( 0, 7,  0, 7, -1, 0 );
***/
}

void loop() 
{
}

[PhoenixWilliams]

Thanks!

A few things about mapIntervals():

1. it rigorously continues the mapping for values of x outside the x-interval defined by [in_min,in_max];
2. because it always 'floors' its return value, it is insensitive to zero-crossings;
3. its reverse-mappings are mirror-images of its unreversed mappings.

Here are all four mappings' output for x=[-10,17] (symmetric about [0,7]):

Testing (x,0,7,0,1) over interval x=[-10,17]
x map() map2() map3() mapIntervals()
-10 -1 -1 -2 -3
-9 -1 -1 -2 -3
-8 -1 -1 -2 -2
-7 -1 -1 -1 -2
-6 0 0 -1 -2
-5 0 0 -1 -2
-4 0 0 -1 -1
-3 0 0 0 -1
-2 0 0 0 -1
-1 0 0 0 -1
0 0 0 0 0 *
1 0 0 0 0 *
2 0 0 0 0 *
3 0 0 0 0 *
4 0 0 1 1 *
5 0 0 1 1 *
6 0 0 1 1 *
7 1 1 1 1 *
8 1 1 2 2
9 1 1 2 2
10 1 1 2 2
11 1 1 2 2
12 1 1 3 3
13 1 1 3 3
14 2 2 3 3
15 2 2 3 3
16 2 2 4 4
17 2 2 4 4

Testing (x,7,0,0,1) over interval x=[-10,17]
x map() map2() map3() mapIntervals()
-10 2 2 4 4
-9 2 2 4 4
-8 2 2 3 3
-7 2 2 3 3
-6 1 1 3 3
-5 1 1 3 3
-4 1 1 2 2
-3 1 1 2 2
-2 1 1 2 2
-1 1 1 2 2
0 1 1 1 1 *
1 0 0 1 1 *
2 0 0 1 1 *
3 0 0 1 1 *
4 0 0 0 0 *
5 0 0 0 0 *
6 0 0 0 0 *
7 0 0 0 0 *
8 0 0 0 -1
9 0 0 0 -1
10 0 0 0 -1
11 0 0 -1 -1
12 0 0 -1 -2
13 0 0 -1 -2
14 -1 -1 -1 -2
15 -1 -1 -2 -2
16 -1 -1 -2 -3
17 -1 -1 -2 -3

Testing (x,0,7,1,0) over interval x=[-10,17]
x map() map2() map3() mapIntervals()
-10 2 2 3 4
-9 2 2 3 4
-8 2 2 3 3
-7 2 2 2 3
-6 1 1 2 3
-5 1 1 2 3
-4 1 1 2 2
-3 1 1 1 2
-2 1 1 1 2
-1 1 1 1 2
0 1 1 1 1 *
1 1 0 1 1 *
2 1 0 1 1 *
3 1 0 1 1 *
4 1 0 0 0 *
5 1 0 0 0 *
6 1 0 0 0 *
7 0 0 0 0 *
8 0 0 -1 -1
9 0 0 -1 -1
10 0 0 -1 -1
11 0 0 -1 -1
12 0 0 -2 -2
13 0 0 -2 -2
14 -1 -1 -2 -2
15 -1 -1 -2 -2
16 -1 -1 -3 -3
17 -1 -1 -3 -3

Testing (x,7,0,1,0) over interval x=[-10,17]
x map() map2() map3() mapIntervals()
-10 -1 -1 -3 -3
-9 -1 -1 -3 -3
-8 -1 -1 -2 -2
-7 -1 -1 -2 -2
-6 0 0 -2 -2
-5 0 0 -2 -2
-4 0 0 -1 -1
-3 0 0 -1 -1
-2 0 0 -1 -1
-1 0 0 -1 -1
0 0 0 0 0 *
1 1 0 0 0 *
2 1 0 0 0 *
3 1 0 0 0 *
4 1 0 1 1 *
5 1 0 1 1 *
6 1 0 1 1 *
7 1 1 1 1 *
8 1 1 1 2
9 1 1 1 2
10 1 1 1 2
11 1 1 2 2
12 1 1 2 3
13 1 1 2 3
14 2 2 2 3
15 2 2 3 3
16 2 2 3 4
17 2 2 3 4

Of course this all comes at the price of somewhat increased complexity. As this is a first draft, it probably can be simplified somewhat.

Here's your test with mapIntervals() included:

long ifloor(long n,long d){return ((n%d)<0L)?(n/d-1):n/d;}
long iceil(long n,long d){return ((n%d)>0L)?(n/d+1):n/d;}

long mapIntervals(long x, long in_min, long in_max, long out_min, long out_max)
{
  if(in_min==in_max) return 0x7FFFFFFF; // slope is infinite; return max (long)
  long x1,x2,y1,y2;
  if(((in_max-in_min)<0)!=((out_max-out_min)<0)) {
    // Slope is negative
    x1 = min(in_min,in_max) - 1;
    x2 = max(in_min,in_max);
    y1 = max(out_min,out_max) + 1;
    y2 = min(out_min,out_max);
  }
  else {
    // Slope is positive
    x1 = min(in_min,in_max);
    x2 = max(in_min,in_max) + 1;
    y1 = min(out_min,out_max);
    y2 = max(out_min,out_max) + 1;
  }
  long dx = x2-x1;
  long dy = y2-y1;
  return ifloor((x-x1)*dy+y1*dx,dx);
} // End mapIntervals()

long map3( long x, long in_min, long in_max, long out_min, long out_max )
{
  long out_range;
  long in_range;

  out_range = out_max - out_min;
  if ( out_range > 0 )
    ++out_range;
  else if ( out_range < 0 )
    --out_range;
  else
    return( 0 );

  in_range = in_max - in_min;
  if ( in_range > 0 )
    ++in_range;
  else if ( in_range < 0 )
    --in_range;
  else
    // Is actually infinity but long has no such thing.  The least negative long is another choice.
    return( 0 );

  return (x - in_min) * out_range / in_range + out_min;
}

long map2(long x, long in_min, long in_max, long out_min, long out_max) {
  return ((x - in_min) * (out_max - out_min) + out_min * (in_max - in_min)) / (in_max - in_min);
}

void TestIt( long lft, long rgt, long in_min, long in_max, long out_min, long out_max )
{
  long xLB = min(in_min,in_max);
  long xUB = max(in_min,in_max);
  long x;
  long y1;
  long y2;
  long y3;
  long y4;

  char s[80];
  sprintf(s,"\nTesting (x,%ld,%ld,%ld,%ld) over interval x=[%ld,%ld]",in_min,in_max,out_min,out_max,lft,rgt);
  Serial.println(s);
  Serial.println( F("x\tmap()\tmap2()\tmap3()\tmapIntervals()") );
  for ( x = lft; x <= rgt; ++x )
  {
    y1 = map ( x, in_min, in_max, out_min, out_max );
    y2 = map2( x, in_min, in_max, out_min, out_max );
    y3 = map3( x, in_min, in_max, out_min, out_max );
    y4 = mapIntervals( x, in_min, in_max, out_min, out_max );
   
    Serial.print( x );
    Serial.write( '\t' );
    Serial.print( y1 );
    Serial.write( '\t' );
    Serial.print( y2 );
    Serial.write( '\t' );
    Serial.print( y3 );
    Serial.write( '\t' );
    Serial.print( y4 );
    if((x>=xLB)&&(x<=xUB))Serial.print("\t*");
    Serial.println();
  }
}

void setup()
{
  Serial.begin( 115200 );

  long xOffset = 0L;
  long xMin = xOffset + 0L;
  long xMax = xOffset + 7L;

  long yOffset = 0L;
  long yMin = yOffset + 0L;
  long yMax = yOffset + 1L;

  long xMargin = 10L;
  long lft = xMin - xMargin;
  long rgt = xMax + xMargin;
  
//  Serial.println( F( "Testing (x,0,7,0,1) over interval x=[0,7]" ) );
//  TestIt( 0, 7,  0, 7, 0, 1 );
  TestIt( lft, rgt,  xMin, xMax, yMin, yMax );

//  Serial.println();
//  Serial.println( F( "Testing (x,7,0,0,1) over interval x=[0,7]" ) );
//  TestIt( 0, 7,  7, 0, 0, 1 );
  TestIt( lft, rgt,  xMax, xMin, yMin, yMax );

//  Serial.println();
//  Serial.println( F( "Testing (x,0,7,1,0) over interval x=[0,7]" ) );
//  TestIt( 0, 7,  0, 7, 1, 0 );
  TestIt( lft, rgt,  xMin, xMax, yMax, yMin );

//  Serial.println();
//  Serial.println( F( "Testing (x,7,0,1,0) over interval x=[0,7]" ) );
//  TestIt( 0, 7,  7, 0, 1, 0 );
  TestIt( lft, rgt,  xMax, xMin, yMax, yMin );

/***
  Serial.println();
  Serial.println( F( "Testing (x,0,1023,1,10) over interval x=[0,1023]" ) );
  TestIt( 0, 1023,  0, 1023, 1, 10 );
***/

/***
  Serial.println();
  Serial.println( F( "Testing (x,0,7,-1,0) over interval x=[0,7]" ) );
  TestIt( 0, 7,  0, 7, -1, 0 );
***/
}

void loop()
{
}

Interesting. The first time I previewed this, the test output looked here like the actual tabbed output. On second preview the columns are all bunched together. O.o

-PW