Thread: is there anything technicaly wrong with this

  1. #1
    Registered User
    Join Date
    Apr 2019
    Posts
    808

    is there anything technicaly wrong with this

    the task is to write a program that adds up all the prime numbers between 1 and 2,000,000

    here is my solution
    Code:
    int main()
    {
        //declare variables
        int i, j, iLimit = 2000000, iMultiples[2000000] = { 0 }; //imultiples is used to mark off multiples of i
        unsigned long long int iSum = 0;
    
        //loop from 2 to iLimit
        for ( i = 2; i < iLimit; i++ )
        {
            //check if i is a multiple of a previous itteration of i
            if ( iMultiples[i] == 0 )
            {
                //i is a new prime so add it to the running total isum
                iSum += i;
    
                //loop from i to ilimit in all multiples of i
                for ( j = i * 2; j < iLimit; j += i )
                {
                   //mark off i * j
                   iMultiples[j] = 1;
                }
            }
        }
        //print the sum of primes from 1 to ilimit to the screen
        printf("The sum of primes between 1 and %d is %llu\n", iLimit, iSum);
    
        return 0;
    }
    this runs in 0.063 seconds

    If i change the variable declarations at the top to
    Code:
    int i, j, iLimit = 2000000; 
        unsigned long long int iSum = 0;
        char iMultiples[2000000] = { '\0' }; //imultiples is used to mark off multiples of i
    ie the array is now type char it cuts the run time approximately in half

    Looking at the "official" solution they used pointers of type char and calloc'ed the memory and treated it as an array which doesn't appear to be any quicker than using a predefined array of type char so i don't see the point

  2. #2
    Registered User
    Join Date
    Apr 2019
    Posts
    808
    sorry meant to say the official answer also declares iLimit as size_t what ever size_t is

  3. #3
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,670
    > Looking at the "official" solution
    What official solution?

    One thing to bear in mind is that int iMultiples[2000000] takes up almost 8MB of stack memory.

    Total stack space is usually restricted to some handful of MB. For example, your program would be damn close to failing on my machine.
    Code:
    $ ulimit -a
    real-time non-blocking time  (microseconds, -R) unlimited
    core file size              (blocks, -c) 0
    data seg size               (kbytes, -d) unlimited
    scheduling priority                 (-e) 0
    file size                   (blocks, -f) unlimited
    pending signals                     (-i) 63267
    max locked memory           (kbytes, -l) 2034520
    max memory size             (kbytes, -m) unlimited
    open files                          (-n) 1024
    pipe size                (512 bytes, -p) 8
    POSIX message queues         (bytes, -q) 819200
    real-time priority                  (-r) 0
    stack size                  (kbytes, -s) 8192
    cpu time                   (seconds, -t) unlimited
    max user processes                  (-u) 63267
    virtual memory              (kbytes, -v) unlimited
    file locks                          (-x) unlimited
    > ie the array is now type char it cuts the run time approximately in half
    The OS doesn't hand out the whole stack allocation at the start.

    Most programs get by with a few 10's of KB of stack, because programmers know not to put very large arrays on the stack (or as demonstrated in one of your other posts, very deep recursive functions).

    A char array would use a quarter of the space (assuming sizeof int is 4), so you're going to get a lot less OS traps asking for more stack space.

    So whilst it might be correct in an abstract sense, there are some issues when run on real machines.

    > for ( i = 2; i < iLimit; i++ )
    1. You only need to go up to the square root of limit.
    2. You may as well treat 2 as a special case, it's the only even prime.
    iRootLimit = sqrt(iLimit);
    for ( i = 3 ; i < iRootLimit ; i += 2 ) // all odd numbers


    Even that is pretty poor.

    Sieve of Eratosthenes - Wikipedia
    "Sieve of Eratosthenes: algorithm steps for primes below 121 (including optimization of starting from prime's square)."
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  4. #4
    Registered User
    Join Date
    Apr 2019
    Posts
    808
    out of interest what is your machine roughly or have you tweaked your settings.
    i get this
    Code:
    $ ulimit -a
    real-time non-blocking time  (microseconds, -R) unlimited
    core file size              (blocks, -c) 0
    data seg size               (kbytes, -d) unlimited
    scheduling priority                 (-e) 0
    file size                   (blocks, -f) unlimited
    pending signals                     (-i) 30345
    max locked memory           (kbytes, -l) 64
    max memory size             (kbytes, -m) unlimited
    open files                          (-n) 1024
    pipe size                (512 bytes, -p) 8
    POSIX message queues         (bytes, -q) 819200
    real-time priority                  (-r) 0
    stack size                  (kbytes, -s) 8192
    cpu time                   (seconds, -t) unlimited
    max user processes                  (-u) 30345
    virtual memory              (kbytes, -v) unlimited
    file locks                          (-x) unlimited
    i have an i5 with 4 cores and 8 threads

  5. #5
    Registered User
    Join Date
    Apr 2019
    Posts
    808
    sorry got side tracked by ulimit. back to the program if i used dynamic memory would that get around the stack problem. or does dynamic memory still come from the stack....

    is there a simple way of overcoming this issue as im sure there are numerous applications for using large arrays to sort/ store large amounts of data for processing rather than reading it off a disk a few mb at a time

  6. #6
    Registered User
    Join Date
    Apr 2021
    Posts
    144
    You can use static storage duration to declare an array that is not allocated on the stack, and also not dynamic. Just write static char instead of char in your declaration. Beware, however, that visibility rules still apply, so if you want to use the array by name in multiple functions, you'll have to declare the array at file scope. For now, with just the one main function, you're okay.

  7. #7
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,670
    > back to the program if i used dynamic memory would that get around the stack problem.
    Dynamic memory would normally be constrained by either data segment size and/or VM size.

    > out of interest what is your machine roughly or have you tweaked your settings.
    Possibly.
    No idea when, what or why though.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  8. #8
    Registered User
    Join Date
    Feb 2019
    Posts
    1,077
    If you declare a local array and initialize it, this initialization is done at runtime, unless the object is declared as static.

    If you declare the local object as static it'll be shared with any threads using the function.

    And yes... the stack is limited and should be kept as tiny as possible. The initial size is, usually, 4 KiB~16 KiB.
    Last edited by flp1969; 05-21-2023 at 08:40 AM.

  9. #9
    Registered User
    Join Date
    Apr 2019
    Posts
    808
    is there a command or utility for mx Linux (Debian based) that shows memory usage at runtime

  10. #10

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Why so wrong numbers? As I write so wrong?
    By Dmy in forum C++ Programming
    Replies: 2
    Last Post: 07-31-2017, 02:10 PM
  2. Replies: 3
    Last Post: 11-14-2011, 06:35 PM
  3. wrong wrong with my xor function?
    By Anddos in forum C++ Programming
    Replies: 5
    Last Post: 04-26-2009, 01:38 PM
  4. whats wrong with this? no errors but wrong result
    By InvariantLoop in forum C Programming
    Replies: 6
    Last Post: 01-28-2005, 12:48 AM
  5. Replies: 9
    Last Post: 07-15-2004, 03:30 PM

Tags for this Thread