Testpad for itoa()

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:

Code:

---


                    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

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):

Code:

---

                    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!

He probably means something like:

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


Quzah.

Umm, what about what iMalc has said, frktons:

Quote:

---

Originally Posted by iMalc

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:

Quote:

---

Originally Posted by iMalc

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?

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.

Quote:

---

Originally Posted by 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):

Code:

---

                    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".

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.

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

Code:

---

#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');
    }
}

---

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.

@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:

Quote:

---

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:

Quote:

---

Originally Posted by 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:

Quote:

---

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.

>> 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.

Quote:

---

Originally Posted by 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.

---

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?

@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:

Code:

---

-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.

Quote:

---

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

Code:

---

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.

Quote:

---

Originally Posted by cyberfish

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

The first one would be something like

Code:

---

- 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.

Code:

---

                    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: -1,234,567,890

 Elapsed time: 208 ms 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
Press any key to continue . . .

---

Code:

---

// ----------------------------------------------------------------------------------------------
// Prog_name: testpad.c
// A program for testing functions formatting integer numbers with
// thousand separators and sign.
//-----------------------------------------------------------------------------------------------
// Created with Pelles C for Windows 6.00.4
// Standard ISO C99
//-----------------------------------------------------------------------------------------------
// Date: 09 july 2010
// Testpad by frktons
//-----------------------------------------------------------------------------------------------

#include <stdio.h>
#include <time.h>
#include <string.h>

//-----------------------------------------------------------------------------------------------
// Function prototype for itoa(). Takes in the number to
// format, and the pointer of the buffer to fill. Returns an int.
//-----------------------------------------------------------------------------------------------

void itoa(long num, char []);

char digits_table[999999][8];

//-----------------------------------------------------------------------------------------------

int main(void)
{
 
        for (int i = 0; i < 999999; i++)
        {
                for (int j = 0; j < 8; j++)
                {
                        digits_table[i][0] = ',';
                        digits_table[i][1] = '0' + char(i / 100000);
                        digits_table[i][2] = '0' + char(i / 10000 % 10);
                        digits_table[i][3] = '0' + char(i / 1000 % 10);
                        digits_table[i][4] = ',';
                        digits_table[i][5] = '0' + char(i / 100 % 10);
                        digits_table[i][6] = '0' + char(i / 10 % 10);
                        digits_table[i][7] = '0' + char(i % 10);
                }
        }
       
        long num = -1234567890;          // test number
    int cycles = 0;



    clock_t start = 0;              // initial time
    clock_t stop = 0;              // end time
    const char *ver = "Elysia";        // Program version
    char buffer[50] = {'\0'};        // string array for the formatted number
                                              // 10 digits max + 3 separators max + sign + NULL
 
    long times = 10000000;      // for testing performance set this number for repetitions

//-----------------------------------------------------------------------------------------------
// HW-SW platform
//-----------------------------------------------------------------------------------------------
    const char *OS = "Windows 7 Ultimate 64 bit";
        const char *CPU = "AMD Athlon II X2 250 (3 GHz)";
    const char *compiler = "Microsoft Visual Studio 2010";
//-----------------------------------------------------------------------------------------------

    printf("\n\t\t    Testing version : %s \n",ver);
    printf("\t\t ------------------------------\n");

    printf(" Testing on %s\n",CPU);
    printf(" OS = %s  --  Compiler = %s\n",OS,compiler);
    printf("\n The value of num is: %d\n",num);

    start = clock();

    for (cycles = 0; cycles < times; cycles++) {

        itoa(num,buffer);

    } // end for

    stop = clock();
   
    printf("\n The formatted value of num is: %s\n",buffer);

    itoa((long)(stop-start)/(CLOCKS_PER_SEC/1000),buffer);
    printf("\n Elapsed time: %s ms",buffer);

    itoa(times,buffer);
    printf(" to perform %s cycles\n",buffer);


//------------------------------------------------------------------------------
// Test some numbers
//------------------------------------------------------------------------------

    printf(" -------------------------------------------------------\n");

    long test = -2147483647 - 1;
        itoa(0,buffer);
    printf("\n handling 0 ---> %s",buffer);
    itoa(12,buffer);
    printf("\n handling 12 ---> %s",buffer);
    itoa(256,buffer);
    printf("\n handling 256 ---> %s",buffer);
    itoa(1000,buffer);
    printf("\n handling 1000 --> %s",buffer);
    itoa(1000000,buffer);
    printf("\n handling 1000000 ---> %s",buffer);
    itoa(1000000000,buffer);
    printf("\n handling 1000000000 ---> %s",buffer);
    itoa(2147483647,buffer);
    printf("\n handling 2147483647 -> %s",buffer);
    itoa(test,buffer);
    printf("\n handling -2147483648 -> %s\n",buffer);

    return 0;
}

//---------------------------------------------------------------
// itoa() - Elysia's version
//---------------------------------------------------------------
__forceinline void itoa(long num, char buffer[])
{
        int remain = 0;                  // integer variable to store the remainder
        bool neg = false;
        const int sizeof_buffer = 30;
        unsigned long newnum;

        memset(buffer, 0, 50);

        if (num == 0)
        {
                strcpy(buffer, "0");
                return;
        }
        if (num < 0)
        {
                neg = true;
                buffer[0] = '-';
                newnum = -num; // transform number to positive if negative
        }
        else
                newnum = num;

        int x, copy_from_offset = 0;
        for (x = sizeof_buffer - 1; newnum; x -= 8)
        {
                if (newnum < 100000)
                {
                        copy_from_offset = 1;
                        if (newnum < 10) copy_from_offset = 6;
                        else if (newnum < 100) copy_from_offset = 5;
                        else if (newnum < 1000) copy_from_offset = 4;
                        else if (newnum < 10000) copy_from_offset = 2;
                }
                remain = newnum % 1000000;
                newnum /= 1000000;
                memcpy(&buffer[x - 8], digits_table[remain], 8);
        }

        int copy_to = 0;
        if (neg) copy_to++;
        memmove(&buffer[copy_to], &buffer[x + 1] + copy_from_offset, sizeof_buffer - x - 1 - copy_from_offset);
        buffer[sizeof_buffer - x - 1] = '\0';
}

---

There you go. Quick and dirt. x64 version (beats x86 version by ~2x).

Quote:

---

Originally Posted by Elysia

Code:

---

                    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: -1,234,567,890

 Elapsed time: 208 ms 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
Press any key to continue . . .

---

Code:

---

// ----------------------------------------------------------------------------------------------
// Prog_name: testpad.c
// A program for testing functions formatting integer numbers with
// thousand separators and sign.
//-----------------------------------------------------------------------------------------------
// Created with Pelles C for Windows 6.00.4
// Standard ISO C99
//-----------------------------------------------------------------------------------------------
// Date: 09 july 2010
// Testpad by frktons
//-----------------------------------------------------------------------------------------------

