Testpad for itoa()

[frktons]

The previous thread is getting too complex to manage, so I prefer
to start a new one with a clean start.

Attached is the testpad you can use to test your version of itoa() with
thousand separator and sign.

The program is written in standard ANSI C99, so you can compile and test
it on your machines.

When you have a working example to post, insert your itoa() version on the
testpad, post it and the results you get, if you like.

The output is something like:

                    Testing version : iMalc
                 ------------------------------
 Testing on Intel Core Duo 6600 2.4 Ghz
 OS = Windows 7 Ultimate 64 bit  --  Compiler = Pelles C 6.00.4

 The value of num is: -1234567890

 The formatted value of num is: -1,234,567,890

 Elapsed ClickTime: 296 to perform 10,000,000 cycles
 -------------------------------------------------------

 handling 0 ---> 0
 handling 12 ---> 12
 handling 256 ---> 256
 handling 1000 --> 1,000
 handling 1000000 ---> 1,000,000
 handling 1000000000 ---> 1,000,000,000
 handling 2147483647 -> 2,147,483,647
 handling -2147483648 -> -2,147,483,648

After we have a few correct versions to test, we can
perform the next test with random numbers to have a real
idea of the performance.

Bye for now

[Elysia]

You realize that there is no ANSI C99, right? There is only ISO C99 with respect to that standard.
My code (which hasn't changed since last):

                    Testing version : Elysia
                 ------------------------------
 Testing on AMD Athlon II X2 250 (3 GHz)
 OS = Windows 7 Ultimate 64 bit  --  Compiler = Microsoft Visual Studio 2010

 The value of num is: -1234567890

 The formatted value of num is: -001,234,567,890

 Elapsed ClickTime: 000,207 to perform 000,010,000,000 cycles
 -------------------------------------------------------

 handling 0 ---> 0
 handling 12 ---> 000,012
 handling 256 ---> 000,256
 handling 1000 --> 001,000
 handling 1000000 ---> 000,001,000,000
 handling 1000000000 ---> 001,000,000,000
 handling 2147483647 -> 002,147,483,647
 handling -2147483648 -> -002,147,483,648

Minor tweaks to your code, too. Remember that string literals are const!

[quzah]

He probably means something like:

gcc -o foo foo.c -std=c99 -Wall -pedantic


Quzah.

[whiteflags]

Umm, what about what iMalc has said, frktons:

There's still the possibility of using multiplicative inverses for div/mod by ten for some of the above, but other than that probably the only faster option is hand-rolled assembly.

You can click the blue arrow and see his particular implementation that he talks about here, before he made the optimization in your testpad.c file. The optimization that turned out not-so-optimized:

I take it back. My last version was a waste of time. Compilers already perform the same optimisation trick, except that they are able to do it using the high 32-bit part of a 64 bit result from multiplication of two 32-bit numbers. This means that they can do the same tricks themselves, but more efficiently.
See here: ridiculous_fish » Blog Archive » Labor of Division (Episode 1)

I think you've reached a plateau, so like, the only things to do are make sure iMalc's version is correct, and you know that it is, apparently. So, what to make this thread about? Did you want a function remotely C like?

[cyberfish]

In decreasing order of importance:

1. You really should use random numbers. You can even compare all answers with reference answers (from a slow, known correct implementation) if you want. This is a more systematic testing method.
2. itoa is a bad name. Some compilers have a function named itoa I believe.
3. You may want to pass the length of the buffer, along with the buffer, to the function, since the function has no way of finding that out. You can't just guarantee it will be larger than the longest answer either, since some implementations may use the buffer as scratch pad, and do clever things with it.
4. clock() measures different things on different platforms. For example, I don't remember which is which, but GCC's clock() measures CPU time on one platform, and wall time on another (Linux/Windows). They are only the same if the program takes 100% CPU all the time, and is the only process executing. There is no portable way to do accurate timing, but on Windows you can use GetSystemTimeAsFileTime. The rest of the world has gettimeofday.

[zacs7]

You realize that there is no ANSI C99, right? There is only ISO C99 with respect to that standard.
My code (which hasn't changed since last):

                    Testing version : Elysia
                 ------------------------------
 Testing on AMD Athlon II X2 250 (3 GHz)
 OS = Windows 7 Ultimate 64 bit  --  Compiler = Microsoft Visual Studio 2010

 The value of num is: -1234567890

 The formatted value of num is: -001,234,567,890

 Elapsed ClickTime: 000,207 to perform 000,010,000,000 cycles
 -------------------------------------------------------

 handling 0 ---> 0
 handling 12 ---> 000,012
 handling 256 ---> 000,256
 handling 1000 --> 001,000
 handling 1000000 ---> 000,001,000,000
 handling 1000000000 ---> 001,000,000,000
 handling 2147483647 -> 002,147,483,647
 handling -2147483648 -> -002,147,483,648

Minor tweaks to your code, too. Remember that string literals are const!

You could argue that it's not the same... You don't produce the same output. I would not be happy with "000,012" if I wanted "12".

[Adak]

I made up a testbed program, as well. It has an array of about 50 numbers in total, which include at least one number from each power of 10:

1
12
101
9999
10000
up to 1234567890

and about 1/3rd of them are negative.

Before the timed run, the program (which is made into a function), runs this test. Every number is tested for accuracy with the string generated by the function. Then the timed run begins and these numbers, are chosen randomly for input.

I had to alter iMalc's first program, but it now works fine, and is still 3 X as fast as the next fastest program (but several programs have not been tested yet). I shortened the test quantity to 10 million numbers, to save time, but still give a good spread.

[whiteflags]

Yeah my earlier versions were wrong. I'm ready to fix this for the final time hopefully.

#include <limits.h>
#include <stdio.h>

void foo (long sn , char *res , size_t res_siz);

int main (void)
{
    long n;
    char str[BUFSIZ];

    foo (LONG_MIN , str , BUFSIZ);
    puts (str);
    foo (LONG_MAX , str , BUFSIZ);
    puts (str);

    for (n = 1L; n < 1000000000L; n *= 10)
    {
        foo (n , str , BUFSIZ);
        puts (str);
        foo (-n , str , BUFSIZ);
        puts (str);
    }

    return 0;
}

void foo (long sn , char *res , size_t res_siz)
{
    unsigned long un = sn;
    unsigned long stack[4];
    int used = 0;
    size_t k = 0U;

    if (sn < 0L) {
        un = sn *= -1L;
        res[used++] = '-';
    }

    while (un > 0UL) {
        stack[k++] = un % 1000UL;
        un /= 1000UL;
    }

    --k;
    used += sprintf (res + used , "%lu%c" , stack[k] , k != 0U ? ',' : '\0');
    while ((size_t)used < res_siz && k-- > 0U) {
        used += sprintf (res + used , "%03lu%c" , stack[k] , k != 0U ? ',' : '\0');
    }
}

[User Name:]

Both Win32 and Linux 64(the only platform I've tried on) allow the execution of rdtsc, you could use that for a very accurate measurement. It measures ticks since the last processor reset. It returns a 64 bit int in edx:eax, it would only take a few lines of asm to make a function to return the tsc.

[frktons]

@Elysia:

If you can get rid of the extra zero in the final results, this
is one of the functions I'd like to have as an example of
readable algorithm for beginner.

about:

There is only ISO C99 with respect to that standard.

you are right. I meant you can compile it on any machine [Mac,Linux,Win...]
that has got a standard C99 compiler. :-)

@quzah:
Yes.

@whiteflags:

Umm, what about what iMalc has said, frktons...
I think you've reached a plateau, so like, the only things to do are make sure
iMalc's version is correct, and you know that it is, apparently. So, what to make
this thread about? Did you want a function remotely C like?

The main aim of this and previous thread is to learn some
C syntax and some C applied to algorithm building/thinking.
Now I'm testing if the posted versions are correct, and I'm
asking your help to do that because I don't have all the time
and knowledge I would.

If I don't go wrong you posted a nice version with recursion,
one that I'd like to be tested and learn something from.

If you can help me, try to do it yourself, no matter the performance,
I like the style and the concepts behind it. :-)
Would you be so kind to adapt the function you wrote
to the testpad and see what you get please?

The "let's do it faster" is just for setting a challenge to
motivate people, not the real target. I hope it is clear
enough.

All the compiler optimization stuff is beyond the scope
of this thread [I am a beginner for the time being].

@cyberfish:

Thanks cyberfish, would you transfer all those nice points
in something C-like? I'd appreciate it very much.
If you have a better testpad than mine, and it would not
be so strange, after all you have far more experience than me
with C-stuff, please show it.
By the way, the function you proposed is a good one,
did you debug it for numbers smaller than 1,000?

@zacs7:

I would not be happy with "000,012" if I wanted "12".

neither would I. ;-)

