asked on

Convert integers to ascii without division

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.

Mayank S

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.

akshayxx

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);
}

akshayxx

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

cjs2895

ASKER

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.

akshayxx

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.

akshayxx

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.

cup

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.

cjs2895

ASKER

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

akshayxx

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 :)

ASKER CERTIFIED SOLUTION

grg99

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial

cjs2895

ASKER

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);
}