Efficient way to filter powers of 10

Projects General Guidance
1

The subject says filtering to powers of 10 but I've used this method with various divisors to filter at different levels. It works fine but as the amount of digits increases the code gets progressively more cumbersome. Curious if anyone has a more elegant solution.

The basic function leverages the truncating properties of integer math in order break down a large value and return the specific digit at each power of 10 location. So for example, 6,124 would be broken down into 10^3=6, 10^2=1, 10^1=2, 10^0=4. I use this primarily in tft/lcd display scenarios so that I can only update the specific digit that has changed rather than updating the whole string. This allows me to update the display faster and with less flickering. It also allows me to insert leading zeros if/when necessary. Example code is attached. Please understand that what I have below is only an example of the digit finding routine. the variable names and uses are purely illustrative.

int value = analogRead(0); // value can be anywhere from 0-1024

int val1k = value/1000; //val1k will either be 1 or 0 given the limited range of analogRead
int val100 = (value-(val1k*1000))/100; //subtract 1000's from value and find the digit in the 10^2 place
int val10 = (value-(val1k*1000)-(val100*100))/10; // find digit in 10^1 position
int val1 = value-(val1k*1000)-(val100*100)-(val10*10); //find the digit in the 10^0 position

As you can see, for a couple digits, the code isn't too bad but my current project is an speedo/odometer display so i want a readout up to 100k miles. The resulting code is difficult to look at. Is there something better or some kind of recursive function that I can use to achieve the same goal?

2

A simple table of integer powers of ten, and a loop?

3

How about

  int value = analogRead(0); // value can be anywhere from 0-1024

  int val1 = value % 10;   // find the digit in the 10^0 position
  value /= 10;
  int val10 = value % 10;  // find digit in 10^1 position
  value /= 10;
  int val100 = value % 10; // find the digit in the 10^2 place
  int val1k = value / 10;  // works up to 9xxx

?

4

Whandall:
How about

  int value = analogRead(0); // value can be anywhere from 0-1024

int val1 = value % 10;  // find the digit in the 10^0 position
  value /= 10;
  int val10 = value % 10;  // find digit in 10^1 position
  value /= 10;
  int val100 = value % 10; // find the digit in the 10^2 place
  int val1k = value / 10;  // works up to 9xxx


?

That's exactly the sort of elegant solution I was looking for. Thanks!

5

You could make the single digits bytes, as they are always between 0 and 9.

6

If this is just a number that's going up and up, it might be reasonable to just implement your own decimal adder. Just maintain one byte per digit, and when you want to add one, add it to the first byte. If that byte is 10, set it to zero and increment the second byte. If that byte is ten, set it to zero and increment the third, etc. No performance-killing divisions to perform, the digits are always ready to use, and because of how the carries "ripple" from one digit to the next, you automatically know which digits have changed, too. No need to do any before-vs-after comparisons.

7

First look up arrays, index 0 = the first digit (LS digit) index 1 the second and so on.

Then note that

  1. 100 = 10*10

  2. then for the ls digit of any it is

int temp = x/10

ls_digit_of_x = x-( temp*10 );

// and then make the new x
x=temp

@op Now you write a for loop to make this work Stop if temp is 0.

Don't forget to store ls_digit_of_x in the array. A minor change will make this work for negative numbers.

IT IS YOUR HOME WORK NOT MINE

@OP If you can do it with a for loop I'l show you a much better way

Mark

8

The divisions in the OP and the modulos (%) in post #2 are very time consuming. For something that's painting an LCD screen or outputting on serial a lot and it has lots of other things to do like controlling motors, then this gets to be a performance bottleneck.

