Thread: Sieve of Eratosthenes

Originally Posted by CommonTater

Before you worry about making it faster/smaller/smarter/prettier ... the first thing is to get it working *at all*... the rest qualifies as improvement.

I did get the program working, just that it works fast for numbers below 100,000, but "fast" is actually slow..

This is what kills me about the RAD crowd... they have tools and code blobs to assemble almost any program in a matter of a couple of days. But lets get real... how much testing and improvement do you think goes into that code... They are, essentially unleashing untested code onto their bosses and customers...

who are the RAD?
I just want to understand how to read algorithms..
this was my first pathetic attempt, and it didn't cross my mind to use 1's and 0's as another method..ah well

Notice how you skip over items that are not a multiple of i (marked with a comment above)? For a vector you don't have to skip anything! You index straight to and mark off exactly every multiple of i.

Am I still not skipping when I am checking if sieve[i] is 1 or 0?

Originally Posted by Eman

Am I still not skipping when I am checking if sieve[i] is 1 or 0?

Well you could call it that, but the point is that no time is taken to skip over items, you just index straight to the item and mark it off. There could be a million entries between items and it would take the same amount of time as when they were two apart.
With the list approach you had, an it++ was required to move to the next item and when you're marking off multiples of 97 say, that's quite a lot of it++ that goes on.
Granted you've already removed some of the items that you would otherwise have to skip over, but that in itself is rather slow as well due to the modulus.

I just want to understand how to read algorithms..

I would recommend to get a good book on algorithm and start reading it. You'll get some referene on where to start. I like the CLR book. It may be a pain in the ass book to carry around though, but very thorough.

Originally Posted by iMalc

With the list approach you had, an it++ was required to move to the next item and when you're marking off multiples of 97 say, that's quite a lot of it++ that goes on.

this is what I don't understand, there is a lot of it++ that goes on..
but in the recent prog i have
j+=2, I can see why moving in twos will make a bit of difference, but I still use modulus once as in the first attempt.

I don't understand why it++ is faster than j+=2, except that I skip one element..

to my inexperienced viewpoint I would say it was the erase operation that makes it slow..but I thought there would be less to traverse by deleting the item...
i didn't know the modulus was slow to use...is it not like any other operator += + - etc..

Originally Posted by CommonTater

Rapid Application Design... the art of distributing essentially untested software.

Ah, yeah I see.

Not to worry... just keep right on trying.

Be like edison... "No, I do not know how to make a lightbulb, however I have found many many ways NOT to make a lightbulb."

xD good quote (you appear to have a lot of them)..thanks will keep it in mind

I would recommend to get a good book on algorithm and start reading it. You'll get some referene on where to start. I like the CLR book. It may be a pain in the ass book to carry around though, but very thorough.

yeah, as soon as I resume college I will look for a good algo book...
However, the ones I have found are rather...scary, very scary.

Originally Posted by Eman

this is what I don't understand, there is a lot of it++ that goes on..
but in the recent prog i have
j+=2, I can see why moving in twos will make a bit of difference, but I still use modulus once as in the first attempt.

I don't understand why it++ is faster than j+=2, except that I skip one element..

to my inexperienced viewpoint I would say it was the erase operation that makes it slow..but I thought there would be less to traverse by deleting the item...
i didn't know the modulus was slow to use...is it not like any other operator += + - etc..

There is no +=2 step in the Sieve of Eratosthenes algorithm. It steps by a prime number in size, using each prime number up to sqrt(max). When that prime number is say 97, one could say that it does j+=97 in the array version. The list version by constrast would have to do ++it a lot of times, just to do the equivalent of j+=97.
Then think about what happens when the prime gets to say 457. The array version goes j+=457 and it's immediately at the next number to mark off. The list version has to step even more times than it did previously, just to step over 457 items (only some of which have been deleted) and then it finally gets to an item to mark off, or in your case - to delete. Worse still, to work out if it has stepped far enough yet, it does a modulus, which yes is slow.

The modulus operation is the same speed as division, and just as it is slower for a human to do division by hand than say addition, it is slower for a computer as well. A division circuit is much more complicated that an addition circuit because it's a much more complicated process.
In general, the longer it takes to solve an equation by hand, the longer it takes a computer.

Originally Posted by iMalc

There is no +=2 step in the Sieve of Eratosthenes algorithm. It steps by a prime number in size, using each prime number up to sqrt(max). When that prime number is say 97, one could say that it does j+=97 in the array version. The list version by constrast would have to do ++it a lot of times, just to do the equivalent of j+=97.
Then think about what happens when the prime gets to say 457. The array version goes j+=457 and it's immediately at the next number to mark off. The list version has to step even more times than it did previously, just to step over 457 items (only some of which have been deleted) and then it finally gets to an item to mark off, or in your case - to delete. Worse still, to work out if it has stepped far enough yet, it does a modulus, which yes is slow.

I would understand what you mean if the way I did it is that way..I now understand what you mean by go straight to the index and mark it off. I didn't do that..I will try that again.. I didn't mean 2's..i meant add it by the amount of the current prime...nimitzhunter's algorithm
so if j was 3 j+=3 and so on..

Code:

#include <iostream>
#include <list>
#include <vector>
#include <stdint.h>
using namespace std ; 
#define SIZE 3000000
int main()
{
	vector<int>  sieve(SIZE,1) ;
	list<int>::iterator it ;
	list<int> aSieve ;
	

	sieve[0] =0;
	sieve[1] = 0;
		
       int j=1 ;
       unsigned long int sum =0;
       int i =2;

       while(i<SIZE)
       {
			   
	
        	if(sieve[i])
	        {
				
		        aSieve.push_back(i) ;
			for(j=i;j<SIZE;j+=i)
			{
				sieve[j]=0;
			}	
		}
		i++ ;
		
      } 


       it = aSieve.begin() ; 
       while(it!=aSieve.end())
       {
           sum+=*it ;
       
           it++ ;
        }

        cout << sum ; 
        cin.get() ; 
        return 0 ;
}

In general, the longer it takes to solve an equation by hand, the longer it takes a computer.

funny, it's supposed to be the other way round..but i get you.

Originally Posted by whiteflags

I have not failed. I've just found 10,000 ways that won't work. - Edison

is that not similar to the lightbulb quote? interesting. Edison has some good quotes..

An algorithm book is an excellent reference tool which you will use when you need to use that and don't remember how. Or, you need to use something and have no ideas. Programming is not really creative for the majority of practitioners.

As for me, I do not seek to remember everything. To pick an area I try to know well: searching and sorting, since it is such a common problem. But many areas of study are bigger than just algorithms, because algorithms operate on data structures. And the real wizardry in software design is figuring out what is best to use when. A perfect example being today, you found out that your favorite data structure, the linked list, actually has drawbacks. An array like structure, vector, has drawbacks too. And many times in your programming future will you be converting to one or the other to take advantage of some performance-related boon.

Yeah, but how would I know which one to use?
by the way is finding efficient algorithms not the point today and how to use them?