Extracting individual digits of a multi digit decimal

[Dan Moos]

I want to control a multi digit seven segment display. The numbers 0 to 9 are easy. It's when I get into numbers requiring multiple digits that I'm needing help.

I don't want a simple sequential count. That too would be easy. I want to take an arbitrary 4 digit number, and display it.

Seems to me some method of extracting the individual digits is in order. I considered converting the number to BCD, and going from there, but I think that might be an unnecessary step.

I imagine I want to do something along the lines of successively dividing by ten and taking what's on the left of the decimal point. Basically like a bitwise shift, but with decimals.

Am I on the right track?

[amyk]

Yes. Repeatedly divide by 10 and the remainders will be the digits.

That assumes the platform you're using has a divide instruction, or doing it in software (shift+subtract) is not too slow. Otherwise there are other more complex methods.

[Dan Moos]

Ok. So I'm on an 8 bit avr running at 8 mHz. My project isn't very computationally intensive though.

So basically I want a modulus function rather than an actual divide, right? I strongly suspect my hardware supports neither, so I'm curious what clever software methods there are ( besides just doing plain divide or modulus). You mentioned some sort of shift and subtract. Care to elaborate? I'm pretty uneducated when it comes to clever math tricks on micros.

[IanB]

You have a four digit decimal number in the range 0 to 9999?

The brute force approach is to break it down digit by digit.

First find the thousands digit. Repeatedly subtract 1000 until the number goes negative and then add back the last one. That's your first digit.

Now repeatedly subtract 100 until the number goes negative and add back the last one. That gives the hundreds digit.

Follow the same process for the tens and units digits. At worst you will have made 40 subtractions.

If you are really keen you could try to optimize it using powers of two, but it may not really be worth it.

[rstofer]

Google is full of BCD to binary conversion algorithms.  Here's a pretty neat one

http://www.eng.utah.edu/~nmcdonal/Tutorials/BCDTutorial/BCDConversion.html

This has the advantage of only using shifts, no multiplication or division.  It is also for an 8 bit binary but it probably works for larger values.  You need to see how it responds to signed char as the example is using unsigned char.  If it doesn't work for signed char (or signed short), I would save the sign and convert to a positive value.  You would do that anyway for display.

The C function is itoa() - integer to ASCII in this case.

[GK]

Sometimes efficiency isn't a priority and you just want the code function to be easy to interpret.

Code: [Select]

yh = three_digit_decimal_number / 100;                     
yt = three_digit_decimal_number - (yh * 100);           
yu = yt - 10 * (yt / 10);                             
yt = yt / 10;

[Dan Moos]

So GK's method honestly is probably the way I'll go since I think I can spare the cycles, but...

How does one go about figuring out how much a particular arithmetic operation costs? I don't believe I have a profiler (running Atmel Studio with an avr Dragon using debug Wire.

[IanB]

So GK's method honestly is probably the way I'll go since I think I can spare the cycles, but...

How does one go about figuring out how much a particular arithmetic operation costs? I don't believe I have a profiler (running Atmel Studio with an avr Dragon using debug Wire.

Normally you should find in the data sheet a table of processor instructions and the number of CPU cycles required for each. You can look at the generated assembly and add them up.

[Someone]

So GK's method honestly is probably the way I'll go since I think I can spare the cycles, but...

How does one go about figuring out how much a particular arithmetic operation costs? I don't believe I have a profiler (running Atmel Studio with an avr Dragon using debug Wire.

Atmel studio does include debugging and simulation tools to do this, you typically add breakpoints at the entry/exit and check the elapsed time for a series of different values. The documentation is top notch:
http://www.atmel.com/webdoc/atmelstudio/atmelstudio.Debug.Views.ProcessorView.html

[snarkysparky]

