rhle.freak said:
Quote:
>
/*This code finally compiles as a 'c' code
Yes, it does, at last. Well done. :-)
Quote:
and is much faster
Oh deary deary me. I killed it after two minutes because it was so
mind-numbingly slow, even though I was redirecting output to a file. (It
had got as far as 996263.)
And yet, in theory, it should be quicker than my own prime number generator,
which runs in 0.2 seconds for the same range (up to 2,000,000).
So let's see if we can't speed it up for you, without changing your basic
method (i.e. trial divide by known primes).
But first, let's answer your questions:
Quote:
/*Regarding indentation ..if it is a problem again...please do help
yourselves! ...
If you are having problems with code becoming magically unindented on
Usenet, you can fix that by using spaces instead of tabs in your source
code. Good editors can swap this over for you.
Quote:
Please let me
know of any potential errors that i am still missing out on
One more question....if i don't free up the memory allocated at the end
of the program ,what happens to the numbers in the stack ,does this
*callousness* on my part corrupt the memory ?? */
If you're using a good OS (and even Windows probably counts as a good OS
nowadays), it will reclaim all the memory used by your program when you
quit. Nevertheless, it's good practice to free up the memory correctly, as
programs have a habit of becoming functions. This is because programming
is, in one sense at least, the art of building up big concepts from little
ones. When you turn a program into a function, and then call that function
in a loop, your unimportant, laughably trivial memory leaks can suddenly
become a serious and expensive maintenance headache.
Okay - to the code!
The first thing I'm going to do is set a benchmark. Since I haven't got all
year, I'm going to reduce your top end from 2,000,000 to 300,000.
Redirecting your results to /dev/null, I get your base runtime for 300,000
as 15 seconds on my system. (For 100,000 it was 1.8 seconds, so this is not
a linear relationship by any means.)
Oh, and your program doesn't include 2 amongst the primes.
So let's get our hands dirty.
The first thing to do is get that number list properly abstracted. I made a
trivial change to the program (to divide by smaller numbers first) and the
whole thing broke, so I'd like to make that whole area more robust.
What characteristics do we need in our prime number list? Well, it must be
able to store values in the order they're given. It must be extensible. It
must be iterable (that is, we need to be able to loop through its data
easily). In fact, it would appear that we are best served by an array
rather than a linked list. But a large array can clog up memory quite
easily. So how about a linked list of relatively small arrays? Well, the
possibilities are probably endless, but the implementation is a detail
which we might decide to change later. What really matters is the
interface. So let's design that, in the firm and certain knowledge that all
prime numbers can be represented by an unsigned long int. :-)
We will postulate some type, t_PrimeList, and for now we won't worry about
the underlying details.
We will need to be able to create such a list:
t_PrimeList *PrimeListCreate(void);
And we will need to be able to destroy it:
void PrimeListDestroy(t_PrimeList **);
We should be able to add a number to the list:
int PrimeListAdd(t_PrimeList *, unsigned long new);
PrimeListAdd may reject an entry if it can tell that the entry is not prime,
or if there is insufficient storage for the new entry.
How many numbers are there in the list?
size_t PrimeListCount(t_PrimeList *);
Get the number at a given position:
unsigned long PrimeListRetrieve(t_PrimeList *, size_t);
FOR NOW, we will implement the actual list as a darn great array (because I
have other stuff to do Real Soon Now). Later, if I get time, we'll mod it
into a linked list. This Will Not Affect The Main Program!
Now I can show you main - but beware that this will not yet compile.
int main(void)
{
unsigned long int candidate = 0;
unsigned long n = 0;
unsigned long maxn = (MAX + 5) / 6;
t_PrimeList *primes = PrimeListCreate();
if(primes != NULL)
{
/* two special cases (not really all that special,
but they don't fit our algorithm very well!) */
PrimeListAdd(primes, 2);
PrimeListAdd(primes, 3);
candidate = 5;
for(n = 0; n < maxn; n++)
{
PrimeListAdd(primes, candidate);
candidate += 2;
PrimeListAdd(primes, candidate);
candidate += 4;
}
maxn = PrimeListCount(primes);
for(n = 0; n < maxn; n++)
{
printf("%lu\n", PrimeListRetrieve(primes, n));
}
PrimeListDestroy(&primes);
}
return 0;
}
As you can see, main() betrays not a single hint of the underlying data
structure used by t_PrimeList. Why should it care, after all?
Note, too, that we only test candidates that are either one less than, or
one more than, a multiple of six. That means we have to put 2 and 3 into
our list separately, since they don't fit this pattern.
In case this shortcut isn't clear to you, think of it this way. In any given
list of six consecutive integers starting at a multiple of six:
n * 6 + 0 is even
n * 6 + 1 is neither even nor a multiple of 3
n * 6 + 2 is even
n * 6 + 3 is a multiple of 3
n * 6 + 4 is even
n * 6 + 5 is neither even nor a multiple of 3
Now, n * 6 + 1 and n * 6 + 5 may not be prime, it's true. But apart from the
exceptions already noted above, they are the only ones that *might* be
prime.
Okay, so I implemented all this (be patient - I'll show you the code in a
minute), and (with output redirected to /dev/null to keep the comparison
fair) I got through those 300000 candidates in not 15 seconds but 0.136.
The full two million took 1.26 seconds. Still not quite as fast as my
current generator, but pretty quick nonetheless when compared to your
original version!
If you increase MAX to greater than 2000000, you'll need to increase the
array size too - which is a pain, so our next iteration will deal with
that, if I get time. For now, though, the important thing to communicate is
that you can play with the implementation to your heart's content, and you
*don't have to change main() when you change the implementation!*. Just
leave the interface and semantics alone, and you can do what you like
underneath.
And finally, here's the code:
#include <stdio.h>
#include <stdlib.h>
#define MAX 2000000UL
struct t_PrimeList_
{
unsigned long prime[150000UL]; /* good for a MAX of 2000000UL */
size_t count;
};
typedef struct t_PrimeList_ t_PrimeList;
t_PrimeList *PrimeListCreate(void)
{
t_PrimeList *new = malloc(sizeof *new);
if(new != NULL)
{
memset(new->prime, 0, sizeof new->prime);
new->count = 0;
}
return new;
}
void PrimeListDestroy(t_PrimeList **old)
{
if(old != NULL && *old != NULL)
{
free(*old);
*old = NULL;
}
}
/* this function *only* validates that the new prime candidate is
* not divisible by any candidate already in the list. If you add
* 6 before you add 2 and 3, it will accept 6 as a prime. So just
* add the candidates in order, okay? (The trial division does,
* in any case, assume that they are in order.)
*/
int PrimeListAdd(t_PrimeList *list, unsigned long new)
{
int rc = 1; /* 1 = reject, 0 = accept */
if(list != NULL &&
list->count + 1 < sizeof list->prime / sizeof list->prime[0])
{
size_t n;
rc = 0;
for(n = 0;
rc == 0 && /* not found a prime yet */
n < list->count && /* haven't run out of trial divisors */
list->prime[n] * list->prime[n]
<= new; /* composite still possible */
n++)
{
if(new % list->prime[n] == 0)
{
rc = 1;
}
}
if(0 == rc)
{
list->prime[list->count++] = new;
}
}
return rc;
}
size_t PrimeListCount(t_PrimeList *list)
{
size_t count = 0;
if(list != NULL)
{
count = list->count;
}
return count;
}
unsigned long PrimeListRetrieve(t_PrimeList *list, size_t pos)
{
unsigned long val = 0;
if(list != NULL && list->count pos)
{
val = list->prime[pos];
}
return val;
}
int main(void)
{
unsigned long int candidate = 0;
unsigned long n = 0;
unsigned long maxn = (MAX + 5) / 6;
t_PrimeList *primes = PrimeListCreate();
if(primes != NULL)
{
/* two special cases (not really all that special,
but they don't fit our algorithm very well!) */
PrimeListAdd(primes, 2);
PrimeListAdd(primes, 3);
candidate = 5;
for(n = 0; n < maxn; n++)
{
PrimeListAdd(primes, candidate);
candidate += 2;
PrimeListAdd(primes, candidate);
candidate += 4;
}
maxn = PrimeListCount(primes);
for(n = 0; n < maxn; n++)
{
printf("%lu\n", PrimeListRetrieve(primes, n));
}
PrimeListDestroy(&primes);
}
return 0;
}
--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at the above domain, - www.