#include <stdio.h>
#include <time.h>
#include <string.h>

//-----------------------------------------------------------------------------------------------
// Function prototype for itoa(). Takes in the number to
// format, and the pointer of the buffer to fill. Returns an int.
//-----------------------------------------------------------------------------------------------

void itoa(long num, char []);

char digits_table[999999][8];

//-----------------------------------------------------------------------------------------------

int main(void)
{
 
        for (int i = 0; i < 999999; i++)
        {
                for (int j = 0; j < 8; j++)
                {
                        digits_table[i][0] = ',';
                        digits_table[i][1] = '0' + char(i / 100000);
                        digits_table[i][2] = '0' + char(i / 10000 % 10);
                        digits_table[i][3] = '0' + char(i / 1000 % 10);
                        digits_table[i][4] = ',';
                        digits_table[i][5] = '0' + char(i / 100 % 10);
                        digits_table[i][6] = '0' + char(i / 10 % 10);
                        digits_table[i][7] = '0' + char(i % 10);
                }
        }
       
        long num = -1234567890;          // test number
    int cycles = 0;



    clock_t start = 0;              // initial time
    clock_t stop = 0;              // end time
    const char *ver = "Elysia";        // Program version
    char buffer[50] = {'\0'};        // string array for the formatted number
                                              // 10 digits max + 3 separators max + sign + NULL
 
    long times = 10000000;      // for testing performance set this number for repetitions

//-----------------------------------------------------------------------------------------------
// HW-SW platform
//-----------------------------------------------------------------------------------------------
    const char *OS = "Windows 7 Ultimate 64 bit";
        const char *CPU = "AMD Athlon II X2 250 (3 GHz)";
    const char *compiler = "Microsoft Visual Studio 2010";
//-----------------------------------------------------------------------------------------------

    printf("\n\t\t    Testing version : %s \n",ver);
    printf("\t\t ------------------------------\n");

    printf(" Testing on %s\n",CPU);
    printf(" OS = %s  --  Compiler = %s\n",OS,compiler);
    printf("\n The value of num is: %d\n",num);

    start = clock();

    for (cycles = 0; cycles < times; cycles++) {

        itoa(num,buffer);

    } // end for

    stop = clock();
   
    printf("\n The formatted value of num is: %s\n",buffer);

    itoa((long)(stop-start)/(CLOCKS_PER_SEC/1000),buffer);
    printf("\n Elapsed time: %s ms",buffer);

    itoa(times,buffer);
    printf(" to perform %s cycles\n",buffer);


//------------------------------------------------------------------------------
// Test some numbers
//------------------------------------------------------------------------------

    printf(" -------------------------------------------------------\n");

    long test = -2147483647 - 1;
        itoa(0,buffer);
    printf("\n handling 0 ---> %s",buffer);
    itoa(12,buffer);
    printf("\n handling 12 ---> %s",buffer);
    itoa(256,buffer);
    printf("\n handling 256 ---> %s",buffer);
    itoa(1000,buffer);
    printf("\n handling 1000 --> %s",buffer);
    itoa(1000000,buffer);
    printf("\n handling 1000000 ---> %s",buffer);
    itoa(1000000000,buffer);
    printf("\n handling 1000000000 ---> %s",buffer);
    itoa(2147483647,buffer);
    printf("\n handling 2147483647 -> %s",buffer);
    itoa(test,buffer);
    printf("\n handling -2147483648 -> %s\n",buffer);

    return 0;
}

//---------------------------------------------------------------
// itoa() - Elysia's version
//---------------------------------------------------------------
__forceinline void itoa(long num, char buffer[])
{
        int remain = 0;                  // integer variable to store the remainder
        bool neg = false;
        const int sizeof_buffer = 30;
        unsigned long newnum;

        memset(buffer, 0, 50);

        if (num == 0)
        {
                strcpy(buffer, "0");
                return;
        }
        if (num < 0)
        {
                neg = true;
                buffer[0] = '-';
                newnum = -num; // transform number to positive if negative
        }
        else
                newnum = num;

        int x, copy_from_offset = 0;
        for (x = sizeof_buffer - 1; newnum; x -= 8)
        {
                if (newnum < 100000)
                {
                        copy_from_offset = 1;
                        if (newnum < 10) copy_from_offset = 6;
                        else if (newnum < 100) copy_from_offset = 5;
                        else if (newnum < 1000) copy_from_offset = 4;
                        else if (newnum < 10000) copy_from_offset = 2;
                }
                remain = newnum % 1000000;
                newnum /= 1000000;
                memcpy(&buffer[x - 8], digits_table[remain], 8);
        }

        int copy_to = 0;
        if (neg) copy_to++;
        memmove(&buffer[copy_to], &buffer[x + 1] + copy_from_offset, sizeof_buffer - x - 1 - copy_from_offset);
        buffer[sizeof_buffer - x - 1] = '\0';
}

---

There you go. Quick and dirt. x64 version (beats x86 version by ~2x).

---

Very good Elysia, thanks for your collaboration.
Unfortunately it seems not strictly C99 standard:

Code:

---

Building testpad.obj.
testpad.c(36): error #2039: Illegal expression.
testpad.c(36): error #2068: Expected a function but found 'int'.
testpad.c(36): error #2168: Operands of '+' have incompatible types 'int' and 'void'.
testpad.c(37): error #2039: Illegal expression.
testpad.c(37): error #2068: Expected a function but found 'int'.
testpad.c(37): error #2168: Operands of '+' have incompatible types 'int' and 'void'.
testpad.c(38): error #2039: Illegal expression.
testpad.c(38): error #2068: Expected a function but found 'int'.
testpad.c(38): error #2168: Operands of '+' have incompatible types 'int' and 'void'.
testpad.c(40): error #2039: Illegal expression.
testpad.c(40): error #2068: Expected a function but found 'int'.
testpad.c(40): error #2168: Operands of '+' have incompatible types 'int' and 'void'.
testpad.c(41): error #2039: Illegal expression.
testpad.c(41): error #2068: Expected a function but found 'int'.
testpad.c(41): error #2168: Operands of '+' have incompatible types 'int' and 'void'.
testpad.c(42): error #2039: Illegal expression.
testpad.c(42): error #2068: Expected a function but found 'int'.
testpad.c(42): error #2168: Operands of '+' have incompatible types 'int' and 'void'.
testpad.c(126): error #2048: Undeclared identifier 'bool'.
testpad.c(126): error #2001: Syntax error: expected ';' but found 'neg'.
testpad.c(126): error #2048: Undeclared identifier 'neg'.
testpad.c(126): error #2048: Undeclared identifier 'false'.
testpad.c(139): error #2048: Undeclared identifier 'true'.
testpad.c(126): warning #2114: Local 'bool' is not referenced.
*** Error code: 1 ***
Done.