@Adak:

good to know, looking forward to seeing for some output
and attached C-stuff.

@User Name:

thanks. good to know.

[whiteflags]

>> Would you be so kind to adapt the function you wrote
>> to the testpad and see what you get please?

The key difference between what I posted here, and the recursive version I gave you ages ago lies in the format strings. Have at it yourself and come back successful or with problems.

>> All the compiler optimization stuff is beyond the scope
>> of this thread [I am a beginner for the time being].

I didn't say it was slow, I said it was wrong.

I'm going to go to sleep now.

[Elysia]

Both Win32 and Linux 64(the only platform I've tried on) allow the execution of rdtsc, you could use that for a very accurate measurement. It measures ticks since the last processor reset. It returns a 64 bit int in edx:eax, it would only take a few lines of asm to make a function to return the tsc.

You need to stop jumping to assembly all the time. Assembly is non-portable, dangerous and not always available (MSVC x64 doesn't allow inline asm, for example).
Plus rdtsc does not accurately work on dual cores processors! Didn't you know that all software/games relied on this before and broke when dual cores came around?

[frktons]

@whiteflags:

while you sleep,

I'm going to test your new version ASAP.

Edit: not really testable by me, I should rewrite it and
I lack the necessary knowledge and skill.
Let it stay there for now, until somebody more capable
than me takes the task to adapt it to the testpad.

In few months, after summer vacation time, I'll probably
be able to do it by myself, in case nobody shows up.

Your new recursive function shows it works properly on some
numbers:

-2,147,483,648
2,147,483,647
1
-1
10
-10
100
-100
1,000
-1,000
10,000
-10,000
100,000
-100,000
1,000,000
-1,000,000
10,000,000
-10,000,000
100,000,000
-100,000,000

But I still don't know it it is a final release or an intermediate step.

[cyberfish]

Thanks cyberfish, would you transfer all those nice points
in something C-like? I'd appreciate it very much.
If you have a better testpad than mine, and it would not
be so strange, after all you have far more experience than me
with C-stuff, please show it.
By the way, the function you proposed is a good one,
did you debug it for numbers smaller than 1,000?

Well I don't really have time right now, but which one do you need help with?

The first one would be something like

generate an array of 1000000 random integers
make an array of 1000000 buffers to hold the answers
start timing
call the function to add commas (and store answers in the second array)
stop timing
for every number, use a known correct algorithm to calculate the string, and compare it to the second array

And no, I didn't try with <1000. Will do that tonight.

[frktons]

Well I don't really have time right now, but
which one do you need help with?

The first one would be something like

- generate an array of 1000000 random integers
- make an array of 1000000 buffers to hold the answers
- start timing
- call the function to add commas (and store answers
  in the second array)
- stop timing
- for every number, use a known correct algorithm to 
  calculate the string, and compare it to the second array

And no, I didn't try with <1000. Will do that tonight.

That is fairly good to do after I have a bounch of working
functions to test and it'll take quite a while to code for a
beginner like me.
I already made a pre-test with my testpad and most of the
functions tested need to be fixed.
So far I'm still waiting for the working versions of:
- quzah
- cyberfish
- Elysia
- whiteflags - not sure
- Adak ?
- maybe somebody else

All of us haven't plenty of time to dedicate to it, so we have to go self
paced. Actually I'm not in a hurry. As time permits and
I study more C-stuff, things are going to speed up a little. And
somebody has already some testpad to test his functions as well.

A last thing: what about itoas() --> from integer to ASCII with
s-eparator ? I hope it's not around yet. :-)

Let's see what happens and enjoy your week-end.