?
Solved

Convert integers to ascii without division

Posted on 2003-03-23
11
Medium Priority
?
454 Views
Last Modified: 2008-01-09
I suspect this will be an easy question for anyone who has ever done embedded systems programming. I'm looking for interesting methods for converting integers to ascii strings -- other then the usual mod/div method. I have found one reference to a lookup table method in an old Usenet posting, however that reference included neither the table nor a method for generating one. I'd be most interested in seeing a method that worked for different integer sizes.

If there is a name for a technique or algorithm that does what I've described and yields some results when I look it up in Google, I'll give points for that.
0
Comment
Question by:cjs2895
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
11 Comments
 
LVL 30

Expert Comment

by:Mayank S
ID: 8193273
You want to convert integers to ascii strings. Why don't you use the itoa () function?

char str[10] ;
int val = 12345 ;

itoa ( val, str, 10 ) ; // base 10

'str' will now store the value "12345". I hope this is what you want. if not, then please specify..

Mayank.
0
 
LVL 8

Expert Comment

by:akshayxx
ID: 8193293
mayank:
itoa also uses  divison/mod strategy,
the questioner wants alternative algorithms for the integer to string conversion "problem"

cjs2895:
i would still say that divison/mod strategy is pretty fast, at least i havent seen anything more efficient.

if you look at the following code , you will feel that its difficult to get anything more efficient than this.

(if you know the number of digits then it can be made faster.)

itoa(i, a)
register int i;
register char *a;
{
register char *j;
charb[6];

if (i < 0)
{
*a++ = '-';
i = -i;
}
j = &b[5];
*j-- = 0;
do
{
*j-- = i % 10 + '0';
i /= 10;
} while (i);
do
{
*a++ = *++j;
} while (*j);
return (0);
}
0
 
LVL 8

Expert Comment

by:akshayxx
ID: 8193389
here is a hint,
first convert the integer to BCD( binary coded decimal), hopefully without using divison/mod , using only shifts,

then take the BCD bits and now its easy to fill up the string, taking 4 at a time
0
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

 
LVL 1

Author Comment

by:cjs2895
ID: 8193390
akshayxx,

That is a perfect itoa function, but its still mod/div based. As I wrote above, what I'm really after is an algorithm that doesn't require an explicit division or modulus to function. Something along the lines of a table based method, or some fancy bitops to divide by ten and calculate the remainder. Its purely a matter of intellectual curiosity, I'm not trying to optimise for speed.

0
 
LVL 8

Expert Comment

by:akshayxx
ID: 8193417
ok based on above hint .. u shud proceed like this,

define a MASK = 0x0000000f ( 4 byte integer with last 4 bits up)

using this mask .. in a for/while loop,
 take last four bits at a time , ( that will be in the range 0-15) ,
then u can calculate the decimal digit for this HEX number, and keep the carry over for next loop
(u'll do 4-bit number - 9 )

shift the original number with 4 bits
then proceed with next iteration of the loop.

continue till the sum of carryover and 4bit number is non-zero.

also u'll need to take into consideration, the SIGN bit,

 u shud first detect the sign bit and unset it( make it 0 to make the original number positive)  before proceeding the 4-bit-stripping.
0
 
LVL 8

Expert Comment

by:akshayxx
ID: 8193421
i hope u are not looking for ready-made code , what i described above is a procedure , u can try coding from there and let us know where u r stuck.
0
 
LVL 11

Expert Comment

by:cup
ID: 8193700
If you are using an intel processor, there are always the little used AAA, AAD, AAM and AAS.  If the numbers are kept in ASCII, these will adjust them to ASCII strings after addition, division, multiplication and subtraction respectively.  If you do find a use for these, could you publish them?  I've been looking for a use for these instructions ever since they came out in the early 80s.
0
 
LVL 1

Author Comment

by:cjs2895
ID: 8193716
akshayxx,

That is closer to what I was hoping to see! I think there might be a couple issues with your conversion algorithm -- I may just be tired, but doing the steps in my head I think 1024 would be printed as "800" following the steps you outlined above. However your earlier comment about converting to BCD first may have put me on the track of a good technique! Using Google to research methods for converting integers to BCD, I've happened upon several references to the "Add 3" algorithm. Unfortunately the "Add 3" algorithm doesn't seem to be documented very well on the web. I've found one snippet that says it will convert a 32bit int to BCD using "Add 3", but its written in PIC assembler so it will take a couple days for me to decode what its doing.

For anyone interested, the link is:
http://www.piclist.com/techref/microchip/math/radix/b2bp-32b10d.htm
0
 
LVL 8

Expert Comment

by:akshayxx
ID: 8194083
i shud have specified that the 'carry' that i mentioned will not be handled straight awayy like that,
sorry i just had the idea  and wrote it down as it is , i'll try to refine it to yield the result u need.
also 9 will not be the number to be substracted..
that makes my 'method' nearly all wrong :)
0
 
LVL 22

Accepted Solution

by:
grg99 earned 300 total points
ID: 8195245
It's easy, but depends on the word length.

You just need a table of powers of 10, up to the highest power that will fit into your word size.  For example, for 16-bit numbers:

Pow10:   word  10000D,1000D,100D,10D,0D


Print10:   lea   bx,Pow10     ; get address of table

repp:       mov   cx,[bx]     ; get next power
            jcxz   AllDone    ; end of table

            mov     dx,0      ; total counter

sublp:      sub    ax,cx     ; subtract from highest digit
            jl     Done
             
            inc   dx
            jmp   sublp

Done:       add     ax,cx   ; restore underflow
            add     dx,'0'
            out     screen,al   ; print the digit
            add     bx,2       ; point to next lesser power
              jmp     repp
AllDone:    add    ax, '0'   ; print bottom digit
             out   screen,al


0
 
LVL 1

Author Comment

by:cjs2895
ID: 8198514
grg99,

Very cool! That really works, no division, and it appears to be independent of integer size. Kudos!

Here it is again translated from ASM to C:

unsigned long Pow10[] = {
0x3b9aca00, 0x5f5e100, 0x989680, 0xf4240, 0x186a0, 0x2710, 0x3e8, 0x64, 0xa, 0x0
};

int main(int argc, char **argv) {
  unsigned long ax;
  unsigned long bx;
  unsigned long cx;
  unsigned long dx;

  ax = 1024; /* Value to convert */
  bx = 0;
  out = 0;
  while((cx = Pow10[bx])) {
    dx = 0;
    while(ax > cx) {
      ax -= cx;
      dx++;
    }
    dx += 0x30;
    putchar(dx);
    bx++;
  }
  ax += 0x30;
  putchar(ax);
}
0

Featured Post

What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were small…
Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use for-loops in the C programming language.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.
Suggested Courses

801 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question