---

My compiler complains about:

Code:

---

                        digits_table[i][0] = ',';
                        digits_table[i][1] = '0' + char(i / 100000);
                        digits_table[i][2] = '0' + char(i / 10000 % 10);
                        digits_table[i][3] = '0' + char(i / 1000 % 10);
                        digits_table[i][4] = ',';
                        digits_table[i][5] = '0' + char(i / 100 % 10);
                        digits_table[i][6] = '0' + char(i / 10 % 10);
                        digits_table[i][7] = '0' + char(i % 10);

---

Any possible standard coding?

Those look like function-style casts from C++. I expect that they should be:

Code:

---

digits_table[i][1] = '0' + (char)(i / 100000);

---

etc. However, the explicit cast is probably unnecessary anyway, since the result would be promoted back to int for the addition.

Right. You complained about that before, but you never said if my solution fixed it... I don't think GCC likes that syntax for some reason.
Change it to:

Code:

---

                        digits_table[i][0] = ',';
                        digits_table[i][1] = '0' + (char)(i / 100000);
                        digits_table[i][2] = '0' + (char)(i / 10000 % 10);
                        digits_table[i][3] = '0' + (char)(i / 1000 % 10);
                        digits_table[i][4] = ',';
                        digits_table[i][5] = '0' + (char)(i / 100 % 10);
                        digits_table[i][6] = '0' + (char)(i / 10 % 10);
                        digits_table[i][7] = '0' + (char)(i % 10);

---

And try again.

Also, for bool, try:

Code:

---

#ifndef _MSC_VER
#include <stdbool.h>
#endif

---

MSVC doesn't support C99.
The first line should be cast to char since otherwise you'll get a warning of int to char: possible loss of data. You could add % 10 to it, or you could cast it. Your choice. The rest doesn't seem to need the cast, though.

And did you have to quote the entire post?

OK Elysia, changing the code with (char) typecasting worked.
The results on my pc:

Code:

---


                    Testing version : Elysia
                ------------------------------
 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 time: 936 ms 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
Press any key to continue...

---

This is going to be one of the selected working solutions.

If you post the EXE compiled with 64 bit features, it'll probably
test faster on my pc as well.

Thanks

Compile an x64 build, as well, should you be able. The code was made to lend itself well to that since it performs a 64-bit move per loop.

Quote:

---

Originally Posted by Elysia

Compile an x64 build, as well, should you be able. The code was made to lend itself well to that since it performs a 64-bit move per loop.

---

I don't think I can do it with Pelles' C. If I use the command line CL.EXE
from MSVC 2010, that I have somewhere on my pc, what command line should I use?

No idea. Not using command lines (what do you think IDEs are for?).
But this is all the more reason to drop your compiler. We've already shown that GCC and MSVC beats it at optimizing.

Quote:

---

Originally Posted by frktons

I don't think I can do it with Pelles' C.

---

The Pelles C homepage states that it supports 64-bit compilation, though obtaining the documentation on how to do that is another matter as there are no obvious links on the website or wiki.

I suppose you should also rerun iMalc's code to measure it in ms instead of clock ticks.
(For a fair comparison; otherwise we don't know by how many orders of magnitude slower or faster other codes are.)

Quote:

---

Originally Posted by Elysia

I suppose you should also rerun iMalc's code
to measure it in ms instead of clock ticks.
(For a fair comparison; otherwise we don't know by how many orders
of magnitude slower or faster other codes are.)

---

My pc is 32 bit, so Pelles'C 64 bit refuses to compile in x64 mode.

Code:

---

    itoa((long)(stop-start)/(CLOCKS_PER_SEC/1000),buffer);
    printf("\n Elapsed time: %s ms",buffer);

---

I didn't see you changed the timing system, ok, I'll change it on the
testpad and retest iMalc version.
Results following:

Code:

---


                    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 time: 297 ms 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

---

See you later :-)

Edit: Well, doesn't seem to change a lot from previous system.

Wait. What?

Testing on Intel Core Duo 6600 2.4 Ghz
OS = Windows 7 Ultimate 64 bit -- Compiler = Pelles C 6.00.4
My pc is 32 bit, so Pelles'C 64 bit refuses to compile in x64 mode.

Something here isn't right. You use a 64-bit system. You have a Core Duo (not Core 2 Duo), which AFAIK, doesn't support x64 AND you say your PC is x86...

Quote:

---

Originally Posted by Elysia

Wait. What?

Testing on Intel Core Duo 6600 2.4 Ghz
OS = Windows 7 Ultimate 64 bit -- Compiler = Pelles C 6.00.4
My pc is 32 bit, so Pelles'C 64 bit refuses to compile in x64 mode.

Something here isn't right. You use a 64-bit system. You have a Core Duo (not Core 2 Duo), which AFAIK, doesn't support x64 AND you say your PC is x86...

---

It is a Core 2 Duo E6600 - IA32 architecture, but supports some x64 software features.
The OS is 64 bit and works fine.

By the way, if I try to compile in x64 mode Pelles C gives these errors:

Code:

---

POLINK: error: Unresolved external symbol '__imp_GetSystemTimeAsFileTime'.
POLINK: error: Unresolved external symbol '__imp_HeapCreate'.
POLINK: error: Unresolved external symbol '__imp_HeapDestroy'.
POLINK: error: Unresolved external symbol '__imp_HeapAlloc'.
POLINK: error: Unresolved external symbol '__imp_HeapReAlloc'.
POLINK: error: Unresolved external symbol '__imp_HeapFree'.
POLINK: error: Unresolved external symbol '__imp_HeapSize'.
POLINK: error: Unresolved external symbol '__imp_HeapValidate'.
POLINK: error: Unresolved external symbol '__imp_ExitProcess'.
POLINK: error: Unresolved external symbol '__imp_GetStartupInfoA'.
POLINK: error: Unresolved external symbol '__imp_GetFileType'.
POLINK: error: Unresolved external symbol '__imp_GetStdHandle'.
POLINK: error: Unresolved external symbol '__imp_GetCurrentProcess'.
POLINK: error: Unresolved external symbol '__imp_DuplicateHandle'.
POLINK: error: Unresolved external symbol '__imp_SetHandleCount'.
POLINK: error: Unresolved external symbol '__imp_GetCommandLineA'.
POLINK: error: Unresolved external symbol '__imp_GetModuleFileNameA'.
POLINK: error: Unresolved external symbol '__imp_GetEnvironmentStrings'.
POLINK: error: Unresolved external symbol '__imp_FreeEnvironmentStringsA'.
POLINK: error: Unresolved external symbol '__imp_UnhandledExceptionFilter'.
POLINK: error: Unresolved external symbol '__imp_RtlUnwindEx'.
POLINK: error: Unresolved external symbol '__imp_ReadFile'.
POLINK: error: Unresolved external symbol '__imp_GetLastError'.
POLINK: error: Unresolved external symbol '__imp_GetConsoleMode'.
POLINK: error: Unresolved external symbol '__imp_GetConsoleCP'.
POLINK: error: Unresolved external symbol '__imp_SetConsoleCtrlHandler'.
POLINK: error: Unresolved external symbol '__imp_GetConsoleOutputCP'.
POLINK: error: Unresolved external symbol '__imp_WriteFile'.
POLINK: error: Unresolved external symbol '__imp_MultiByteToWideChar'.
POLINK: error: Unresolved external symbol '__imp_VirtualAlloc'.
POLINK: error: Unresolved external symbol '__imp_VirtualQuery'.
POLINK: error: Unresolved external symbol '__imp_SetStdHandle'.
POLINK: error: Unresolved external symbol '__imp_SetFilePointer'.
POLINK: error: Unresolved external symbol '__imp_WideCharToMultiByte'.
POLINK: error: Unresolved external symbol '__imp_CloseHandle'.
POLINK: error: Unresolved external symbol '__imp_DeleteFileA'.