void MakeDigits(unsigned int inval)
{
   DigVals[3] = 0x000a; DigVals[2] = 0x000a; DigVals[1]=0x000a; DigVals[0] = 0x0000; // clear digits
   
   if(inval > 9999)inval = 9999;  //  max display
   
   if(inval > 999 )   //   extract thousands digit
   {
      if(inval > 4999)      //
      {
         if(inval > 8999)
         {
           DigVals[3] = 9;
           inval = inval - 9000;
         }
         else if(inval > 7999)
         {
            DigVals[3] = 8;
            inval = inval - 8000;
         }
         else if(inval > 6999)
         {
            DigVals[3] = 7;
            inval = inval - 7000;
         }
         else if(inval > 5999)
         {
           DigVals[3] = 6;
           inval = inval - 6000;
         
         }
         else
         {
           DigVals[3] = 5;
           inval = inval - 5000;
         }
      }  //  if(inval > 4999)
      else      // inval between 4999 and 1000
      {
         if(inval > 3999)        // 4000 - 4999
         {
           DigVals[3] = 4;
           inval = inval - 4000;
         }
         else if(inval > 2999)   // 3000 - 3999
         {
            DigVals[3] = 3;
            inval = inval - 3000;
         }
         else if(inval > 1999)    // 2000 - 2999
         {
            DigVals[3] = 2;
            inval = inval - 2000;
         }
         else                     //  1000 - 1999
         {
           DigVals[3] = 1;
           inval = inval - 1000;
         }

     
      } 
      DigVals[2] = 0x0000; DigVals[1]=0x0000; DigVals[0] = 0x0000; // fill with zeros
   
    }//  if(inval >999)
   
   
   
   if(inval > 99 )   //  extract the hundreds digit
   {
      if(inval > 499)      //
      {
         if(inval > 899)
         {
           DigVals[2] = 9;
           inval = inval - 900;
         }
         else if(inval > 799)
         {
            DigVals[2] = 8;
            inval = inval - 800;
         }
         else if(inval > 699)
         {
            DigVals[2] = 7;
            inval = inval - 700;
         }
         else if(inval > 599)
         {
           DigVals[2] = 6;
           inval = inval - 600;
         }
         else
         {
           DigVals[2] = 5;
           inval = inval - 500;
         }
      }  //  if(inval > 499)
      else      // inval between 499 and 100
      {
         if(inval > 399)        // 400 - 499
         {
           DigVals[2] = 4;
           inval = inval - 400;
         }
         else if(inval > 299)   // 300 - 399
         {
            DigVals[2] = 3;
            inval = inval - 300;
         }
         else if(inval > 199)    // 200 - 299
         {
            DigVals[2] = 2;
            inval = inval - 200;
         }
         else                   //  100 - 199
         {
           DigVals[2] = 1;
           inval = inval - 100;

         }

     
      }
     DigVals[1]=0x0000; DigVals[0] = 0x0000; // fill tens and ones dec with zeros
     
     
   }//  if(inval > 99)
   if( inval > 9 )      //  get the tens digit
   {
      if(inval > 49)   //  50 - 99
      {
        if(inval > 89)    // 90 - 99
        {
           DigVals[1] = 9;
           inval = inval - 90;
        }
        else if(inval > 79)
        {
           DigVals[1] = 8;
           inval = inval - 80;
        }
        else if(inval > 69)
        {
           DigVals[1] = 7;
           inval = inval - 70;
        }
        else if(inval > 59)
        {
           DigVals[1] = 6;
           inval = inval - 60;
        }
        else
        {
           DigVals[1] = 5;
           inval = inval - 50;
        }
      }// if(inval > 49)
      else      // 10 - 49
      {
        if(inval > 39)    // 10 - 40
        {
           DigVals[1] = 4;
           inval = inval - 40;
        }
        else if(inval > 29)
        {
           DigVals[1] = 3;
           inval = inval - 30;
        }
        else if(inval > 19)
        {
           DigVals[1] = 2;
           inval = inval - 20;
        }
        else
        {
           DigVals[1] = 1;
           inval = inval - 10;
        }
      }
     
    }
    DigVals[0] = inval; //  at this point inval should be less than 10




}

[Kalvin]

void MakeDigits(unsigned int inval)
{
   <snip>
}

Totally awful!   

[T3sl4co1l]

For an example of an efficient approach, here's how the divide-by-10 might be implemented:
http://www.seventransistorlabs.com/uDivTen.asm.txt
Naturally, it's cryptic assembly, but hey, you asked.

