Testpad for itoa()

This is a discussion on Testpad for itoa() within the C Programming forums, part of the General Programming Boards category; The previous thread is getting too complex to manage, so I prefer to start a new one with a clean ...

  1. #1
    Registered User
    Join Date
    Jun 2010
    Posts
    182

    Testpad for itoas()

    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
    Attached Files Attached Files
    Last edited by frktons; 07-09-2010 at 04:49 PM.

  2. #2
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,422
    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!
    Last edited by Elysia; 07-08-2010 at 06:37 PM.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  3. #3
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    He probably means something like:

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


    Quzah.
    Last edited by quzah; 07-08-2010 at 06:44 PM.
    Hope is the first step on the road to disappointment.

  4. #4
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,627
    Umm, what about what iMalc has said, frktons:

    Quote Originally Posted by iMalc View Post
    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 View Post
    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?
    Last edited by whiteflags; 07-08-2010 at 08:29 PM.

  5. #5
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,167
    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.

  6. #6
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    Quote Originally Posted by Elysia View Post
    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".

  7. #7
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    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.

  8. #8
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,627
    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');
        }
    }

  9. #9
    Password:
    Join Date
    Dec 2009
    Location
    NC
    Posts
    587
    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.

  10. #10
    Registered User
    Join Date
    Jun 2010
    Posts
    182
    @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:

    Quote Originally Posted by whiteflags View Post
    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.
    Last edited by frktons; 07-09-2010 at 07:34 AM.

  11. #11
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,627
    >> 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.

  12. #12
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,422
    Quote Originally Posted by User Name: View Post
    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?
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  13. #13
    Registered User
    Join Date
    Jun 2010
    Posts
    182
    @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.
    Last edited by frktons; 07-09-2010 at 11:30 AM.

  14. #14
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,167
    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.

  15. #15
    Registered User
    Join Date
    Jun 2010
    Posts
    182
    Quote Originally Posted by cyberfish View Post
    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.
    Last edited by frktons; 07-09-2010 at 01:14 PM.

Page 1 of 7 1234567 LastLast
Popular pages Recent additions subscribe to a feed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21