1. Forum
  2. Usenet
  3. COMP.LANG.C

  • A very slow program

    From Student Project@21:1/5 to All on Sun Sep 15 22:45:59 2024
    XPost: alt.comp.lang.c

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

    #define RUNS 1000
    #define SIZE 1000000

    int mark[SIZE];

    int main(void)
    {
    time_t start, finish;
    int i, loop, n, num;

    time(&start);

    /* This loop finds the prime numbers between 2 and SIZE */
    for (loop = 0; loop < RUNS; ++loop)
    {
    for (n = 0; n < SIZE; ++n)
    mark[n] = 0;
    /* This loops marks all the composite numbers with -1 */
    for (num = 0, n = 2; n < SIZE; ++n)
    if (!mark[n])
    {
    for (i = 2 * n; i < SIZE; i += n)
    mark[i] = -1;
    ++num;
    }
    }
    time(&finish);
    printf("Program takes an average of %f seconds "
    "to find %d primes.\n",
    difftime(finish, start) / RUNS, num);
    }
    /*
    The result on my slow machine:
    Program takes an average of 0.018000 seconds to find 78498 primes.
    */

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Kaz Kylheku@21:1/5 to Student Project on Mon Sep 16 02:44:10 2024
    XPost: alt.comp.lang.c

    On 2024-09-15, Student Project <student@invalid.invalid> wrote:
    /*
    The result on my slow machine:
    Program takes an average of 0.018000 seconds to find 78498 primes.
    */

    Use the clock() function, to get clock_t time values. They usually
    have better granularity than time_t. The resolution of clock_t is
    given by the CLOCKS_PER_SEC constant. There is no difftime equivalent;
    you just subtract the earlier clock_t from the later one, and divide by CLOCKS_PER_SEC to get seconds. This is usually done in floating-point:

    clock_t start = clock();
    clock_t end = clock();
    double interval = (end - start) / (double) CLOCKS_PER_SEC;

    (This assumes that CLOCKS_PER_SEC is in range of double; if that
    were not the case, we get undefined behavior. I'm only pointing this
    pointless concern because if I don't, someone else will.)

    --
    TXR Programming Language: http://nongnu.org/txr
    Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
    Mastodon: @Kazinator@mstdn.ca

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Paul@21:1/5 to Student Project on Mon Sep 16 01:22:09 2024
    XPost: alt.comp.lang.c

    On Sun, 9/15/2024 6:45 PM, Student Project wrote:
    #include <time.h>
    #include <stdio.h>

    #define RUNS 1000
    #define SIZE 1000000

    int mark[SIZE];

    int main(void)
    {
    time_t start, finish;
    int i, loop, n, num;

    time(&start);

    /* This loop finds the prime numbers between 2 and SIZE */
    for (loop = 0; loop < RUNS; ++loop)
    {
    for (n = 0; n < SIZE; ++n)
    mark[n] = 0;
    /* This loops marks all the composite numbers with -1 */
    for (num = 0, n = 2; n < SIZE; ++n)
    if (!mark[n])
    {
    for (i = 2 * n; i < SIZE; i += n)
    mark[i] = -1;
    ++num;
    }
    }
    time(&finish);
    printf("Program takes an average of %f seconds "
    "to find %d primes.\n",
    difftime(finish, start) / RUNS, num);
    }
    /*
    The result on my slow machine:
    Program takes an average of 0.018000 seconds to find 78498 primes.
    */


    Good prime code, comes with its own timing routines :-)

    http://cr.yp.to/primegen.html

    http://cr.yp.to/primegen/primegen-0.97.tar.gz

    Paul

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Paul@21:1/5 to Vir Campestris on Wed Oct 2 06:37:46 2024
    XPost: alt.comp.lang.c

    On Wed, 10/2/2024 6:16 AM, Vir Campestris wrote:
    On 16/09/2024 06:22, Paul wrote:
    Good prime code, comes with its own timing routines 🙂

    http://cr.yp.to/primegen.html

        http://cr.yp.to/primegen/primegen-0.97.tar.gz

       Paul

    I pricked my ears up when I saw this - I've been spending a quite ridiculous amount of time tuning prime code.

    Happily for my sanity the program I published over on comp.lang.c++(1) is quite a bit faster than that one. On the other hand, I'm tuning for modern processors, and the comment in there say inter alia "It generates the 50847534 primes up to 1000000000
    in just 8 seconds on a Pentium II-350"

    I don't remember the last time I saw one of those.

    <https://en.wikipedia.org/wiki/List_of_Intel_Pentium_II_processors>

    tells me it was release in 1998...

    Andy

    I started on PCs, with a Celery 300 for home use.
    That was the one that didn't have cache.

    And the generation before I got a machine, there
    were cache DIMMs for adding a cache function, and
    the cache DIMM in some cases, only covered half
    the address space, instead of covering the whole
    thing. The things you have to put up with.

    Paul

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Vir Campestris@21:1/5 to Paul on Wed Oct 2 11:16:37 2024
    XPost: alt.comp.lang.c

    On 16/09/2024 06:22, Paul wrote:
    Good prime code, comes with its own timing routines 🙂

    http://cr.yp.to/primegen.html

    http://cr.yp.to/primegen/primegen-0.97.tar.gz

    Paul

    I pricked my ears up when I saw this - I've been spending a quite
    ridiculous amount of time tuning prime code.

    Happily for my sanity the program I published over on comp.lang.c++(1)
    is quite a bit faster than that one. On the other hand, I'm tuning for
    modern processors, and the comment in there say inter alia "It generates
    the 50847534 primes up to 1000000000 in just 8 seconds on a Pentium II-350"

    I don't remember the last time I saw one of those.

    <https://en.wikipedia.org/wiki/List_of_Intel_Pentium_II_processors>

    tells me it was release in 1998...

    Andy
    --

    (1) See thread "Sieve of Eratosthenes optimized to the max" and look for
    a post from me which is quite big

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Janis Papanagnou@21:1/5 to Student Project on Wed Oct 2 16:41:32 2024
    On 16.09.2024 00:45, Student Project wrote:
    [ snip C program ]
    /*
    The result on my slow machine:
    Program takes an average of 0.018000 seconds to find 78498 primes.
    */

    Note, this is the same runtime magnitude that Unix'es 'primes'
    command needs to run on 1000000 numbers to create 78498 primes
    (0m00.01s) [on my very old (and slow) Unix system].

    Is there a point in still writing own programs for that task?
    I see some point when examining performance optimizations (as
    someone downthread seems to have done). For cryptography there's
    certainly demands for yet faster (parallelized) algorithms - if
    quantum system algorithms don't make it superfluous (lately, or
    in near future). But for cryptography you'd anyway need larger
    numeric domains, beyond '[long]* integer' arithmetics. (I don't
    know whether the [downthread posted] C++ code was designed to
    support arbitrary length arithmetics.)

    Optimized algorithms of new methods alone might not be a C topic.
    But given your posting name, "Student Project", I suppose you're
    anyway just using it as example for learning the C language?

    For ordinary users it's probably sufficient to use an existing
    program; on Unix 'primes 1 1000000000' runs in about 8 seconds.
    And it's checking 2^32 numbers in 50 seconds (including 'wc'
    and creating output [suppressed by redirection]), generating
    50847534 primes. A simple prime test of some "arbitrary large"
    number runs in no time, as does factorization of numbers with
    the Unix'es 'factor' program. Just a simple command line call.
    That existing 'primes' program also has some limit; the man page
    documents a value of 4294967295, but no error message is created
    for values up to around 1.8446744*10^19 on my system.

    Janis

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Paul@21:1/5 to Bonita Montero on Thu Oct 3 17:25:14 2024
    XPost: alt.comp.lang.c

    On Wed, 10/2/2024 8:44 AM, Bonita Montero wrote:
    Ive developed a Sieve of Erastosthenes in C++20 with an unbeaten
    performance. With this code I get all primes <= 2 ^ 32 in 140ms
    on my AMD 7950X 16-core Zen4-system.

    Why not measure against the programs provided in a Linux distro ?

    $ time primesieve 1e6
    Sieve size = 256 KiB
    Threads = 1
    100%
    Seconds: 0.000
    Primes: 78498

    real 0m0.002s <=== Without printing the numbers, is pretty fast
    user 0m0.000s
    sys 0m0.000s

    $ time primesieve 1e6 --print > NUL

    real 0m0.009s <=== Without Terminal to slow I/O, is in the Unix ballpark user 0m0.005s
    sys 0m0.000s

    $ time primesieve 4294967295
    Sieve size = 256 KiB
    Threads = 16 <=== 5700G Zen3 (8C 16T), stock speed, execution under WSL2
    100%
    Seconds: 0.072
    Primes: 203280221

    real 0m0.073s
    user 0m0.869s
    sys 0m0.009s

    Paul

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)