---

maybe I miss an #include somewhere.

OK, solved. In X64 mode I have:

Code:

---


                    Testing version : iMalc
                ------------------------------
 Testing on Intel Core 2 Duo E6600 2.4 Ghz IA32
 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 time: 265 ms 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

---

and

Code:

---


                    Testing version : Elysia
                ------------------------------
 Testing on Intel Core 2 Duo E6600 2.4 Ghz IA32
 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 time: 905 ms 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
Press any key to continue...

---

This is not missing includes! This is missing libraries.

Quote:

---

Originally Posted by Elysia

This is not missing includes! This is missing libraries.

---

Sorry Elysia, I still don't know very well Pelles C.
I had to create a Win 64 console project and everything went
all right, see my previous post.

Quote:

---

Originally Posted by 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.

---

There is more to the solution to issue 1 than you'd think though. If you use random numbers equally distributed over the entire range of an int then you'll get very few numbers close to 0 and as such might not test any one or two digit cases for example.
You can either test say -9999 to 9999 explicitly first (along with other specific cases like min and max), or you can generate the values from a different distribution such as normal distribution.

With number 3, in the real world it could be handled by documentation perhaps in the form of comments that the buffer must always have room for 15 characters (1 minus sign, 10 digits, 3 commas, 1 null terminator).

So x64 cut it down to 265 ms? Nice.

Quote:

---

Originally Posted by iMalc

There is more to the solution to issue 1 than you'd think though. If you use random numbers equally distributed over the entire range of an int then you'll get very few numbers close to 0 and as such might not test any one or two digit cases for example.
You can either test say -9999 to 9999 explicitly first (along with other specific cases like min and max), or you can generate the values from a different distribution such as normal distribution.

With number 3, in the real world it could be handled by documentation perhaps in the form of comments that the buffer must always have room for 15 characters (1 minus sign, 10 digits, 3 commas, 1 null terminator).

---

Probably tests based on some range between -n to +n, plus the particular cases
like zero, int_min, int_max, plus a random serie of numbers in 3-4 different ranges
could be exaustive enough.

With number 3 I used the "always room for 15 characters" option.

@Elysia

Quote:

---

So x64 cut it down to 265 ms? Nice.

---

Yes, X64 option is a bit faster even on my IA32 machine. :-)

Your real X64 machine should give an impressive 80-90 ms for
iMalc version. Did you test it?

And a last thing. Your version can spare some ms getting rid of
the bool neg altogheter. Without you have:

Code:

---


                    Testing version : Elysia
                ------------------------------
 Testing on Intel Core 2 Duo E6600 2.4 Ghz IA32
 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 time: 897 ms 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

---

Changing the appropriate code:

Code:

---

        if (num < 0)
        {
//                neg = true;
                copy_to++;
                buffer[0] = '-';
                newnum = -num; // transform number to positive if negative
        }

---

Without inlining, I got 198 ms for iMalc's code.
When I forced it inline, the compiler was smart enough to optimize it all away, so 0 ms.

Quote:

---

Originally Posted by Elysia

Without inlining, I got 198 ms for iMalc's code.
When I forced it inline, the compiler was smart enough to optimize it all away, so 0 ms.

---

I have still some doubts about what the compiler does
when the performance changes so much, only testing the
function with random generated numbers can give me a
realistic idea.

OK, I added the random generation for the numbers to
format, so now we can see if the optimization miracle of
modern compiler is a real one or a fake version.

Attached the source for testing iMalc's function with the
modified testpad.

Let me know what results do you get.

Mine are:

Code:

---


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

 The value of num is: 938786183

 The formatted value of num is: 938,786,183

 Elapsed time: 328 ms 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

---

And yours?

Code:

---

                    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: 3734

 The formatted value of num is: 3,734

 Elapsed time: 355 ms 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
Press any key to continue . . .

---

Your version is slower than mine?
Oh ! you didn't test iMalc's version, but yours.
What about the "0 ms"?

That was iMalc's code. The compiler optimized away the function because it thought it didn't do anything worth while.
But you should understand that it's impossible to guarantee a deterministic time since we're using random numbers. You would have to have a pattern, such as x numbers of y length, etc.

Quote:

---

Originally Posted by Elysia

That was iMalc's code. The compiler optimized away the function because it thought it didn't do anything worth while.

---

You mean that your X64 ultra-speed mega VS2010 has a slower
performance than mine?

Ok let's change the instruction:

Code:

---

srand(time(NULL));

---

with:

Code:

---

srand(0);

---

so we can test the same sequence of numbers all the time.

Quote:

---

Originally Posted by frktons

You mean that your X64 ultra-speed mega VS2010 has a slower
performance than mine?

---

I have no idea where you got that from.

But it wouldn't surprise me if iMalc's code is faster. iMalc's code uses predicted paths to do as little work as necessary. But what's the most clever is the fact that there are no modulus operations. I have no idea how iMalc implemented it using minus and multiplication, though.

Quote:

---

Originally Posted by Elysia

I have no idea where you got that from.

---

I suspect it derives from a sentence I frequently heard from
a couple of guys, that sounds like:
Time to switch to a better compiler or the like. :-)

By the way we can solve the performance gap test doing:

Code:

---

srand(0);

---

and we test the same sequence of numbers all the time.

Quote:

---

Originally Posted by frktons

