Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
Solved

# Convert integers to ascii without division

Posted on 2003-03-23
Medium Priority
482 Views
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
Question by:cjs2895

LVL 30

Expert Comment

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

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

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

LVL 1

Author Comment

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

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

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

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

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

LVL 8

Expert Comment

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

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

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

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â€¦
This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see soâ€¦
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.
The goal of this video is to provide viewers with basic examples to understand opening and reading files in the C programming language.
###### Suggested Courses
Course of the Month11 days, 8 hours left to enroll