Long-hand division (not shown here) is done the same way you do long division by hand, with the simplification that, since the running remainder can only possibly have a one or a zero in the relevant place (conveniently arranged so it's the sign bit), the actual operation is a shift and conditional subtraction.  On AVR, it takes about 220 CPU cycles.

The above method is accurate for a constant divisor.  It uses the precomputed reciprocal, and multiplies the dividend by it.  The extra (fraction) bits are the remainder.  Because AVR has a hardware multiply, this operation can be very fast, even though it's a roundabout method, conceptually.

A compiler probably won't output a function like this, for constant division, but will use the long-hand function instead (built into a library).  A compiler will use an in-line operation where the division is a power of 2, however: those reduce to a shift-right operation.  You will often see programmers write "x = y / 16" as "x = y >> 4", explicitly.

Completing an operation such as "sprintf("%n", var_is_uint16_t)", in standard C and libraries, should take on the order of several thousand clock cycles to finish.  (There's also a lot of wasted cycles and code space, spent jumping over the very complicated parts of sprintf, if it's a fully C-compliant sprintf.)

Tim

[snarkysparky]

void MakeDigits(unsigned int inval)
{
   <snip>
}

Totally awful!   

Ow now it ain't that bad.  I happen to like it, and am quite proud of it.  My code frequently gets similar responses though.  I would really appreciate an in depth critique from anyone who has the time.   I will only reply once. 
thanks

[Kalvin]

This thread has some solutions:
https://www.eevblog.com/forum/microcontrollers/memory-efficient-int-to-chars-without-division-(bitshift-ok)-for-binary-bases/
The thread has some requirements for the formatting and different bases, but removing the extra options will give a nice solution.

[AndyC_772]

I would really appreciate an in depth critique from anyone who has the time.   I will only reply once. 

I'm afraid I agree with Kalvin here, your solution could be a lot better in many different ways. Here's a few metrics which you might like to consider.

- how much space does your solution take up?
- how easy is it to see how it's meant to work?
- how easy is it to see that it actually does work, without silly mistakes (such as typos) which could stop it from working under some conditions?
- how fast is it? Has it been optimised to an appropriate degree given how often it'll be called, and the time constraints which might apply when it is called?
- how easy is it to modify in order to, say, add additional digits, or support for negative numbers, or decimal places, or leading zero suppression, or... whatever?

[newbrain]

void MakeDigits(unsigned int inval)
{
   <snip>
}

Totally awful!   

Ow now it ain't that bad. I happen to like it, and am quite proud of it.  My code frequently gets similar responses though.  I would really appreciate an in depth critique from anyone who has the time.   I will only reply once. 
thanks

"Ogni scarrafone è bell'a mamma soja" (literally: every cockroach is beautiful to its mother").
I will not go deep into the code, apart from the first and last line:
- is there a reason to init some digits to 0x000A? That seems wrong. Also, is DigVals a global?
- how's the value returned? (see above)

And leave these two notes:
- think of the poor guy that will see this "scarrafone" some months or years from now (and it could be you).
- even worse, think of the tests needed to prove that this code works, with respect to the straightforward one.

[snarkysparky]

- how much space does your solution take up?
Well it has lots of int comparisons and int assignments.  All of which are single cycle on most machines. 

- how easy is it to see how it's meant to work?
It seems to me much easier to comprehend than some other solutions posted here.  Custom assembler routines for division

- how easy is it to see that it actually does work, without silly mistakes (such as typos) which could stop it from working under some conditions?
See above answer.

- how fast is it? Has it been optimised to an appropriate degree given how often it'll be called, and the time constraints which might apply when it is called?
Without hardware division ( the situation posed by the OP )  I would ball park it to be 20X faster.  Worst case is 21 integer comparisons and branches.  Even on AVR these
are single cycle.


- how easy is it to modify in order to, say, add additional digits, or support for negative numbers, or decimal places, or leading zero suppression, or... whatever?
Not so easy I admit. 

Do note that IanB ( a supercontributor )  advocated this method.  His code would have been a lot nicer I am sure.

Given that this is how I would code the thing in the workplace ( with some cleanup ) should I give up on working as a programmer.  I ask seriously because I usually really really really don't get the basis for complaints against my code.  I have been thinking of this for some time.  Fear not hurt feelings let me have it.  ( I have other things I can do to put food on table )

[snarkysparky]

void MakeDigits(unsigned int inval)
{
   <snip>
}

Totally awful!   

Ow now it ain't that bad. I happen to like it, and am quite proud of it.  My code frequently gets similar responses though.  I would really appreciate an in depth critique from anyone who has the time.   I will only reply once. 
thanks

"Ogni scarrafone è bell'a mamma soja" (literally: every cockroach is beautiful to its mother").
I will not go deep into the code, apart from the first and last line:
- is there a reason to init some digits to 0x000A? That seems wrong. Also, is DigVals a global?
- how's the value returned? (see above)

And leave these two notes:
- think of the poor guy that will see this "scarrafone" some months or years from now (and it could be you).
- even worse, think of the tests needed to prove that this code works, with respect to the straightforward one.

0x000a flags the digit as invalid if not modified.  I know the global variable sucks and the lack of documentation.  I accept your criticisms,  this code I snipped from a home project thermocouple display.  Still it isn't the most useless post in the thread.  Thanks for the feedback.

[FrankBuss]

So GK's method honestly is probably the way I'll go since I think I can spare the cycles, but...

How does one go about figuring out how much a particular arithmetic operation costs? I don't believe I have a profiler (running Atmel Studio with an avr Dragon using debug Wire.

What I do to measure the runtime of a function on hardware is usually to use a high resolution timer on the hardware. If this is not available, I set a GPIO high on start and low on end of the function, then measure it with an oscilloscope. Much easier than counting cycles. But be careful, it doesn't give you a worst case runtime, just the tests you are doing. But you could run all possible values for your case and turn on persistence on the scope.

[rstofer]

- how much space does your solution take up?
Well it has lots of int comparisons and int assignments.  All of which are single cycle on most machines. 

The OP wants to do the conversion on an 8 bit AVR.  Int comparisons are expensive.
What I didn't see mentioned was the range of values that needed conversion.

[IanB]

What I didn't see mentioned was the range of values that needed conversion.

Four digits, from 0000 to 9999.

[Someone]

- how much space does your solution take up?
Well it has lots of int comparisons and int assignments.  All of which are single cycle on most machines.

Comparison might be single cycle, but conditional branching is most certainly not!

[rstofer]

What I didn't see mentioned was the range of values that needed conversion.

Four digits, from 0000 to 9999.

So the data is stored in two bytes...  That's regrettable because even the shift algorithm gets ugly.  I would still try to work with the shift algorithm I posted in Reply 4.  Shifts are still faster than multiply and divide and probably faster than repeated add/subtract.

I wonder if the data should have been carried in BCD from the beginning.  That may not apply here but I have done it in the past.  In fact, the 8080/z80 have a DAA (Decimal Adjust Accumulator) for this very reason.  I have seen code (just now) to implement a DAA subroutine on the AVR.  I don't know if it will help.

[hamster_nz]

If you wanted to do cascaded 'if's (which is somewhat silly, but maybe you are loop adverse) at least do it like this:

Code: [Select]

   d2 = d1 = d0 = '0';

   /* Hundreds */
   if(val > 500) {
     val -= 500;
     d2 += 5;
  }
   if(val > 200) {
     val -= 200;
     d2 += 2;
  }
   if(val > 200) {
     val -= 200;
     d2 += 2;
  }
   if(val > 100) {
     val -= 100;
     d2++;
  }

  /* Tens */
   if(val > 50) {
     val -= 50;
     d1 += 5;
  }
   if(val > 20) {
     val -= 20;
     d1 += 2;
  }
   if(val > 20) {
     val -= 20;
     d1 += 2;
  }
   if(val > 10) {
     val -= 10;
     d1 ++;
  }

  /* Units */
  d0 += val;

It should actually be quicker than looping code like this:

Code: [Select]

   d2 = d1 = d0 = '0';

   while(val > 100) {
     val -= 100;
     d2++;
  }
   while(val > 10) {
     val -= 10;
     d1 ++;
  }
  d0 += val;

But maybe 3x the code size.

The cascaded 'if's has an advantage that it gives predictable results with over-range values too...

[Someone]

There are good examples here:
http://www.avrfreaks.net/forum/smallest-and-fastest-binary-bcd-conversion?page=all