itoa replacement ALMOST perfect

[aewarnick]

This code is almost perfect. The only problem occurs (commented in code below). The problem does not occur if T is an int and n is int_min. Little help please. There is a solution to this because ostringstream gets it right.
#define int64_max 9223372036854775807LL
#define int64_min (-int64_max-1)

template <typename T>
aStr IntToStr(T n, uint radix= 10)
{
if(!n)
{
return "0";
}
else
{
bool neg= n < 0;
if(neg)
{
n= -n;
MB(n); //when T is __int64 and n is int64_min, n stays as int64_min!
}
const uint bits= sizeof(T)*8;
char buf[bits];
// Set chars from the end of the buffer
char* ptr= &buf[bits-1];
*ptr= 0; //terminating NULL
while(n > 0)
{
--ptr;
//*ptr= itoaChars[n%radix]; //this works too
*ptr= n%radix+'0';
n /= radix;
}
if(neg)
{
--ptr;
*ptr= '-';
}
return aStr(ptr);
}
}

[Butterfly]

please show the error message

[aewarnick]

There is no error, it just outputs jibberish such as: x*((u)60($

[Paul McKenzie]

This code is almost perfect.No it isn't. See comments below.The only problem occurs (commented in code below). The problem does not occur if T is an int and n is int_min.You should be using the constants defined in <limits.h> and not hard-code minimum and maximum values. Not everyone has a 64-bit machine to test your code on.

What is wrong with just using itoa? Is it for the same (possibly wrong) reason you wanted to code your own gcvt from this thread?

http://www.codeguru.com/forum/showthread.php?t=357633

Quite honestly, I don't look too seriously on code that is supposed to replace standard library functions. Usually the code that is supposed to "replace" the standard library functions is inferior to the standard library code in maintainability, speed, and a whole host of other areas.

Right now, you have a bug, so already you are going uphill when you don't need to. I already pointed out that your code is only for 64-bits. What if you want to take this code to a 32-bit machine? So in reality, you haven't replaced itoa, you are trying to write a limited subset of itoa.

Regards,

Paul McKenzie

[NMTop40]

given that this is C++ (you've used a template) why not use standard libraries?
What is aStr? What is MB?

[aewarnick]

One of the reasons I'm making this code is that itoa is inferior. It only accepts int.

Now that my motive is clear...I am using a 32 bit machine, I don't see where you are getting the idea that the code only works for 64 bit. The code does work perfectly for int32_max, uint32_max, uint64_max, int64_max...all the time. It's only when n is at a negative max value.

When n is -2147483648 and I do this:
n= -n;
the max of int is 2147483647, 2147483648 is too big, so it just remains the same; -2147483648. And that is where the problem is.

[Marc G]

You can always use a stringstream:
std::stringstream ss;
ss << my_int;
Just like Paul McKenzie said, I'm a bit reluctant when it comes to rewrite standard functions...

[aewarnick]

What if I want to use this in a C not C++ library sometime in the future?

Lets look at this from a different angle - You make a convert to absolute value function that works for any integer type; int, int64, int128...

template<typename T>
T Abs(T t)
{
return -t;
}
MB(Abs(int_min)); //output -2147483648 WRONG!
MB(Abs(int_min+1)); //output 2147483647
How would you solve that? Keep in mind that you can't use abs because that function does not accept __int64.

[Paul McKenzie]

What if I want to use this in a C not C++ library sometime in the future?
1) This is a C++ forum.

2) Since you posted a template, it is assumed you are using this in C++, not C. Therefore you will get C++ answers. Next time state up front you are writing this for a C compiler. No one can read minds.

Regards,

Paul McKenzie

[Paul McKenzie]

One of the reasons I'm making this code is that itoa is inferior. It only accepts int.

Now that my motive is clear...I am using a 32 bit machine, I don't see where you are getting the idea that the code only works for 64 bit.

#define int64_max 9223372036854775807LL

This will not compile on a compiler where the maximum int is 32 bits. In other words, your code is highly non-portable.

You never write code assuming these types of limits. You always use the constants defined in limits.h to determine what is the maximum integer supported by the compiler.

Regards,

Paul McKenzie

[Paul McKenzie]

One of the reasons I'm making this code is that itoa is inferior. It only accepts int.Just to add,

The itoa() is a 'C' function that cannot be overloaded. Therefore it can only have one type, and the type that is chosen is int. An "int" is the standard integer type for C++ where the sizeof(int) is compiler dependent. There is no such standard type as int64, __int64, or anything like that. Yes, you've used these types, but all of those are compiler creations and not officially part of the ANSI standard.

So saying that itoa() is inferior is not a fair statement. If your compiler library vendor were smart, there would be functions called itoa_64() or abs_64() or something similar to that if the compiler has 64 bit numbers. I would be highly surprised if the compiler didn't have these functions, given that the compiler has native 64-bit integers.

Regards,

Paul McKenzie

[jlou]

Just wanted to mention that itoa is not standard. Writing a version of it that uses only standard code and is portable is not a bad idea, although I personally just prefer to use a stringstream.

[aewarnick]

I'll start using limits.h. That's a good point. I am using MSVC+ 2002. I can't find 64 bit functions anywhere.

[NMTop40]

I'd use <numeric_limits> myself but then I'm a standard C++ programmer.

[Marc G]

I'll start using limits.h. That's a good point. I am using MSVC+ 2002. I can't find 64 bit functions anywhere.
According to the MSDN, the following functions are available:
_itoa, _i64toa, _ui64toa, _itow, _i64tow, _ui64tow

[aewarnick]

I'll have to check those out.

You know, I'm thinking about the way this whole thing is being done. Specifically this section:

while(n > 0)
{
--ptr;
*ptr= n%radix+'0';
n /= radix;
}

Isn't it possible to get each number by bit manipulation instead? I was thinking about this and printed out the bit values of int types and I'm confused:

int_max: //31 bit is the negative
01111111111111111111111111111111 //2147483647
int_min: //31 bit is the negative
10000000000000000000000000000000 //-2147483648
uint_max:
11111111111111111111111111111111

How is it that int_min is larger than int_max when the bit count that makes the number is the same?

[Bob Davis]

It's an artifact of 2's-complement binary representation of integers. In 32 bits, you have 2^32 possible values. You'd like to split them up evenly between positive and negative numbers, but you have to set one value aside to represent zero. Therefore, you have (2^32) - 1 possible nonzero values that you can represent with 32 bits. Due to how 2's-complement works, it just so happens that 2^31 of these are negative numbers and (2^31) - 1 are positive numbers. Therefore, there is one negative 32-bit number that can not be represented as a positive 32-bit number: 2^31.

[aewarnick]

I tried and tried to understand that but no matter how I look at it, it doesn't make sense.

10000000000000000000000000000000 //-2147483648
11111111111111111111111111111110 //-1 I'm assuming
11111111111111111111111111111100 //-3 I'm assuming
11111111111111111111111111111101 //-2 I'm assuming - what you said above does not make sense because the 0 bit is used in negative numbers, otherwise -2 could not be represented.

[HeartBreakKid]

You're looking at it the wrong way.


-2147483648 (min value)

means 2147483648 NEGATIVE values (staring with -1)



2147483647 (max value)

means 2147483648 POSITIVE values (starting with 0) 0 is NOT negative


Also the following is the wrong assumption:
10000000000000000000000000000000 //-2147483648
11111111111111111111111111111110 //-1 I'm assuming
11111111111111111111111111111100 //-3 I'm assuming
11111111111111111111111111111101 //-2 I'm assuming


10000000000000000000000000000001 // -1
10000000000000000000000000000010 // -2
10000000000000000000000000000011 // -3
11111111111111111111111111111111 //-2147483648

[aewarnick]

Then why does itoa output (radix of 2)
10000000000000000000000000000000 for -2147483648
and
10000000000000000000000000000001 for -2147483647
and
11111111111111111111111111111110 for -2
and
10 for 2
and
1111111111111111111111111111110 for 2147483646

-2 is the one that stumps me:
11111111111111111111111111111110
shouldn't it be:
11111111111111111111111111111101
?

[Bob Davis]

Actually, you're both incorrect.

-1 = 0xFFFFFFFF = 11111111111111111111111111111111
-2 = 0xFFFFFFFE = 11111111111111111111111111111110
... and so on.
-(2^31) = 0x80000000 = 10000000000000000000000000000000

That's just the way it works. Search Google for 2's-complement binary format and you'll find everything there is to know about this topic. To convert a positive number to a negative number, you don't just flip the sign bit. If you did, then it would be possible to have a negative zero, which doesn't make sense.

To negate a 2's-complement number, you negate all of the bits in the number, then add one to the result. That's it. There's no point in wondering why this results in things that seem unnatural to you; that's just the way that (almost) every digital systems designer decided to implement binary integer representation.

[NMTop40]

So if you are programming on Windows use those functions.

If you want your code to be portable in C++ only, you can do something like this:

namespace myNamespace
{

template < typename INT_TYPE, typename CHAR_TYPE >
CHAR_TYPE * myItoA( INT_TYPE value, CHAR_TYPE * param, int radix=10 );

#include myItoAImpl.tpp

}

(I use .tpp for a template implementation that is in a different file from its declaration). You can have different versions of the implementation file, one for uses on Windows that specialises all the types and calls the already-implemented versions. For users on other systems you can implement it when you need to (or call methods supported by those systems).

If you want to make this portable for C then you'd have to provide different functions, for both character types and for different integral types, and there'd be no version for non-portable types. The types that are portable can be implemented with ostringstream and supports different bases too, so your default implementation could use ostringstream.

It would be nicer to be able to return std::string although that has portability issues across libraries too, i.e. you couldn't write such a function and export in a DLL.

[aewarnick]

Is there a reason for 2's-complement binary or is that just to make the designers LOOK smarter?

[Paul McKenzie]

You probably don't come from a computer science background, or taken basic assembly language course in college.

Two's complement binary has been in use for decades. It wasn't just thought up by Microsoft. If you take a computer science course, one of the first things that you're taught is 2's complement binary -- flip bits and add 1 to represent the negative of a number. Flip bits and add 1 again to get the positive number.

It is used for easier basic numeric operations between signed and unsigned numbers.
For example -2 + 1:

-2 = 1110 as 2's complement

so:

1110 + 0001 = 1111 == -1 as a 2's complement number.

Regards,

Paul McKenzie

[aewarnick]

I see. Does Linux also use this same method?

[Paul McKenzie]

I would think that most, if not all binary-based hardware (i.e. computers) use 2's complement to represent negative numbers. It's just a basic computer science fundamental.

Regards,

Paul McKenzie

[marten_range]

Actually 2-complement makes lot of sense:

A property of a number is that if you add to it its negative counterpart the sum becomes zero. IE:
a + (-a) = 0

This should be true for binary numbers as well.

So if we have the following number in binary:

00001110

If we want find the negative value of the binary number above we should solve the equation:

00001110 + X = 00000000

It turns out that the 2-complement is an elegant solution as no special logic is needed in the logical circuits to deal with negative number because if we choose X = 11110010 the equation above becomes (that is X is the 2-complement of 00001110).

00001110 + 11110010 = (1)00000000

(1) is the ninth bit and therefore sliced of for byte artimetics. Taking that into consideration:

00001110 + 11110010 = 00000000

Or perhaps a more formal way of expressing it

00001110 + 11110010 = 00000000 mod 256

Which is what we wanted.

Hopefully that made some sense.

[Paul McKenzie]

Thanks for filling in the gaps, marten_range. I only added just the taste of why 2's complement is used, but you've explained it pretty well.

Regards,

Paul McKenzie

[aewarnick]

This function has now become part of my aStr class that replaces string. My tests have shown that it is alot faster than itoa when radix is 2 and a tiny bit slower than itoa if radix is 10.
Code and Results (http://www.foryouandi.com/Programming/C_Cpp/source.php)

Testing code snippet:
void aStrAssignNumbers()
{
int b= int_min; aStr as;
ResetAndStartTimer("Mine");
for(uint i= 0; i< loops; ++i)
{
as.Assign(b, 10);
}
StopAndLog();
ResetAndStartTimer("itoa");
for(uint i= 0; i< loops; ++i)
{
const uint bits= sizeof(b)*CHAR_BIT;
char c[bits+1]; char* cc= itoa(b, c, 10);
as= cc;
}
StopAndLog();
testInt+= b*b*b+30*b/6;
}

//Above function is called here
else if(&goBut== e.c)
{
::SetThreadPriority(::GetCurrentThread(), THREAD_PRIORITY_TIME_CRITICAL); //THREAD_PRIORITY_HIGHEST THREAD_PRIORITY_ABOVE_NORMAL THREAD_PRIORITY_BELOW_NORMAL THREAD_PRIORITY_IDLE THREAD_PRIORITY_LOWEST THREAD_PRIORITY_NORMAL=0
loops= 0;
loopsEB.Text.ToInt(&loops);
if(!loops)
{
::SetThreadPriority(::GetCurrentThread(), THREAD_PRIORITY_NORMAL);
MB("Invalid entry. Setting to max."); loopsEB.setText(ToStr(int_max).str());
return;
}
aStr s("Loops: "); s= s<< loops;
listBox.AddItem(s); listBox.AddItem("");

aStrAssignNumbers(); listBox.AddItem("");
//Primitives(); listBox.AddItem("");
::SetThreadPriority(::GetCurrentThread(), THREAD_PRIORITY_NORMAL);
DD("");
}
I am using VC++ 2002 building in Release with all optimasations on; /O2.

[Bob Davis]

That's an incomplete example. You haven't shown your aStr class at all. I'm assuming that "as" is an instance of this class. I notice in the itoa() case, you're calling operator= and assigning the character pointer to your object. Your implementation of operator= could be the cause for the measured poor performance in that case. To say anything definitive, we would need to see your whole class, enough that anyone here could compile and run the program. Just as Paul is, I'm very wary of these implementations that "beat" the standard library.

[aewarnick]

In Assign(my Itoa function) I changed this:
Assign(buf, bits);
to
*this= buf;
as a test for you.
And it made my function 1 second slower; bringing it to 4.5 seconds. Not even close to 10.

And I did give you more than enouph code to compile this and test it yourselves. You can easily take that function and return a string. It will require almost no effort.

[Paul McKenzie]

And I did give you more than enouph code to compile this and test it yourselves.You must provide *your* code in a compilable form that we can just copy and paste it in our compiler and test. We still do not know what aStr is. Once we have to guess, make up things, or fill in the gaps with our own code, then the tests become biased and invalid. It will require almost no effort.It should require *no* effort from us, except using the copy and paste function and push the compile button.

Regards,

Paul McKenzie

[Paul McKenzie]

In Assign(my Itoa function) I changed this:
Assign(buf, bits);
to
*this= buf;
as a test for you.
And it made my function 1 second slower; bringing it to 4.5 seconds. Not even close to 10.You also didn't mention whether you compiled this as a release with optimizations turned on or whether you are timing a debug version.

We are trying to believe you, but this sort of dramatic speed increase given that your function is a *full* version of the standard function is very uncommon. It is usually only accomplished by very experienced programmers, and usually only those that are familiar with the code already to know what exactly is slow.

It is not done by persons who happen to put a function together in less than a few hours and "lo and behold", the function is 3 times faster than the standard function. That is just too hard to believe at this point.

If it is the case that you have a function 3 times faster than itoa(), report this to PJ Plauger at DinkumWare, since he is the one that wrote the standard library for Visual C++.

So the real question is this: what makes itoa() slow, if it is slow?

Regards,

Paul McKenzie

[aewarnick]

I whipped it up real quick. So there may be mistakes. But IntToStr seems to be faster most of the time even if radix is 10.
http://foryouandi.com/Programs/index.php

And I did say I build it in Release with /O2 optimizations in the other thread.

[Paul McKenzie]

Compiled on Visual C++ 6.0 (Maximize Speed). I replaced "int64" with just plain old "int".

loops = 10000
itoa 0
-2147483648

IntToStr 0
-2147483648


loops = 100000
itoa 0.032
-2147483648

IntToStr 0.031
-2147483648


loops = 1000000
itoa 0.312
-2147483648

IntToStr 0.25
-2147483648
So far there is an increase, but not three-fold.

Changing your Test() function to the following:

void Test()
{
int b=0;
uint radix=10;
string s;
s.resize(65);
const uint bits= sizeof(b)*CHAR_BIT;
char c[bits+1];
uint i;
ResetAndStartTimer("itoa");
for(i= 0; i<loops; ++i)
{
for ( int j = 0; j < 10000; ++j )
s = itoa(j, c, radix);
}
StopAndLog();
cout << s <<"\n"<<endl;

ResetAndStartTimer("IntToStr");
for(i= 0; i<loops; ++i)
{
for ( int j = 0; j < 10000; ++j )
s = IntToStr(j, c, radix);
}
StopAndLog();
cout << s <<"\n"<<endl;

testInt += b*b*b+30*b/6;
}


loops = 10000
itoa 18.14
9999

IntToStr 15.657
9999

Again not a three fold increase in speed.

The other check which was not made is to see if the answers are correct. You should write the code to verify that your IntToStr() function actually does work by comparing the return result with itoa() with more than one number.

Regards,

Paul McKenzie

[aewarnick]

I did say that with a radix of 2 mine is much much faster. Try it, you'll see.

[Paul McKenzie]

I did say that with a radix of 2 mine is much much faster. Try it, you'll see.The code you have shows a radix of 10, so this is what I tried. However, this brings me back to my point of writing tests that are biased.

Sure, you can take practically any standard function (or class) and write your own version that is optimized for only certain data or conditions. This does not count as a "faster replacement", since it is only fast for one or just a few conditions.

This reminds me --

I remember someone claiming they had a string class faster than std::string, and they only tested it against concatenation of single characters to the string in a loop. The tests that this person wrote were delibrately written to take advantage of the single char concatentation. Yes, the home-made string class was faster when it came to concatenating single characters onto a string, but when the code was tested under general conditions (meaning the test was then written by another party) and with real-life examples, it was a failure and proved to be much slower than std::string.

I did what any other person who really wanted to use your code would do -- and that is to test against all and/or any criteria, and not test it against something that you know it is optimized for. The function takes a radix value, so it is only reasonable to test against different radix values, not just 2.

Regards,

Paul McKenzie

[aewarnick]

I agree. For that very same reason, I set b to int_min because the test is just unfair for me otherwise if radix is 2. I wanted all bits output all the time in binary mode, unlike what itoa does:
int 1;
itoa would output 1.
mine would output 31 zeros, then a 1.

Besides, we have both verified that IntToStr is faster dealing with a radix of 10 and 2 than itoa is.

One thing I did not even try to test was a radix of 16. Don't be surprised if it doesn't work right.

[aewarnick]

http://foryouandi.com/Programs/index.php
Now works perfectly for hex (radix==16) and seems to be just as fast as before. I also changed BOOL to bool. I was under the impression that BOOL was faster but my tests showed it was not. What do you think?

Paul, that is a good idea about checking to see if my function is always outputting correctly. I'll do that tonight and post back...if my wife lets me.

[Paul McKenzie]

One thing I did not even try to test was a radix of 16. Don't be surprised if it doesn't work right.Remember, this is only for one compiler. I have not tested this under any other version of Visual C++, or some other compiler.

All of this depends on how itoa() is implemented for a certain compiler. There is no guideline on how fast or slow this function is supposed to perform or how it is to be implemented. Another compiler vendor may have written itoa() all or most of it in assembly langage (and many C run-time functions are done this way).

Therefore be prepared for varying successes and failures when you run your code on another compiler.

Regards,

Paul McKenzie

[Paul McKenzie]

http://foryouandi.com/Programs/index.php
Now works perfectly for hex (radix==16) and seems to be just as fast as before. I also changed BOOL to bool. I was under the impression that BOOL was faster but my tests showed it was not. What do you think?A bool is an actual C++ type. A BOOL is a macro, and assuming it is defined in windows.h, it is nothing more than an int. Therefore if you want your code to be portable to other compilers, use bool.
Paul, that is a good idea about checking to see if my function is always outputting correctly. I'll do that tonight and post back...if my wife lets me.If any step can bring the whole thing down like a house of cards, it's this one, and that is testing to see if the output is correct.

Regards,

Paul McKenzie

[NMTop40]

That intToStr is faster in the profile test could come about simply because the compiler is able to optimise the call of a local function more than one through a library. It may even be inlining it.

Put intToStr in a DLL and call it that way for a fairer test.

[aewarnick]

Can't you just look at the assembly output? And is it common that dll functions are slower because they're in a dll?

I thought I would keep everyone updated as to where i'm at. I am testing my IntToStr function and comparing the output with itoa's output. So far, with a radix of 10 and 16 everything is the same. I had this running all night. My first test is from 1 to int_max. My second test will be the same except from int_min.

For the first test, again, has been running ALL NIGHT! I didn't realize how big int_max was. I'm currently around:
50000000
int_max is around:
2000000000

How big is 2000000000 anyway? Is that 2 gig?

[Paul McKenzie]

Can't you just look at the assembly output? And is it common that dll functions are slower because they're in a dll?Yes, it will be slower. The compiler can optimize the code globally, i.e. may make the function inline.

For the DLL function, there is no way the compiler can inline this function, since there is no way for it to optimize calling it (it's already compiled, and in an external module). So basically the compiler has to go with the "push arguments" and "call" set of operations when calling the DLL function, while your function benefited from the compiler's optimizer, eliminating these steps.

As a matter of fact, I did look at the assembly output. Your function generated no calls to "push arguments" and then "call", while the DLL function call must do this.

So NMTop40 is correct. Place your version of itoa() in a DLL, and then test. Then there is no optimization or any other things that the compiler may do to take advantage of code that is written inline.

Regards,

Paul McKenzie

[aewarnick]

I didn't make the dll yet, however, I did upload a new version of the program and source. Found a really stupid mistake that only occured when the int is at a minimum max value.

I also put the test function in the source to check if IntToStr is outputting correctly all the time. I am doing the positive numbers now and it may take days to finish just the positive. Maybe to save time, someone else could do the negative and report back.

http://foryouandi.com/Programs/index.php

[aewarnick]

IntToStr in dll:
http://foryouandi.com/Programs/index.php

I didn't see a difference.

[aewarnick]

After looking at my code I realized that it was taking so long to test if every number output from IntToStr correctly because I was redrawing the window for every number. I changed that and now the test completes in about an hour on my computer.

You'll be happy to know that every integer output exacly as itoa does. The only thing that does not is negative hex. I'll work on that.

Did anyone else test the dll version yet to see if IntToStr is faster than itoa on your computer?

[aewarnick]

My function is slower when working with 64 bit integers than _i64toa is. So I removed some parts of the code and put it in it's own function to show that the bottle neck is. Removing the parts I removed below doesn't really speed the function up at all so that bottleneck is obvious. Take a look.
char* IntToStr(int64 n, char* buf, uint radix= 10)
{
if(!n)
{
return "0";
}
static const uint bitCount= 64;
char* ptr= buf+bitCount;
*ptr= 0; //Terminating NULL
/*if(radix == 2)
{
int64 bitPos= 1;
for(register uint i= 0; i < bitCount; ++i)
{
--ptr; *ptr= (n & bitPos) ? '1' : '0'; bitPos= bitPos << 1;
}
return buf;
}
bool neg= n < 0; bool negMax= 0;
if(neg)
{
n= -n;
if(n < 0)
{
negMax= 1;
n= ~n; //make posotive max
}
}
if(radix == 16) //hex
{
static const char* itoaChars= "0123456789abcdefghijklmnopqrstuvwxyz";
while(n > 0)
{
--ptr;
*ptr= itoaChars[n%radix];
n /= radix;
}
}
else*/
{
while(n > 0) //bottleneck here! Speed up for 64 bit
{
--ptr;
*ptr= n%radix+'0';
n /= radix;
}
}
/*if(neg)
{
--ptr;
*ptr= '-';
}
if(negMax && radix == 10)
{
char* ptr2= buf+(bitCount-1);
while(*ptr2 == '9')
{
*ptr2= '0';
--ptr2;
}
if(*ptr2 == '7') *ptr2= '8';
else if(*ptr2 == '0') *ptr2= '1';
else if(*ptr2 == '1') *ptr2= '2';
else if(*ptr2 == '2') *ptr2= '3';
else if(*ptr2 == '3') *ptr2= '4';
else if(*ptr2 == '4') *ptr2= '5';
else if(*ptr2 == '5') *ptr2= '6';
else if(*ptr2 == '6') *ptr2= '7';
else if(*ptr2 == '8') *ptr2= '9';
}*/
return ptr;
}
Any ideas on how to optimize this function for 64 bit?

I uploaded a new program so that you can see for yourselves if 64 bit is slower on your computer. Just change testWith64 to 1.

http://foryouandi.com/Programs/index.php

[Paul McKenzie]

You need to get a code profiler so that you know where the slowdown is actually taking place instead of making guesses.

Regards,

Paul McKenzie