itoa'd you so?

Dave Smith dave at thesmithfam.org
Fri Sep 21 14:59:05 MDT 2007


Steve wrote:
> Since the sprintf function is slowing down on the log10 due to
> floating point arithmetic, I wonder if a further optimization could be
> made by rewriting the log10 function in assembler to take advantage of
> the floating point registers?
>   

I found that writing an integer-based log10 function sped up my itoa 
function considerably. I don't think you could do anything faster in 
ASM, especially since floating point math is not strictly required anyway.

Anyway, I revised my implementation today to not *need* a log10 function 
by writing the ascii value into the *end* of the buffer, right-to-left, 
least-significant to most-significant, and then it returns a pointer to 
the beginning of the ascii string it creates. That way, I didn't need to 
calculate the length of the string up front (or ever), and it cut my 
runtime in half.

I did, however, find another special case (in addition to zero), and 
that is INT_MIN. If you can figure out why INT_MIN is a special case, 
you get bonus Plug Karma points. The answer lies in the result of the 
following C expression:

    abs( INT_MIN ); // What does this return? :)

    (Note: you'll need to include <limits.h> and <stdlib.h>)

I found this special case by running 2^32 test cases for every 32 bit 
integer, and 48 minutes later, it reported that it passes (ie, returns 
the same as sprintf()) for all 2^32 values. Also, my code performed 
about 3.3 million itoa()'s per second. Not too shabby. :)

I wonder how Java would do, and Qt's QString::number() for that matter.

--Dave



More information about the PLUG mailing list