itoa in pure C

[pete]

I wrote a version of itoa yesterday.

Features:
1 No implementation defined arithmetic. All of the division
and modulus division is done on positive values only.
2 No object is assumed capable of representing the
magnitude of INT_MIN.
3 The string is constructed in place without reversal.
4 No features from standard library are used.

sput_i writes the decimal representation of a nonnegative int value
argument to an array of char.
sput_ip1 writes the representation of one greater than the
argument value, for any nonnegative int value argument, to an
array of char.

/* BEGIN itoa.c */

void itoa(int, char *);
char *sput_i(int, char *);
char *sput_ip1(int, char *);

void itoa(int integer, char *string)
{
if (0 > integer) {
++integer;
*string++ = '-';
*sput_ip1(-integer, string) = '\0';
} else {
*sput_i(integer , string) = '\0';
}
}

char *sput_i(int integer, char *string)
{
if (integer / 10 != 0) {
string = sput_i(integer / 10, string);
}
*string++ = (char)('0' + integer % 10);
return string;
}

char *sput_ip1(int integer, char *string)
{
int digit;

digit = (integer % 10 + 1) % 10;
if (integer / 10 != 0) {
string = (digit == 0 ? sput_ip1 : sput_i)(integer / 10, string);
*string++ = (char)('0' + digit);
} else {
if (digit == 0) {
*string++ = '1';
}
*string++ = (char)('0' + digit);
}
return string;
}

/* END itoa.c */

--
pete

[CBFalconer]

pete wrote:

Dan Pop wrote:

.... snip ...

just treat INT_MIN as a special case: set a flag
and handle it as INT_MIN + 1. If the flag is set, increment the least
significant digit of the result.
No need to worry about carry propagation
because no power of two has 0 as its least significant digit.
void ito_a(int i, char *s)
{
char c, *p;
int int_min = 0;

p = s;
if (0 > i) {
*p++ = '-';
++s;
if (i == INT_MIN) {
int_min = 1;
i = INT_MAX;
} else {
i = -i;
}
}

Try a simpler method (untested in C).

if (0 > i) sign = '-';
else {
i = -i;
sign = '\0';
}
p = s;
/* Now sign has been recorded, and i is negative */
/* Only the first digit is critical, after that the range */
/* of i will easily be within that of a positive int */
do {
c = i % 10; /* this step requires careful std reading */
/* about modulus of -ve numbers. Check it */
*p++ = c + '0'; /* which may require adding 10 here */
i /= 10;
} while (i);
if (*p++ = sign) *p++ = '\0';
--p;
/* Now reverse the string s through p in place */
while (s < --p) {
c = *s;
*s++ = *p;
*p = c;
}

There may be an evil gotcha in the above, because something about
modulo changed between C89 and C99.

do {
*p++ = (char)('0' + i % 10);
i /= 10;
} while (i);
if (int_min) {
++*s;
}
for (*p = '\0'; --p > s; ++s) {
c = *s;
*s = *p;
*p = c;
}
}

