itoa'd you so?

Charles Curley charlescurley at charlescurley.com
Fri Sep 21 22:45:22 MDT 2007


On Fri, Sep 21, 2007 at 08:37:11PM -0600, Levi Pearson wrote:
> Charles Curley <charlescurley at charlescurley.com> writes:
> >
> > Have we beaten this thing into the ground yet?
> 
> Not quite yet.  Try this one:

I like it. A few points.

* It is base ten only. My solution is much more general. Need base 36?
  Recall that base 10 was not specified in the original problem. But
  your method can be adapted at the cost of:

  * expanding the lookup table,

  * dividing by a variable instead of an inline constant, usually
    slower.

  Also, your lookup table is probably faster than my calculation.

* You have a call to abs inside your main loop. I think I see why, but
  would you safely speed things up by moving it outside?

* Your reverse function is nice, but probably slower than strcat
  because it uses an intermediate variable. But I think you can speed
  it up considerably by only running for (strlen (s))/2 iterations. If
  so, it probably would be better than my temporary buffer.

  If the compiler will optimize the /2 into a right shift, you get rid
  of a divide instruction. (Or, on most 16 bit processors, a divide
  function.) Or do it yourself with (strlen (s))>>.

* I replaced my while loop with a do ... while loop, and found (to no
  great surprise) that it is slower. I didn't check, but I doubt it
  saved any space because of the way do ... while loops usually
  compile. That did let me get rid of the 0 special case, making
  things more elegant. The same might apply here.

I made a few other optimizations in my version.

* I now initialize i to SIZE and decrement it. This gets rid of a
  subtraction instruction inside the main loop.

* I declared some variables to be register variables. That helps on
  Intel architecture, which is so pathetically register poor. It might
  or might not help on register rich processors because the compiler
  might do it for you.

* I declared the function digit inline. That helped. But it would make
  for a smaller code size only if digit isn't used elsewhere. It could
  be a useful routine for special cases like a hex dump.

--------------------------------------------------

/* We depend on a pure ASCII environment here. */
inline char digit (int d)
{
    register char ret = '0' + d;

    /* For bases greater than 10, skip from '9' to 'A' in the ASCII
     * table. This may have been a trick your examiner was looking
     * for. */
    if (ret > '9') {
        ret += 7;
    }
    return (ret);
}

char *itoa (int value, char *buffer)
{
    register int i = SIZE;

    /* I have no way of knowing the size of the incoming buffer, so I
     * have to build in a buffer, then copy into the given one. strcat
     * is likely more efficient and faster than strncat, and probably
     * coded in assembler. */
    char tmp[SIZE+1];

    tmp[SIZE] = 0;

    /* For negative numbers, set the sign. Having done that, do
     * the conversion as a positive number. */
    if (value < 0) {
        strcat (buffer, "-");
        value = 0 - value;
    }

    do {
        /* Since we are starting at the right end of the string, we
         * fill our temporary buffer from the right. This is likely
         * another trick the examiner wanted. */
        tmp[--i] = digit (value%base);
        value = value/base;
    } while (value);

    strcat (buffer, &tmp[i]);
}
--------------------------------------------------

-- 

Charles Curley                  /"\    ASCII Ribbon Campaign
Looking for fine software       \ /    Respect for open standards
and/or writing?                  X     No HTML/RTF in email
http://www.charlescurley.com    / \    No M$ Word docs in email

Key fingerprint = CE5C 6645 A45A 64E4 94C0  809C FFF6 4C48 4ECD DFDB
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
Url : http://plug.org/pipermail/plug/attachments/20070921/11c63299/attachment.bin 


More information about the PLUG mailing list