I suspect it derives from a sentence I frequently heard from
a couple of guys, that sounds like:
Time to switch to a better compiler or the like. :-)

---

Still doesn't tell me from what context you got that from.

I won't be doing any more performance improvements now, though. At least not for a while.
Instead, I am going to sleep. Sweet sleep.

Quote:

---

Originally Posted by frktons

So far I'm still waiting for the working versions of:
- whiteflags - not sure

---

I have shown you a similar unit test (the main function) to your test pad. If you can't get it to work with your code, I can't help you unless you're specific. But with the version I posted here, all you need to do is invoke foo. O_o

Quote:

---

Originally Posted by whiteflags

I have shown you a similar unit test (the main function) to your test pad. If you can't get it to work with your code, I can't help you unless you're specific. But with the version I posted here, all you need to do is invoke foo. O_o

---

Thanks for your explanation, I'll try again, maybe I get it working
on my testpad.

Quote:

---

Originally Posted by Elysia

I have no idea how iMalc implemented it using minus and multiplication, though.

---

Here's a good link with an explanation of the technique. Hopefully not too math heavy.

Here's an updated version which includes some small lookup tables for a futher slight improvement.
I haven't updated the testbed at this stage though.

Quote:

---

Originally Posted by iMalc

Here's an updated version which includes some small lookup tables for a futher slight improvement.
I haven't updated the testbed at this stage though.

---

Thanks iMalc.

Can you explain why you are declaring:

Code:

---

int itoa(long snum, char s[])

---

and using

Code:

---

    return ps - s;

---

?

What are these for? I rewrote them this way:

Code:

---

void itoa(long snum, char s[])

---

and

Code:

---

    return;

---

Because we are not using a return value, so this pushing
to the stack a return value is using CPU cycles for no purpose,
at least in this context.

By the way, the performance I get is not any better than the previous
one, even 2-3 ms slower. (?)

A last question, if you like to elaborate it:
You said the algorithm you are applying here is not the best you
can get, because compilers already do that even better.

What would be the difference between your version and the version
a smart compiler produces?

Thanks again for your collaboration. The idea behind this optimization
is very clever and I hope I'll be able to grasp it one day. :-)

Quote:

---

Originally Posted by frktons

What are these for?

---

To return the length of the string.

Quote:

---

Originally Posted by laserlight

To return the length of the string.

---

Thanks. It could be useful in another context. ;-)

Quote:

---

By the way, the performance I get is not any better than the previous
one, even 2-3 ms slower. (?)

A last question, if you like to elaborate it:
You said the algorithm you are applying here is not the best you
can get, because compilers already do that even better.

What would be the difference between your version and the version
a smart compiler produces?

---

Not to answer in iMalc's stead but I did try to warn you that you've hit a performance plateau.

And the compiler's doing instructions better is a positive thing.

The fastest version is not meant to be a nearly unreadable set of instructions like you've been getting. Normally you would use math to do this, as iMalc and several people have, and minimize complicated logic. Then, you turn on the compiler's optimization switch (provided you understand what your options are), and the compiler will do things in the underlying assembly, say, to get speed.

iMalc has gone into detail about said optimization as it applies to his code.

If you attempt to do such optimizations in plain code, without knowing what you are doing more than anyone usually does, you will just convince the compiler to use different assembly instructions for the operation, which may or may not be faster.

Quote:

---

Originally Posted by whiteflags

Not to answer in iMalc's stead but I did try to warn
you that you've hit a performance plateau.

And the compiler's doing instructions better is a positive thing.

The fastest version is not meant to be a nearly unreadable set of instructions like you've been getting. Normally you would use math to do this, as iMalc and several people have, and minimize complicated logic. Then, you turn on the compiler's optimization switch (provided you understand what your options are), and the compiler will do things in the underlying assembly, say, to get speed.

iMalc has gone into detail about said optimization as it applies to his code.

If you attempt to do such optimizations in plain code, without knowing what you are doing more than anyone usually does, you will just convince the compiler to use different assembly instructions for the operation, which may or may not be faster.

---

I ask because I've some doubts. When somebody posted a zero ms result
versus 100-200 ms, my logic freaked out. So I asked some smart Assembly
guys who just replied:"NO WAY, show us the Assembly produced by the
compiler and we'll show you what nasty trick the compiler is playing".

Now, with random numbers the miracle of "0 ms performance" is over.
Those guys explained me what more or less the compiler was doing.

The performance is not the main subject of this thread, we are testing for
correctness the various posted solutions, so if we reached a performance plateau
it doesn't really matter.

I'm here to learn, or to have a look at what to learn in the future.
Curiosity is not an unforgiveable sin. I just asked iMalc why he
is not happy about applying the math that he showed us.

I can understand your warnings, they are pretty correct. Unfortunately the
infinite debate among Aseembly guys and Compiler adepts is not going to
stop. I'm not in that debate, and I don't want to be involved.

Try to think this way: some 30 years ago I was playing with COBOL on
big old mainframes. Now that I'm free from that hardware and I can play
with new toys, I really would appreciate my freedom of doing a lot of mistakes
I was not allowed to in that age.

Bear with me my friend, let me learn it the hard way. :-)

Quote:

---

Originally Posted by frktons

Because we are not using a return value, so this pushing
to the stack a return value is using CPU cycles for no purpose,
at least in this context.

---

You are being paranoid. The time taken there is negligible compared to the rest of the code. It probably won't impact the result by anything.

As for the 0ms thingy, it's like I said. The compiler simply removes all of the code because it detects that it actually does nothing. You calculate a result and then throws it away. That's unnecessary because you're not storing it anywhere, so the compiler could easily remove the code and gain speed.
So the code itself isn't super hyper ultra fast--it's gone. That's what I meant. iMalc's code allowed the compiler to figure out what it was doing enough to deem it unnecessary.

Quote:

---

Originally Posted by Elysia

You are being paranoid. The time taken there is negligible compared to the rest of the code. It probably won't impact the result by anything.

As for the 0ms thingy, it's like I said. The compiler simply removes all of the code because it detects that it actually does nothing. You calculate a result and then throws it away. That's unnecessary because you're not storing it anywhere, so the compiler could easily remove the code and gain speed.
So the code itself isn't super hyper ultra fast--it's gone. That's what I meant. iMalc's code allowed the compiler to figure out what it was doing enough to deem it unnecessary.

---

Thanks Elysia, if I correctly remember, the same nasty trick GCC was
doing with my code as well, not only with iMalcs, as cyberfish revealed.

About the first part of your comment I agree almost completely, except for
the very first part. :-) Don't worry about my mental sanity, I can make it. ;-)

Quote:

---

Originally Posted by frktons

Thanks iMalc.

Can you explain why you are declaring:

