poser@csli.Stanford.EDU (Bill Poser) (07/24/89)
One way to put an integer into a character string is to use sprintf(3),
e.g.: sprintf(string,"%d",foo);
If you are doing a lot of conversions it may be worthwhile to
use a special-purpose function.
/*
* This is a fast subroutine for converting a binary
* integer into a decimal ASCII string. It is very much
* like the itoa routine described on p.60 of K&R, but differs
* from it in several respects. One is the order of arguments.
* The name of the string in which to write is given first in order
* to be consistent with sprintf and kindred functions.
*
* The other differences are intended to speed up the function.
* These include:
*
* Use of registers for frequently accessed variables.
*
* Use of a divide, two shifts, an add and a subtract in place of a
* divide and a C modulus operation. Interestingly, on this machine
* replacing the modulus with a multiplication and a subtraction only
* cut the time a little, but replacing the multiplication with
* two shifts and an add cut the time substantially. This optimization
* should work on other machines using the MC68020 processor. Your
* mileage may vary on machines using processors whose relative
* instruction times are different.
*
* Use of pointer arithmetic rather than array indexing.
*
* Inline code for reversal of the string (which is generated backwards).
* This not only eliminates the function call overhead, but it also
* eliminates the need to detect the end of the string using strlen
* since we know its location already.
*
* Using itoa(s,n) is almost 20 % faster than using sprintf(s,"%d",n).
* Testing on conversions of the 1e6 integers from -500000 to 499999
* on an unloaded HP 9000/350 showed an average of 53.2 microseconds
* per conversion for sprintf() and 43.8 microseconds per conversion
* for this implementation of itoa. (Figures are after subtraction
* of test loop overhead of 1.1 seconds.)
*
* Author: William J. Poser (Department of Linguistics, Stanford U.)
*
*/
void
itoa(string,k)
char *string; /* String in which to write */
int k; /* Integer to convert */
{
register int temp;
register char *s;
register char *p;
register int n;
register int q;
register int r;
int sign;
n = k; /* Copy integer into register */
p = s = string; /* Copy pointer into registers */
if( (sign = n) < 0) n = -n; /* Make n positive */
/* Do conversion */
do {
q = n / 10;
r = (q << 3) + (q << 1); /* Multiply by 10 (8x + 2x = 10x) */
*s++ = n + '0' - r;
} while (( n = q) > 0);
if(sign < 0) *s++ = '-'; /* If negative, add sign */
*s = '\0'; /* Null terminate string */
s--; /* Point s at last non-null char */
/*
* Now we reverse the string. When we begin, p points at the first
* character of the string, s at the last non-null character.
*/
while(p < s){
temp = *p;
*p++ = *s;
*s-- = temp;
}
return;
}chris@mimsy.UUCP (Chris Torek) (07/24/89)
In article <9813@csli.Stanford.EDU> poser@csli.Stanford.EDU (Bill Poser) writes: >One way to put an integer into a character string is to use sprintf(3), >e.g.: sprintf(string,"%d",foo); >If you are doing a lot of conversions it may be worthwhile to >use a special-purpose function. First, however, make sure that the special-purpose function is both needed and correct! [many bits of code deleted below] >int k; /* Integer to convert */ > register int n; > int sign; > n = k; /* Copy integer into register */ > if( (sign = n) < 0) n = -n; /* Make n positive */ If ints are 16 bits wide and represented in two's complement, the routine will not produce the right answer for -32768. If ints are 32 bits wide, the troublesome number will be -2 147 483 648. > /* Do conversion */ > do { > q = n / 10; > r = (q << 3) + (q << 1); /* Multiply by 10 (8x + 2x = 10x) */ > *s++ = n + '0' - r; > } while (( n = q) > 0); If you really need speed, use a binary search to find the range (unless the range is known to be clustered), then use bits of in-line code to convert from binary to BCD or equivalent. Unfortunately, this requires knowing the range represented by integers. You will also have to include a special case for the most negative integer, or use unsigned integers; on some machines, unsigned comparisons are slower than signed, and on others the reverse is true. This sort of thing is generally best left hidden.... -- In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163) Domain: chris@mimsy.umd.edu Path: uunet!mimsy!chris
poser@csli.Stanford.EDU (Bill Poser) (07/24/89)
It is correct that the routine I posted doesn't do the right thing on the most negative integer. That requires a special case, which I left out. Chris Torek is correct that a binary search will speed it up even more, but as he says that means knowing the range of integers on the machine, which reduces portability. The simplest and most portable way (across environments where sprintf is available) to do this is to use sprintf, the fastest and least portable is to write an assembly language routine that takes advantage of the machine's instruction set and knowledge of the size of integers. The routine I provided is the middle ground - it gives a speed advantage over sprintf (at least on certain common processors) but remains pretty portable. I think Chris is being cranky about the need for the routine. I began with the most straightforward solution (sprintf), gave a routine that shows how the conversion is done, and was explicit about the magnitude of its speed advantage and how it might vary. What more can you ask for?
ark@alice.UUCP (Andrew Koenig) (07/25/89)
In article <9814@csli.Stanford.EDU>, poser@csli.Stanford.EDU (Bill Poser) writes: > It is correct that the routine I posted doesn't do the right thing on the > most negative integer. That requires a special case, which I left out. It is possible to do it without special cases, at least for a very wide range of machines. For example, every machine I've ever seen allows you to flip the sign of the most positive integer without overflow. This suggests using negative numbers for all your intermediate results. If you do that, be careful to defend against machines that round toward -infinity rather than toward zero when doing integer division. -- --Andrew Koenig ark@europa.att.com