--
Chuck F (cb********@yah oo.com) (cb********@wor ldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home .att.net> USE worldnet address!

[pete]

pete wrote:

Peter Nilsson wrote:

What are your thoughts on...?

char *itoa(int i, char *s)
{
char *p = s;
char *q = s;

if (i >= 0)
{
do
{
*q++ = '0' + (i % 10);
}
while (i /= 10);
}
else if (-1 % 2 < 0)
{
This is the part of the code that runs on my machine.
I believe that here, (-1 % 10 == -1) and (-1 / 10 == 0) are true.
*q++ = '-';
p++;

do
{
*q++ = '0' - i % 10;
}
while (i /= 10);
I'm thinking about converting -1.
'0' - i % 10 is '1', so that looks good.
}
else
{
This code is unreachable on my machine,
so all I can do is to think about it.
*q++ = '-';
p++;

do
{
int d = i % 10;
i = i / 10;
if (d) { i++; d = 10 - d; }
*q++ = '0' + d;
}
I'm thinking about converting -1 again.
I think that in the above loop,
(-1 % 10 == 1) and (-1 / 10 == -2) are true.
I see why i++ is there, but I think that the value of
int d = i % 10;
is correct and should not be altered as in d = 10 - d;
while (i);
}

for (*q = 0; p < --q; p++)
{
char c = *p;
*p = *q;
*q = c;
}

return s;
}

At first glance, it seems to be efficient and thorough.
I'll take a closer look at it.

--
pete

[pete]

pete wrote:

pete wrote:

Peter Nilsson wrote:

What are your thoughts on...?

char *itoa(int i, char *s)
{
char *p = s;
char *q = s;

if (i >= 0)
{
do
{
*q++ = '0' + (i % 10);
}
while (i /= 10);
}
else if (-1 % 2 < 0)
{
This is the part of the code that runs on my machine.
I believe that here, (-1 % 10 == -1) and (-1 / 10 == 0) are true.

/* (a/b)*b + a%b shall equal a */

(-1 / 10 == 0, 0) * 10 + (-1 % 10 == -1, -1) == -1

*q++ = '-';
p++;

do
{
*q++ = '0' - i % 10;
}
while (i /= 10);
I'm thinking about converting -1.
'0' - i % 10 is '1', so that looks good.
}
else
{
This code is unreachable on my machine,
so all I can do is to think about it.
*q++ = '-';
p++;

do
{
int d = i % 10;
i = i / 10;
if (d) { i++; d = 10 - d; }
*q++ = '0' + d;
}
I'm thinking about converting -1 again.
I think that in the above loop,
(-1 % 10 == 1) and (-1 / 10 == -2) are true.

I can't make , "(a/b)*b + a%b shall equal a "
hold for those numbers, so I think I'm wrong.
I see why i++ is there, but I think that the value of
int d = i % 10;
is correct and should not be altered as in d = 10 - d;

Is this what you're using ?
(-1 / 10 == -1) (-1 % 10 == 9)
That would explain
d = 10 - d;
but not
i++;

while (i);
}

for (*q = 0; p < --q; p++)
{
char c = *p;
*p = *q;
*q = c;
}

return s;
}

At first glance, it seems to be efficient and thorough.
I'll take a closer look at it.

--
pete

[pete]

pete wrote:

pete wrote:

pete wrote:

Peter Nilsson wrote:

> What are your thoughts on...?
>
> char *itoa(int i, char *s)
> {
> char *p = s;
> char *q = s;
>
> if (i >= 0)
> {
> do
> {
> *q++ = '0' + (i % 10);
> }
> while (i /= 10);
> }
> else if (-1 % 2 < 0)
> {

This is the part of the code that runs on my machine.
I believe that here, (-1 % 10 == -1) and (-1 / 10 == 0) are true.

/* (a/b)*b + a%b shall equal a */

(-1 / 10 == 0, 0) * 10 + (-1 % 10 == -1, -1) == -1

> *q++ = '-';
> p++;
>
> do
> {
> *q++ = '0' - i % 10;
> }
> while (i /= 10);

I'm thinking about converting -1.
'0' - i % 10 is '1', so that looks good.

> }
> else
> {

This code is unreachable on my machine,
so all I can do is to think about it.

> *q++ = '-';
> p++;
>
> do
> {
> int d = i % 10;
> i = i / 10;
> if (d) { i++; d = 10 - d; }
> *q++ = '0' + d;
> }

I'm thinking about converting -1 again.
I think that in the above loop,
(-1 % 10 == 1) and (-1 / 10 == -2) are true.

I can't make , "(a/b)*b + a%b shall equal a "
hold for those numbers, so I think I'm wrong.

I see why i++ is there, but I think that the value of
int d = i % 10;
is correct and should not be altered as in d = 10 - d;

Is this what you're using ?
(-1 / 10 == -1) (-1 % 10 == 9)
That would explain
d = 10 - d;
but not
i++;

Actually it does explain i++;

--
pete

[Peter Nilsson]

"pete" <pf*****@mindsp ring.com> wrote in message
news:40******** ***@mindspring. com...

pete wrote:

pete wrote: ....

I'm thinking about converting -1 again.
I think that in the above loop,
(-1 % 10 == 1) and (-1 / 10 == -2) are true.

I can't make , "(a/b)*b + a%b shall equal a "
hold for those numbers, so I think I'm wrong.
-1/10 => -0.1, so the integer division can be 0 or -1.

I see why i++ is there, but I think that the value of
int d = i % 10;
is correct and should not be altered as in d = 10 - d;

Is this what you're using ?
(-1 / 10 == -1) (-1 % 10 == 9)
Yes.
That would explain
d = 10 - d;
but not
i++;

Actually it does explain i++;

C89 supports no less than 8 different forms of integer division[*]. But I've
only ever seen two: rounding towards zero, and the mathematical non-negative
remainder version.

You can actually test all of the different versions, simply by adjusting the
results of the existing division. [That's how I tested my code; I replaced
the % and / calculations with some function macros.]
[*] there are three possible ways for at least one of two operands to be
negative, and there are two possible division results for each case.

--
Peter

[pete]

Peter Nilsson wrote:

"pete" <pf*****@mindsp ring.com> wrote in message
news:40******** ***@mindspring. com...

pete wrote:

pete wrote: ... > I'm thinking about converting -1 again.
> I think that in the above loop,
> (-1 % 10 == 1) and (-1 / 10 == -2) are true.

I can't make , "(a/b)*b + a%b shall equal a "
hold for those numbers, so I think I'm wrong.
-1/10 => -0.1, so the integer division can be 0 or -1.
I see why i++ is there, but I think that the value of
> int d = i % 10;
> is correct and should not be altered as in d = 10 - d;

Is this what you're using ?
(-1 / 10 == -1) (-1 % 10 == 9)
Yes.
That would explain
d = 10 - d;
but not
i++;

Actually it does explain i++;

C89 supports no less than 8 different forms of integer division[*].
But I've only ever seen two: rounding towards zero, and the
mathematical non-negative remainder version.

You can actually test all of the different versions,
simply by adjusting the
results of the existing division.
[That's how I tested my code; I replaced
the % and / calculations with some function macros.]

[*] there are three possible ways for at least one of two operands
to be negative,
and there are two possible division results for each case.

You get my vote for
"most efficient library independant itoa alogorithm".

--
pete

[Dave Thompson]

On Thu, 29 Jan 2004 19:13:19 -0500 (EST), "Arthur J. O'Dwyer"
<aj*@nospam.and rew.cmu.edu> wrote:

On Thu, 29 Jan 2004, Larry Doolittle wrote:

[pete wrote:]

Can't do it if UINT_MAX == 65535, and INT_MIN == -65536.

<snip> #if -(INT_MIN)>UINT_ MAX

Huh? On a "normal" two's-complement machine, this would produce
undefined behavior when you tried to negate INT_MIN. "Fixing" the
code to read

#if (0u - INT_MIN) > UINT_MAX

just makes it sillier: the left-hand side evaluates to some unsigned
int, which by definition cannot be greater than UINT_MAX. <snip>

Not by definition; preprocessor arithmetic is done in u/long in C89,
and u/intmax_t in C99. But it is still *possible* that the largest
unsigned type cannot handle the full range of signed INT etc., so on
an absolute-maximum-portability quest you still have the problem.

- David.Thompson1 at worldnet.att.ne t

[Dan Pop]

In <vc************ *************** *****@4ax.com> Dave Thompson <da************ *@worldnet.att. net> writes:

Not by definition; preprocessor arithmetic is done in u/long in C89,
and u/intmax_t in C99. But it is still *possible* that the largest
unsigned type cannot handle the full range of signed INT etc.,

^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^
It's not only possible, it's a *certitude*.

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de

[Dave Thompson]

On 6 Feb 2004 19:29:42 GMT, Da*****@cern.ch (Dan Pop) wrote:

In <vc************ *************** *****@4ax.com> Dave Thompson <da************ *@worldnet.att. net> writes:

Not by definition; preprocessor arithmetic is done in u/long in C89,
and u/intmax_t in C99. But it is still *possible* that the largest
unsigned type cannot handle the full range of signed INT etc.,

^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^
It's not only possible, it's a *certitude*.

Sorry, sloppy wording. I meant can't handle the magnitudes of the full
negative range, and in particular of the 2sC most negative value,
which was the issue upthread.

Nit: a thing that is necessarily or always so, like what you marked,
is a "certainty" . "Certitude" is (and "certainty" is *also*) the
property of a person being confident of something.

- David.Thompson1 at worldnet.att.ne t

[Dan Pop]

In <b7************ *************** *****@4ax.com> Dave Thompson <da************ *@worldnet.att. net> writes:

On 6 Feb 2004 19:29:42 GMT, Da*****@cern.ch (Dan Pop) wrote:

In <vc************ *************** *****@4ax.com> Dave Thompson <da************ *@worldnet.att. net> writes:

>Not by definition; preprocessor arithmetic is done in u/long in C89,
>and u/intmax_t in C99. But it is still *possible* that the largest
>unsigned type cannot handle the full range of signed INT etc., ^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^
It's not only possible, it's a *certitude*.

Sorry, sloppy wording. I meant can't handle the magnitudes of the full
negative range, and in particular of the 2sC most negative value,
which was the issue upthread.

Unsigned types cannot handle any single bit of the negative range, by
definition.
Nit: a thing that is necessarily or always so, like what you marked,
is a "certainty" . "Certitude" is (and "certainty" is *also*) the
property of a person being confident of something.

Thanks,
Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de