---

Yup, string length as already noted my laserlight

Quote:

---

By the way, the performance I get is not any better than the previous
one, even 2-3 ms slower. (?)

---

I got a slight improvement using visual studio, but it certainly small enough that it's likely to vary from slightly better to slightly worse depending on compiler and platform etc. It trades a multiplication for a table lookup, which isn't always a win I guess.

Quote:

---

A last question, if you like to elaborate it:
You said the algorithm you are applying here is not the best you
can get, because compilers already do that even better.

What would be the difference between your version and the version
a smart compiler produces?

---

Because the multiplicative inverse I was using only allowed me to perform the simulated division on numbers up to 10000 but not 100000 you'll notice that I had to split the number up into three variables num1, num2, and num3, each being a most 9999. When the compiler performs the same multiplicative inverse trick it can use instructions that basically calculate the full 64-bit multiplication result and then just keep the highest 32-bits from that. This means that it doesn't need the extra step of breaking it up into num1, num2 and num3 first, possibly freeing up some registers as well as avoiding the two divides I had.
However, on the plus side the code I wrote may end up around the same size overall since the constants used in the machine code are smaller than the constants the compiler would have used since it can't assume the numbers are below 10000, and it may generate slightly more code when doing the same thing itself, to make sure it doesn't overflow a 64-bit multiplication as it may in some cases if you look at the article I linked earlier.

Quote:

---

Thanks again for your collaboration. The idea behind this optimization
is very clever and I hope I'll be able to grasp it one day. :-)

---

It probably helps to think of it in several parts:

• Loop unrolling.
• Multiplicative inverse to perform division.
• Reducing total branch count by reordering tests.
• Pointer arithmetic instead of array indexing.
• Lookup tables.

I did make a version which had the same branching scheme that reduced the number of gotos to two, just to see how low I could get it, but I'm actually going to have to admit that the version with gotos was clearer as code wasnt nested about ten levels deep.

Quote:

---

Originally Posted by Elysia

So the code itself isn't super hyper ultra fast--it's gone. That's what I meant. iMalc's code allowed the compiler to figure out what it was doing enough to deem it unnecessary.

---

Which is pretty impressive of the compiler if you ask me! It presumably would have to had determined that there were
no calls to other functions,
no accessing globals,
only writing to an array that was never read from,
and not using the return value.
Violating perhaps any one of those would probably have foiled its efforts.

@frktons:

Your machine is 64-bit. There is no "partial" 64-bit mode. If you are running a 64-bit OS, the CPU is running in 64-bit mode.

The C2D is 64-bit capable.

And I've decided to scrap my version. It's nothing special, just good old lookup tables.

Also, the C standard only guarantees a minimum RAND_MAX of 2^16. So it's possible (and very likely) that it's only generating numbers between ~-32000 to 32000. To make sure you have the full range, do something like,

Code:

---

int random_number = (rand() << 16) ^ rand();

---

And you should really exclude the random number generation time from the timing, since it would depend on the implementation (different compilers implement rand() differently. Some go for higher quality random numbers, some go for speed).

srand(0) does NOT make sure we are using the same random numbers. Using the same seed and guarantees you will get the same sequence FROM THE SAME IMPLEMENTATION. But that probably doesn't matter if iterations is big enough.

Random numbers are not very good for measuring performance, since we get different numbers a lot of the times.
But they are better at testing and making sure we try a greater range of numbers and stop the compiler from assuming the input will only one kind of number.
Using srand(NULL) is better than not using random numbers.

Why don't you just use a set distributions of numbers that covered the whole range?

Code:

---

(for i=0;i<maximum;i+=maximum/num_iterations)
    format i

---

sort of thing

Quote:

---

Originally Posted by KBriggs

Why don't you just use a set distributions of numbers that covered the whole range?

Code:

---

(for i=0;i<maximum;i+=maximum/num_iterations)
    format i

---

sort of thing

---

If you have a large lookup table, for example, that won't give you accurate memory performance because most of the digits will stay the same.

Not only that, but if maximum is 0x7FFFFFFF then you cound easily overflow.
How about a random stepsize that gradually increases over time?

Code:

---

long stepsize = 0;
(for long i=0x80000000; i <= 0x7FFFFFFF-stepsize; i += stepsize))
{
    itoa(i, buffer);
    stepsize = 1 + rand() % (((((unsigned long)i)>>7)+1);
}

---

Back from a computerless week-end, I feel like to have some:

Digression Time ;)

Before starting my considerations, I'd like to thank all the guys who
are contributing to this thread with code, suggestions, links, whatever.
I'm not going, for the time being, to reply your last posts, but I'll
do, sooner or later.

As we know, when we use standard C functions we deal with an
abstract machine, and this very fact gives us the degree of portability
we can need if we code for cross-platform software systems.

In some occasions we code just for fun, like myself, or code for
a single platform [Mac, Linux, Windows, whatever] and the degree of
portability of our code is not our first concern.

So far we have seen that a very simple task like putting a thousand separator in a
number, for readability purpose, gives us a few choices and quite a lot of thinking.

But when I look at what my Win7 OS does when I ask it to display
some info about my testpad.c guess what I get?

Code:

---


C:\>dir *.c
 Il volume nell'unità C è WIN7-64
 Numero di serie del volume: 24E7-E258

 Directory di C:\

09/07/2010  22:00            5.493 testpad.c
              1 File          5.493 byte
              0 Directory  26.987.839.488 byte disponibili

C:\>

---

As you can see my OS speaks italian and displays DATE and numbers
well formatted and localized. The same happens with the GUI properties
dialog box.

I am not sure about that, but I guess any modern OS does the same.

From a didactical point of view I need to know how I can solve the problem
using standard C functions but, at the same time, I need to know my
real machine as well. So while I have intention to carry on this experiment
of building a standard function for the given task, in a few weeks I'm going
to move towards the real machine I'm using, and have a look at the APIs
already doing what I need, and [why not] if this is more or less efficient than
the functions we built so far.

But the very next step is going to be:
The slowest but still reliable standard C99 formatting function you can dream about
:eek:

A last consideration: I think a good name for the function we are building
should be itoas() = integer to ASCII with thousand separator.

Attached the slowest version I could manage to code and the output:

Code:

---


                    Testing version : frk_slow
                ------------------------------
 Testing on Intel Core 2 Duo E6600 2.4 Ghz // IA32
 OS = Windows 7 Ultimate 64 bit  --  Compiler = Pelles C 6.00.4

 Elapsed time: 4.883 ms to format 10.000.000 random numbers
 ----------------------------------------------------------

 handling 0 ---> 0
 handling 12 ---> 12
 handling -12 ---> -12
 handling 256 ---> 256
 handling -256 ---> -256
 handling 1000 --> 1.000
 handling -1000 --> -1.000
 handling 1000000 ---> 1.000.000
 handling -1000000 ---> -1.000.000
 handling 1000000000 ---> 1.000.000.000
 handling -1000000000 ---> -1.000.000.000
 handling 2147483647 -> 2.147.483.647
 handling -2147483648 -> -2.147.483.648

