NewMap() - map revisited

On the forum there has been multiple discussion about the map() function, e.g. http://www.arduino.cc/cgi-bin/yabb2/YaBB.pl?num=1257716581/all and http://www.arduino.cc/cgi-bin/yabb2/YaBB.pl?num=1278362349 and I want to add another one :slight_smile:

For a small test application I had to map relative large values to a smaller range. ‚ÄúAha lets use map()!‚ÄĚ, the code was straightforward but the output was strange and I recognized it as overflow and identified the overflow condition in the formula as given on http://www.arduino.cc/en/Reference/Map

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 code does the multiply before the division to be accurate as possible, (integer divisions are famous for their rounding and flooring results). However for large values this multiplication may overflow resulting in unexpected values. So I added a simple test to detect the overflow before it happens and added some code so the mapping would behave as one would expect.

The idea behind the additional code is to divide the input and the output range in half, and recall the map function recusively, either for the upper half or the lower half of the range (yes, inspired by binary-search algorithms). This will be done until there is no overflow condition anymore and the well known formula is used. My first implementation was completely recursive but this one is faster.

long NewMap(long val, long in_min, long in_max, long out_min, long out_max)
{
  #define MAXLONG 2147483647
  
  if ((MAXLONG / abs(out_max - out_min)) >= abs(val - in_min))   // test if there will be no overflow
  {
    // no overflow => use the well known formula
    return out_min + ((out_max - out_min) * (val - in_min)) / (in_max - in_min);
  }
  // if overflow would occur => divide the input & output range in two
  // Serial.print("<divide>"); // just to see the dividing
  long mid = in_min + (in_max - in_min)/2; 
  if (mid == in_min) return (out_max - out_min)/2;  // special case -> input range becomes effective zero
  long Tmid = out_min + (out_max - out_min)/2;  
  if (val >= mid) return NewMap(val, mid, in_max, Tmid, out_max);        // map with upper half of original range
  return NewMap(val, in_min, mid, out_min, Tmid);                                // map with lower half of original range
}

This sketch does some tests to compare the existing map() with newMap() under ‚Äúextreme conditions‚ÄĚ, however this is not exhaustive and new tests are welcome. Sofar newmap() behaves as expected where map() fails due to the overflow.

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

void loop()
{
  long y;
  Serial.println("TEST 1 =============================");

  for (int i=0; i<= 1023; i+=10)
  {
    y = map(i, 0, 1023, -123456789, 123456789); 
    Serial.print(i);
    Serial.print(" => ");
    Serial.println(y);
  }
  
  Serial.println("=============================");
      
  for (int i=0; i<= 1023; i+=10)
  {
    y = NewMap(i, 0, 1023, -123456789, 123456789); 
    Serial.print(i);
    Serial.print(" => ");
    Serial.println(y);
  }
  
  Serial.println("TEST 2 =============================");
    
  for (long i=0; i<= 1000000000; i+=10000000)
  {
    y = map(i, 0, 1000000000, -100, 100); 
    Serial.print(i);
    Serial.print(" => ");
    Serial.println(y);
  }
  
  Serial.println("=============================");
      
  for (long i=0; i<= 1000000000; i+=10000000)
  {
    y = NewMap(i, 0, 1000000000, -100, 100);
    Serial.print(i);
    Serial.print(" => ");
    Serial.println(y);
  }
  
  Serial.println("TEST 3 =============================");
    
  for (long i=0; i<= 1000000; i+=12345)
  {
    y = map(i, 0, 1000000, -1000000, 1000000); 
    Serial.print(i);
    Serial.print(" => ");
    Serial.println(y);
  }
  
  Serial.println("=============================");
      
  for (long i=0; i<= 1000000; i+=12345)
  {
    y = NewMap(i, 0, 1000000, -1000000, 1000000);
    Serial.print(i);
    Serial.print(" => ");
    Serial.println(y);
  }
  
   while (1);
}

Open for additional tests and comments.

Rob

Neither the existing map function or your new one are idiot-proof, like they should be. What happens if in_min == in_max?

What happens in your code if the to range endpoints are equal?

Rob,

it's nice that you take up the discussion about map, but your solution seems to address a part of the matter, the overflow. The result of the mapping is with mapping to small resulting range (eg 0-1) still not balanced. If one decides to rework that function, please do it properly and fix that too. For inspiration look at the algorithms published by Bresenham in the early 1960ies.

Paul, that would be easy to fix. If I get bored, I might rewrite the function to work properly and deliver a uniform and symmetric distribution of the input range into the output range.

Korman

What happens if in_min == in_max?

it explodes ?

What happens in your code if the to range endpoints are equal?

it explodes (again) ?

Good additional tests ! Thanks,

Be back in a minute :)


  y = map(10,0,1023,0,0);
  Serial.println(y);
  
  y = NewMap(10,0,1023,0,0);
  Serial.println(y);
  
  y = map(10,0,0,0,0);
  Serial.println(y);
  
  y = NewMap(10,0,0,0,0);
  Serial.println(y);
  
  y = map(0,0,0,0,0);
  Serial.println(y);
  
  y = NewMap(0,0,0,0,0);
  Serial.println(y);

results in:

0
0
-1
0
-1
0

So it did not explode map() returned -1 twice, definitely out of range NewMap() consequently returned 0, which is what one should expect. (although I did not know beforehand)

More tests welcome ...

If the ranges are the same, you get a divide by 0. Since the Arduino does not have exception handling, the exception is ignored.

Still, it's better to take some action to prevent the exception rather than just ignoring it.

You are 100% right, the fact that the output is what one expects is pure luck. An update of the compiler and it could behave differently. So, back to the drawingboard :)

Back from the drawingboard with a new version of NewMap() and an additional function called BalancedMap().

NewMap() does a number of tests to prevent errors and detect special conditions. If overflow would occur in the well known formula it will call NewMap() recursively with the ranges divided by two. Finally the code calls either the ‚Äúold‚ÄĚ map function or a newer BalancedMap() function.

Notes:

  • In the code below the code of BalancedMap is embedded in Newmap(). One can choose to replce this with the original map() formula.
  • Due to the divide by 2 tactic to handle large ranges - in NewMap() - there occur small errors that still need attention.
  • TODO: write a non recursive version that uses less memory.

Code of BalancedMap()

// balanced map
// PRE-CONDITIONS: 
// 1: in_max - in_min < MAXLONG
// 2: in_min <= val <= in_max
// 3: out_max - out-min < MAXLONG
// 4: ((pos * nov)+ niv-1) < MAXLONG
long BalancedMap(long val, long in_min, long in_max, long out_min, long out_max)
{
  // TEST: in_min must be lower than in_max => flip the ranges
  // must be done before out of range test
  if (in_min > in_max) return BalancedMap(val, in_max, in_min, out_max, out_min);

  // TEST: if input value out of range it is mapped to border values. By choice.
  if (val <= in_min) return out_min;
  if (val >= in_max) return out_max;

  // TEST: special range cases
  if (out_min == out_max) return out_min;
  if (in_min == in_max) return out_min/2 + out_max/2;    // out_min or out_max? better

  unsigned long niv = in_max - in_min + 1;          // number input valuer
  unsigned long nov = abs(out_max - out_min) + 1;   // number output values
  unsigned long pos = val - in_min + 1;             // position

  // new position with rounding;
  unsigned long newpos = ((pos * nov)+ niv-1) / niv;  
  if (out_min < out_max) return out_min + newpos -1;
  return out_min - newpos + 1;
}

NewMap with testcode will be in next message.

So time to shoot again :slight_smile:

update: added tests and some comments

Code of NewMap() - currently with the BalancedMap code embedded - with several tests comparing the existing (old) map() versus the NewMap() .

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

void loop()
{
  long y;

  Serial.println("TEST 0 =============================");

  y = map(10,0,1023,0,0);     
  Serial.println(y);
  y = NewMap(10,0,1023,0,0);  
  Serial.println(y);

  Serial.println();

  y = map(10,0,0,0,0);        
  Serial.println(y);
  y = NewMap(10,0,0,0,0);     
  Serial.println(y);

  Serial.println();

  y = map(0,0,0,0,0);         
  Serial.println(y);
  y = NewMap(0,0,0,0,0);      
  Serial.println(y);

  Serial.println();

  y = map(-1,10,0,0,10);      
  Serial.println(y);
  y = NewMap(-1,10,0,0,10);   
  Serial.println(y);

  Serial.println();

  // BUG should return 5   
  y = map(1,-2147483647L,2147483647L,0,10);      
  Serial.println(y);
  y = NewMap(1,-2147483647L,2147483647L,0,10);   
  Serial.println(y);


  Serial.println(); 
  Serial.println("TEST 1 =============================");
  Serial.println("y = map(i, 0, 1023, -123456789, 123456789);");
  Serial.println();

  for (int i=0; i<= 1024; i+=103)
  {
    y = map(i, 0, 1023, -123456789, 123456789); 
    Serial.print(i);
    Serial.print(" old => ");
    Serial.print(y);
    y = NewMap(i, 0, 1023, -123456789, 123456789); 
    Serial.print("\t new => ");
    Serial.println(y);
  }

  Serial.println();
  Serial.println("TEST 2 =============================");
  Serial.println("y = map(i, 0, 1000000000, -100, 100);");
  Serial.println();

  for (long i=0; i<=1000000000; i+=100000000)
  {
    y = map(i, 0, 1000000000, -100, 100); 
    Serial.print(i);
    Serial.print(" old => ");
    Serial.print(y);
    y = NewMap(i, 0, 1000000000, -100, 100);
    Serial.print("\t new => ");
    Serial.println(y);
  }

  Serial.println();
  Serial.println("TEST 3 =============================");
  Serial.println("y = map(i, 0, 1000000, -1000000, 1000000);");
  Serial.println();

  for (long i=0; i<= 1000000; i+=100000)
  {
    y = map(i, 0, 1000000, -1000000, 1000000); 
    Serial.print(i);
    Serial.print(" old => ");
    Serial.print(y);
    y = NewMap(i, 0, 1000000, -1000000, 1000000);
    Serial.print("\t new => ");
    Serial.println(y);
  }

  Serial.println();
  Serial.println("TEST 4 =============================");
  Serial.println("y = map(i, 0, 1000000, 1000000, -1000000);");
  Serial.println();

  for (long i=0; i<= 1000000; i+=100000)
  {
    y = map(i, 0, 1000000, 1000000, -1000000); 
    Serial.print(i);
    Serial.print(" old => ");
    Serial.print(y);
    y = NewMap(i, 0, 1000000, 1000000, -1000000);
    Serial.print("\t new => ");
    Serial.println(y);
  }

  Serial.println();
  Serial.println("TEST 5 =============================");
  Serial.println("y = map(i, 0, 10, 0, 1);");
  Serial.println();
  for (int i=0; i <= 10; i++) 
  {
    y = map(i, 0, 10, 0, 1); 
    Serial.print(i);
    Serial.print(" old => ");
    Serial.print(y);
    y = NewMap(i, 0, 10, 0, 1);
    Serial.print("\t new => ");
    Serial.print(y);
    y = BalancedMap(i, 0, 10, 0, 1);
    Serial.print("\t B => ");
    Serial.println(y);
  }
  
  Serial.println();
  Serial.println("y = map(i, 0, 10, 0, 1);");
  Serial.println();
  
  for (int i=0; i <= 10; i++) 
  {
    y = map(i, 0, 10, 0, -1); 
    Serial.print(i);
    Serial.print(" old => ");
    Serial.print(y);
    y = NewMap(i, 0, 10, 0, -1);
    Serial.print("\t new => ");
    Serial.print(y);
    y = BalancedMap(i, 0, 10, 0, -1);
    Serial.print("\t B => ");
    Serial.println(y);
  }

  Serial.println();
  Serial.println("TEST 6 =============================");
  Serial.println("y = map(i, 0, 10 0, 6);");
  Serial.println();
  for (int i=0; i <= 10; i++) 
  {
    y = map(i, 0, 10, 0, 6); 
    Serial.print(i);
    Serial.print(" old => ");
    Serial.print(y);
    y = NewMap(i, 0, 10, 0, 6);
    Serial.print("\t new => ");
    Serial.print(y);
    y = BalancedMap(i, 0, 10, 0, 6);
    Serial.print("\t B => ");
    Serial.println(y);
  }
  Serial.println();
  Serial.println("y = map(i, 0, 20, 0, -4); ");
  Serial.println();
  for (int i=0; i <= 20; i++) 
  {
    y = map(i, 0, 20, 0, -4); 
    Serial.print(i);
    Serial.print(" old => ");
    Serial.print(y);
    y = NewMap(i, 0, 20, 0, -4);
    Serial.print("\t new => ");
    Serial.print(y);
    y = BalancedMap(i, 0, 20, 0, -4);
    Serial.print("\t B => ");
    Serial.println(y);
  }

  Serial.println("Done...");
  while (1);
}

////////////////////////////////////////////////////////////////////////////////
//
// NewMap
//

#define MAXLONG 2147483647

long NewMap(long val, long in_min, long in_max, long out_min, long out_max)
{
  // TEST: in_min must be lower than in_max => flip the ranges
  // must be done before out of range test
  if (in_min > in_max) return NewMap(val, in_max, in_min, out_max, out_min);

  // TEST: if input value out of range it is mapped to border values. By choice.
  if (val <= in_min) return out_min;
  if (val >= in_max) return out_max;

  // TEST: special range cases
  if (out_min == out_max) return out_min;
  if (in_min == in_max) return out_min/2 + out_max/2;    // out_min or out_max? better

  // test if there will be an overflow with well known (unbalanced) formula
  if (( (MAXLONG / abs(out_max - out_min)) < (val - in_min) )  // multiplication overflow test
  || ((MAXLONG - in_max) < -in_min ))                        // division overflow test
  {
    // if overflow would occur that means the ranges are too big
    // To solve this we divide both the input & output range in two
    // alternative is to throw an error.
    // Serial.print(" >> "); // just to see the dividing
    long mid = in_min/2 + in_max/2; 
    long Tmid = out_min/2 + out_max/2;  
    if (val > mid)
    { 
      // map with upper half of original range
      return NewMap(val, mid, in_max, Tmid, out_max);
    } 
    // map with lower half of original range
    return NewMap(val, in_min, mid, out_min, Tmid);  
  }

  // finally we have a range that can be calculated
  // unbalanced
  // return out_min + ((out_max - out_min) * (val - in_min)) / (in_max - in_min);
  
  // or balanced
  // return BalancedMap(val, in_min, in_max, out_min, out_max);
  unsigned long niv = in_max - in_min + 1;          // number input valuer
  unsigned long nov = abs(out_max - out_min) + 1;   // number output values
  unsigned long pos = val - in_min + 1;             // position of val

  unsigned long newpos = ((pos * nov) + niv-1) / niv;  // new position with rounding
  if (out_min < out_max) return out_min + newpos -1;
  return out_min - newpos + 1;
}