Thread: is there anything technicaly wrong with this

1. 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. sorry meant to say the official answer also declares iLimit as size_t what ever size_t is

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

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

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

9. is there a command or utility for mx Linux (Debian based) that shows memory usage at runtime

Popular pages Recent additions