---

And here we have the whole integer range performed with iMalc's itoas():

Code:

---


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

 Testing the numbers from: -2147483648  to  2147483647

 The formatting process has taken:  105,818 ms  to perform the whole cycle

---

Now we need a second version, fast enough, and already pre-tested
to compare the whole integer range generated strings to confirm they
are doing the same thing.

If I correctly remember the only pre-tested and fast enough second
itoas() should be Elysia's version. The next test should take some 9-10'.
Let me know if there is a faster pre-tested version that I don't remember.

The second function to use for testing purposes against iMalc's one
gives these results on 10 million random numbers:

Code:

---


                    Testing version : Elysia
                ------------------------------
 Testing on Intel Core 2 Duo E6600 2.4 Ghz IA32
 OS = Windows 7 Ultimate 64 bit  --  Compiler = Pelles C 6.00.4

 Elapsed time: 1.436 ms to  format 10.000.000 random numbers
 ------------------------------------------------------------

 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

---

So it'll take about 8-9 minutes to perform the whole range of
integers formatting, plus the more or less 2 minutes for iMalc's one
and the time for comparing each string produced by the two.

We are going to total 12 minutes, and still we don't know if all the
formatted strings are correct. :rolleyes:

It looks like creating a standard new function takes a lot of time.
And we didn't consider the options of locale.h so far.

locale.h was mentioned before somewhere. I mentioned it earlier in another thread it seems like that post got lost. It's possible to do this with locale.h, printf and setting the thousand_sep to "." if that is what you prefer.

Im my opinion it makes more sense to format only when you print, no need to deal with strings and the numbers can be stored in their internal representation as numbers which takes much less space. It's seems to me like the time it takes to get a number to screen is the least to worry about.

Quote:

---

Originally Posted by Subsonics

locale.h was mentioned before somewhere. I mentioned it earlier in another thread it seems like that post got lost. It's possible to do this with locale.h, printf and setting the thousand_sep to "." if that is what you prefer.

Im my opinion it makes more sense to format only when you print, no need to deal with strings and the numbers can be stored in their internal representation as numbers which takes much less space. It's seems to me like the time it takes to get a number to screen is the least to worry about.

---

Unfortunately locale.h doesn't do anything more than changing the
decimal point with a comma for european countries that use a different
thousand separator.

Normally the thousand separator is a space, at least on my machine. But you can set it to what ever you want.

Code:

---

#include <stdio.h>
#include <locale.h>

int main()
{
        setlocale(LC_NUMERIC, "");
        struct lconv *locale = localeconv();
        locale->thousands_sep = ".";

        int value = 1234567899;

        printf("%'d\n", value);


        return 0;
}

---

This prints: 1.234.567.899

Quote:

---

Originally Posted by Subsonics

Normally the thousand separator is a space, at least on my machine. But you can set it to what ever you want.

Code:

---

#include <stdio.h>
#include <locale.h>

int main()
{
        setlocale(LC_NUMERIC, "");
        struct lconv *locale = localeconv();
        locale->thousands_sep = ".";

        int value = 1234567899;

        printf("%'d\n", value);


        return 0;
}

---

This prints: 1.234.567.899

---

And the output is:

Code:

---

'd
Press any key to continue...

---

Is this what you meant?

No, that is not what I meant. It prints 1.234.567.899 here. This was posted earlier to get the currency symbol as well, without ' you don't get the separation. I'm using Unix so this is the locale.h I'm using.

http://www.opengroup.org/onlinepubs/.../locale.h.html

Have you tried it, or are you assuming based on the code?

Quote:

---

Originally Posted by Subsonics

No, that is not what I meant. It prints 1.234.567.899 here. This was posted earlier to get the currency symbol as well, without ' you don't get the separation. I'm using Unix so this is the locale.h I'm using.

<locale.h>

---

What compiler are you using? Is that standard C99? Let me see the link
as well, but on my compiler it doesn't work.

It's part of the C standard library yes. I'm not sure about the printf single quote though, It seems to be that that your system is missing.

I use gcc version 4.2.1
I just tried it in clang as well and it worked just the same.

Quote:

---

Originally Posted by Subsonics

It's part of the C standard library yes. I'm not sure about the printf single quote though, It seems to be that that your system is missing.

I use gcc version 4.2.1
I just tried it in clang as well and it worked just the same.

---

Without the single quote before the "d" I get no formatting at all:

Code:

---

1234567899
Press any key to continue...

---

Probably it is a macro extension that GCC implements, but so far
I don't know if it works on Windows C99 compilers. Until then I have
to stick with the building process. :cool:

Quote:

---

Originally Posted by frktons

Unfortunately locale.h doesn't do anything more than changing the
decimal point with a comma for european countries that use a different
thousand separator.

---

If I do:

Code:

---

int main(void)
{
        setlocale(LC_NUMERIC, "");
        struct lconv *locale = localeconv();
        locale->thousands_sep = ".";
        locale->decimal_point = ",";

        double value = 1234567.899;

        printf("%.3f\n", value);

        return 0;
}

---

I get :

Code:

---

1234567,899
Press any key to continue...

---

That is what I already knew. Unfortunately nothing else for my
compilers gets authomated.

Quote:

---

Originally Posted by frktons

Without the single quote before the "d" I get no formatting at all:

Code:

---

1234567899
Press any key to continue...

---

---

Me neither. Anyway this is most likely a printf issue, but look into how you print based on locale settings in windows, there must be a way. :)

Quote:

---

For some numeric conversions a radix character ('decimal point') or thousands' grouping character is used. The actual character used depends on the LC_NUMERIC part of the locale. The POSIX locale uses '.' as radix character, and does not have a grouping character. Thus,

printf("%'.2f", 1234567.89);
results in '1234567.89' in the POSIX locale, in '1234567,89' in the nl_NL locale, and in '1.234.567,89' in the da_DK locale.

---

Up to this point I am unable to get anything useful from
locale.h on my C99 Windows compiler, so I carry on with the idea of
testing all the possible combinations of negative and positive
numbers inside the integer range.

I've imagined many solutions to test the correctness of the generated
strings. One of them consists in generating the strings from
-2,147,483,648 to +2,147,483,647 using 10 nested loops from 0 to 9, except
the most external one, and a lookup table of 10 char elements with the
digits "0" => "9".

Building the strings this way should be fast and reliable enough to use
them for comparing the results I get from the itoas() function to test.