You may not think so but repeated subtractions are actually faster than divisions for this kind of work.

  char c = '0';
  while(value >= 10000) {
    value -= 10000;
    c++;
  }
  Serial.write(c);
  c = '0';
  while(value >= 1000) {
    value -= 1000;
    c++;
  }
  Serial.write(c);
  c = '0';
  while(value >= 100) {
    value -= 100;
    c++;
  }
  Serial.write(c);
  c = '0';
  while(value >= 100) {
    value -= 100;
    c++;
  }
  Serial.write(c);
  c = '0';
  while(value >= 10) {
    value -= 10;
    c++;
  }
  Serial.write(c);
  c = '0' + value;  
  Serial.write(c);

Suppressing leading zeroes is left as an exercise. Obviously substitute your LCD or whatever for the Serial.write(). This method is also useful for sending data that has a checksum - you can add the character c to the checksum at each print. NMEA data is the most common example of checksums.

9

@MorganS - no need for many loops (for or while) you can doit with one loop - this avoids repeated code and therefore bugs!.

@awol et al I op has given 4 digits just as an example. This is a classic programming problem and the solution should work of ANY int of any size and any sign. I think both you and the OP have been mislead by the example.

Mark

10

I don't know how to do it with one loop, without using a divide operation or a lookup table. How do you do it?

It is obvious that I have 'unrolled' a loop, but where I used it, performance was critical and the unrolled loop was significantly faster. The input values were also constrained, so I knew how many digits I had to print.

11

This is a standard problem given to students and the OP is a student so I wont give any solution for now.

BUT I was given this as a programming problem way back when I was a student

I think that the OP has been told to write some code to print an int WITHOUT using print or the like!

In a day or two I'll send you/post two solutions but I do want to see what the OP comes up with!

But it can be done with just one loop or none! (none in this case without the repeated code!)

Mark

MorganS you have a PM

12

I am not a student and THIS IS NOT HOMEWORK. I am a mid 30's mechanical engineer that has been playing with coding and microprocessors since the late 90's. I have never taken, nor will I ever take, any sort of formal training to learn this stuff. Everything I know is the result of books, forums, and experimenting on my own. I DO have a passion for elegance and cleanliness in the things I create whether they be physical or coded which is why I ask questions like this but ultimately I'm interested in function over beauty.

Regarding this particular usage, I ask the question because the original code I posted was ugly and I was sure a better solution existed. The wording of the question was deliberately broad because I use this sort of function in a variety of ways. The current use requires powers of 10 because of the application but the first time I needed this sort of numeric reduction was to take a value of time from millis() and break it down into hours, minutes, and seconds. I had hoped to take a single answer from a broad question, and utilize it in multiple programs.

For the sake of detail I will reiterate that the current application is a speedometer/odometer display. The final build is months if not years away from completion because I am working on this in my spare time between work, wife, kids, etc. Again, referencing my desire for clean and elegant solutions, I will be using the existing speedometer pickup on the bike (inductive sensor). I've decided against using interrupts to count the pulses from the sensor because I'm not convinced that the other functions will continue to work properly as road speed increases. Instead I will be running the pulses through a frequency to voltage converter and monitor an analog input to determine current speed. The issue then became how to use an ever changing speed input to track how far I've gone. My solution there is not as elegant as I would like but should result in a reasonably accurate measurement. Each time the input is sampled, the current time is stored. The new sample and time are then compared to the previous sample and time, and the distance traveled is calculated based on those deltas. Unfortunately the divisor to convert to MPH from a millisecond time base is 3,600,000 and the time between samples is so short that even floating point math didn't work so I had to keep everything in integer form. However this caused my distance variable to overflow almost instantly at any speed. To correct for that I used an "if" routine to increments the odoTenths variable by 1 every time the distance variable reaches (or exceeds) 3,600,000 and then subtracts that 3600000 from the value of the distance variable. This keeps that variable down to a reasonable size without losing resolution from my measurement. The odo variable is then miles traveled x 10 which gives me a display resolution of .1 miles (typical of any display). That variable is then broken down into the individual 10^n components for the actual display. The original suggestion was a great one IMO but it had the failing that it modified the odo variable in order to perform the math which is something my current setup will not tolerate. What I ended up with is based on that suggestion and much cleaner than my original code, though still not "pretty". I spent some time working on a loop function to clean it up further but gave up before I found a good way to generate incrementing powers of 10. My searching came up with the pow() function but as that involves floating point math I decided against using it.

  static byte odo[6] = {0,0,0,0,0,0};
  static unsigned long odoTenths = 0;

  if (distance >= 3600000){
    odoTenths += 1;
    distance -= 3600000;
  }

  odo[0] = odoTenths/1 % 10;
  odo[1] = (odoTenths/10) % 10;
  odo[2] = (odoTenths/100) % 10;
  odo[3] = (odoTenths/1000) % 10;
  odo[4] = (odoTenths/10000) % 10;
  odo[5] = (odoTenths/100000) % 10;

@ holmes, I like your method in post 6 but it won't work (at least not directly as written) because it requires the tracking variable to be modified by the math routine. I was able to build my math into a loop that seems to be working but some additional testing is still needed. :

  byte odoIndex = 0;
  unsigned long odoDivide = 1;
  
  while (odoIndex < 6) {
    odo[odoIndex] = (odoTenths/odoDivide) % 10;
    odoDivide *= 10;
    odoIndex += 1;
  }
13

Again, if all you're doing is incrementing your odometer each time through, there's no need for any multiplications or divisions or any fanciness. Just increment the lowest digit, then the next, then the next, etc., in a loop:

#define ODO_DIGITS 6

byte odo[ODO_DIGITS] = {0};

void incOdo()
{
  for (int i = 0; i < ODO_DIGITS; i++)
  {
    // increment this digit
    odo[i]++;

    // bail out early if we don't need to carry
    if (odo[i] < 10)
    {
      break;
    }

    // we do need to carry; roll this digit over to zero and move on to the next
    odo[i] = 0;
  }
}
14

[quote author=soofle616 link=msg=31 My searching came up with the pow() function but as that involves floating point math I decided against using it.
[/quote]
Good choice. For this application it's totally unnecessary.

I think it is good to have a general-purpose solution rather than just an odometer. You might wish to use this to display battery volts or acceleration or anything.

15

jaholmes:
Again, if all you're doing is incrementing your odometer each time through, there's no need for any multiplications or divisions or any fanciness. Just increment the lowest digit, then the next, then the next, etc., in a loop:

Apologies, I don't think I fully understood what you were getting at in your previous post. Now that I see the code it makes a lot of sense. I'll have to think a bit on what the affects of that approach might be on the rest of my code but looking at it purely from the perspective of my original question it is a nice solution.

16

Finally got around to working on this some more and taking holmes's suggestion I have fully functional code that I'm quite pleased with. Thank you everyone for your help. I have included the relevant section of my finished code below. The full program is quite lengthy and includes several library functions that I wrote myself so it's not worth posting the whole thing.

void displayOdo(int currentSpd, int prevSpeed) {
  static long prevTime = millis();
  static long prevDistance = 0;
  static byte odo[6] = {0,0,0,0,0,0};
  long currentTime = millis();
  long elapsedTime = currentTime - prevTime;
  
  prevTime = currentTime;
  
  long distance = prevDistance + (((currentSpd + prevSpeed)/2)*elapsedTime);
  
  if (distance >= odoDivide){ 
    distance -= odoDivide;
    
    /*cycle through each digit of the odo and increment as needed
     *If the current digit is 0-8, increment that digit by 1, update the display, and exit the 
     *loop. Otherwise, reset that digit to 0 (digit has rolled over to next power of 10) and
     *continue to next digit
     */
    for (int i = 0; i < 6; i++) { 
      int xPos = 300 - 20*i;
      if (odo[i] < 9) {
        odo[i] += 1; 
        tft.drawChar(xPos, 200, getChar(odo[i]), 0xF800, 0x0000, 3);
        break;
      }
      else { 
        odo[i] = 0;
        tft.drawChar(xPos, 200, getChar(0), 0xF800, 0x0000, 3);
      }
    }
  }
  prevDistance = distance;
}