I'll work on it and see if the task is a viable one and the performance is
good enough to attach it to the testpad.

If you have any better idea, or something to warn me about you are
always welcome.

Bye for now

A pre-test looks promising:

Code:

---


                    Testing version : Nested_chars
                ------------------------------------
 Testing on Intel Core 2 Duo E6600 2.4 Ghz // IA32
 OS = Windows 7 Ultimate 64 bit  --  Compiler = Pelles C 6.00.4

 Testing the numbers from: 0  to  4,000,000,000

 The generating process has taken:  12,933 ms  to perform the whole cycle

---

with this nested loops:

Code:

---

    for (digit[0] = 0; digit[0] < four; digit[0]++){
        for (digit[1] = 0; digit[1] < ten; digit[1]++){
            for (digit[2] = 0; digit[2] < ten; digit[2]++){
                  for (digit[3] = 0; digit[3] < ten; digit[3]++){
                      for (digit[4] = 0; digit[4] < ten; digit[4]++){
                          for (digit[5] = 0; digit[5] < ten; digit[5]++){
                                  for (digit[6] = 0; digit[6] < ten; digit[6]++){
                                  for (digit[7] = 0; digit[7] < ten; digit[7]++){
                                      for (digit[8] = 0; digit[8] < ten; digit[8]++){
                                          for (digit[9] = 0; digit[9] < ten; digit[9]++){
                                                times++;
                                              } // end digit[9] for
                                          } // end digit[8] for
                                  } // end digit[7] for
                                  } // end digit[6] for
                          } // end digit[5] for
                      } // end digit[4] for
                  } // end digit[3] for
            } // end digit[2] for         
          } // end digit[1] for
    } // end digit[0] for

---

Of course now there are a lot of details to deal with, but
the whole is going to take less than 10' I guess.

Code:

---

void bar( char s[], long l )
{
    char buf[ BUFSIZ ] = {0};
    char *p = buf, *q = s;
    size_t comma = 0, trail = 0;
   
    sprintf( buf, "%ld", l );

    if( *p == '-' )
        *q++ = *p++;
   
    for( trail = strlen( p ) % 3; trail > 0; trail-- )
    {
        *q++ = *p++;
    }

    for( comma = strlen( p ) / 3; comma > 0; comma-- )
    {
        *q++ = ',';
        *q++ = *p++;
        *q++ = *p++;
        *q++ = *p++;
    }
    *q = '\0';
}

---

Quzah.

Quote:

---

Originally Posted by quzah

Code:

---

void bar( char s[], long l )
{
    char buf[ BUFSIZ ] = {0};
    char *p = buf, *q = s;
    size_t comma = 0, trail = 0;
   
    sprintf( buf, "%ld", l );

    if( *p == '-' )
        *q++ = *p++;
   
    for( trail = strlen( p ) % 3; trail > 0; trail-- )
    {
        *q++ = *p++;
    }

    for( comma = strlen( p ) / 3; comma > 0; comma-- )
    {
        *q++ = ',';
        *q++ = *p++;
        *q++ = *p++;
        *q++ = *p++;
    }
}

---

Quzah.

---

Hi quzah. Did you test it? how long it is going to take for the
whole range of integers? Did you see my previous post?

The use of:

Code:

---

    sprintf( buf, "%ld", l );

---

makes me think it is going to be quite slow.:confused:

Edit: the simple sprintf() cycle takes:

Code:

---


                    Testing version : Sprintf()
                ------------------------------------
 Testing on Intel Core 2 Duo E6600 2.4 Ghz // IA32
 OS = Windows 7 Ultimate 64 bit  --  Compiler = Pelles C 6.00.4

 Testing the numbers from: 0  to  100,000,000

 The generating process has taken:  43,633 ms  to perform the whole cycle

---

using this code:

Code:

---

    for (x = 0; x < times; x++){
        sprintf( buffer, "%ld", x );
    } // end x for

---

quite slow indeed for testing 4 billion combinations it is going to take
more or less 20' by itself.

I wasn't doing it for speed. I was just having fun.

There's also two calls to strlen which could be reduced to one, or you could modify the sprintf line to count its length for you using the n modifier:

Code:

---

sprintf( buf, "%ld%n", l, &length );

---

Edit: Your testpad fails to clean the buffer it passes between calls.


Quzah.

Quote:

---

Originally Posted by quzah

I wasn't doing it for speed. I was just having fun.

There's also two calls to strlen which could be reduced to one, or you could modify the sprintf line to count its length for you using the n modifier:

Code:

---

sprintf( buf, "%ld%n", l, &length );

---

Edit: Your testpad fails to clean the buffer it passes between calls.


Quzah.

---

Good to see that you're having fun. Enjoy.

The cleaning is supposed to be done inside the function, when
itoas() will be completed. :cool: Or not?

Code:

---

void itoas( long l, char s[] )
{
    char buf[ BUFSIZ ] = {0};
    char *p = buf, *q = s;
    size_t comma = 0, trail = 0;
    int len;
   
    sprintf( buf, "%ld%n", l, &len );

    if( *p == '-' )
    {
        *q++ = *p++;
        len--;
    }

    for( trail = len % 3; trail > 0; trail-- )
    {
        *q++ = *p++;
    }

    for( comma = len / 3; comma > 0; comma-- )
    {
        if( len != 3 )
            *q++ = ',';
        *q++ = *p++;
        *q++ = *p++;
        *q++ = *p++;
    }
    *q = '\0';
}

---

It doesn't seem to change its speed by much if I get rid of strlen and use the built in %n. (The if check fixes an issue with three digit numbers getting a comma.) But this was really just about making a simple version, not for speed.

Quzah.

Quote:

---

Originally Posted by quzah

Code:

---

void itoas( long l, char s[] )
{
    char buf[ BUFSIZ ] = {0};
    char *p = buf, *q = s;
    size_t comma = 0, trail = 0;
    int len;
   
    sprintf( buf, "%ld%n", l, &len );

    if( *p == '-' )
    {
        *q++ = *p++;
        len--;
    }

    for( trail = len % 3; trail > 0; trail-- )
    {
        *q++ = *p++;
    }

    for( comma = len / 3; comma > 0; comma-- )
    {
        if( len != 3 )
            *q++ = ',';
        *q++ = *p++;
        *q++ = *p++;
        *q++ = *p++;
    }
    *q = '\0';
}

---

It doesn't seem to change its speed by much if I get rid of strlen and use the built in %n. (The if check fixes an issue with three digit numbers getting a comma.) But this was really just about making a simple version, not for speed.

Quzah.

---

In order to test 4.2 billion combinations I prefer to develop a
faster one, but your version is good for didactical purposes :cool: