Thread: Various optimization questions

  1. #16
    Amazingly beautiful user.
    Join Date
    Jul 2005
    Location
    If you knew I'd have to kill you
    Posts
    254
    Just wondering, is there anywhere we can join in on the competition, or is it closed?
    Programming Your Mom. http://www.dandongs.com/

  2. #17
    </3 Segfaults
    Join Date
    Jul 2007
    Posts
    27
    It's closed. Sorry.

    I have no clue what sieves are, so sorry about that too. =\

    Code:
    //////////
    //Kevin Yin
    //July 12, 2007
    //Lists of primes
    
    //Speedups possible:
    //
    //maybe instead of "= 0", "^= itself"
    // -	cprogramming.com forums say "= 0"  is faster
    //
    //hardcoding in imn and smn
    //
    //maybe having a miraculous way of using mods to speed up the array
    // -	looked up Sieve of Atkin, not possible
    
    using namespace std;
    
    #include <iostream>
    
    int main()
    {
    	int limit; //highest value
    	int increm; //value checked
    	int small; //increm checking increm
    	int square = 0; //square root of limit
    	bool cor = true; //whether to output
    	bool *array = NULL; //for speeding things up
    	int acrem; //for the array
    	int alim; //for the array, upper bound
    	int smn = 2, imn = 4; //how much to increm them by
    	//imn is reversed, so keep it like this
    
    	cout << "This program outputs prime numbers up to a number.\n";
    	cout << "Please insert that number.\n";
    	cin >> limit;
    
    	if (limit <= 1)
    	{
    		cout << "Don't be stupid.\n";
    		return 0;
    	}
    
    	alim = limit / 2 + 1;
    
    	array = new bool[alim];
    
    	for (acrem = 0; acrem < alim; acrem++)
    		array[acrem] = true;
    
    	//yes, what a cheater I am =)
    	cout << "2\n3";
    
    	for (increm = 5; increm <= limit; increm += imn) //incrementing the div by 2, from 7
    	{
    		//changes imn
    		imn = 2 + (imn == 2) * 2;
    
    		if (array[increm / 2]) //seeing if the array spot for the div is 0
    		{
    			//making a square root
    			while (square * square <= increm)
    				square++;
    
    			//the actual doing
    			for (small = 5; small <= square; small += smn) //incrementing small from 5, by 2
    			{
    				if (array[small / 2]) //if small is divisible
    					if (!(increm &#37; small)) //seeing if increm is divisible by small
    					{
    						//sets cor to 0
    						cor = false;
    
    						//updates the array
    						if (array[small * 3 / 2])
    							for (acrem = small * 3 / 2; acrem <= alim; acrem += small)
    								array[acrem] = false;
    						break;
    					}
    				smn = 2 + (smn == 2) * 2;
    			}
    
    			smn = 2;
    
    			//displaying and updating
    			if (cor)
    			{
    				cout << '\n' << increm;
    
    				//updates the array
    				for (acrem = increm * 3 / 2; acrem <= alim; acrem += increm)
    					array[acrem] = false;
    			}
    			cor = true;
    		}
    	}
    	cout << '\n';
    }
    The principle of smn and imn are that

    0 _ 2 3 4 _ 6 _ 8 9 10 _ 12 _

    (see a pattern?) They add 2, then 4, then 2...

    The small divisor starts at 5 because the large divisor automatically skips numbers divisible by 2 and 3.

    The array only stores odd numbers.

    It's currently working with a max because I don't know what I should set the max at for 20 seconds so far.

    Lastly, if you feel that you don't want to scroll through the code, I can just add it to cpp.sf.net and put a link here.
    Last edited by Differ; 07-31-2007 at 04:17 PM. Reason: UPDATE TO THE CODE

  3. #18
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    I have no clue what sieves are, so sorry about that too. =\
    That is the point Salem made earlier: before you do micro-optimisations (and if possible, before you even start coding), do the major optimisation by using a fast algorithm.

    The hybrid approach I suggested has a problem: it "wastes" time by generating a list of primes, so it only wins out when the range becomes sufficiently large. As such, for a PHP based contest that I entered a couple of years back, it had pretty bad performance as the time limit for the primality testing was 3 seconds. However, I digged up some old C++ code in which I had implemented that algorithm and tested against your code, and even as soon as the millionth prime range my program was noticeably faster than yours.

    Incidentally, the C++ keywords for true and false are entirely lowercase, and you need to qualify the names from the std namespace.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  4. #19
    </3 Segfaults
    Join Date
    Jul 2007
    Posts
    27
    Wait, so it's standard to use lowercase words?

    I don't know what's going on, but GCC doesn't seem to need the std namespace. I got used to it (coding in Windows) a project member took it out, and my code still worked fine.

    Mine wastes time generating a list, but instead of listing primes, it has an array in which each member corresponds to one odd number. So in the end, you still have to check the array, and check every single box (1 or 0) until you either hit a valid divisor or until you hit the square root of the number.

    I was dead wrong that sqrt() was faster than my while loop. The while loop makes the code run 40&#37; faster.

  5. #20
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Wait, so it's standard to use lowercase words?
    Yes, in C++.

    I don't know what's going on, but GCC doesn't seem to need the std namespace. I got used to it (coding in Windows) a project member took it out, and my code still worked fine.
    Rather unusual. I tested with the MinGW port of g++ 3.4.2
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #21
    </3 Segfaults
    Join Date
    Jul 2007
    Posts
    27
    Same here: the MinGW I have needs the std namespace. I started with the package that came with Dev-C++, then overwrote it with the MinGW from the CVS.

    For some reason, my MinGW doesn't let me declare variables anywhere inside loops (initialization fields are banned too), and doesn't let me declare file I/O pointers anywhere but in the top level inside of functions. So it really stinks, and I'm really not sure what kind of compiler it is now.

    But my GCC works fine.

    Is null also supposed to be lowercase?
    Last edited by Differ; 07-30-2007 at 10:39 PM.

  7. #22
    Captain - Lover of the C
    Join Date
    May 2005
    Posts
    341
    Don't quote me on that... ...seriously

  8. #23
    </3 Segfaults
    Join Date
    Jul 2007
    Posts
    27
    Quote Originally Posted by Brad0407 View Post
    I guess I used a faster version of the Sieve of Eratosthenes.

  9. #24
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Is null also supposed to be lowercase?
    No, uppercase, though you can also use 0.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  10. #25
    Registered User
    Join Date
    Oct 2001
    Posts
    2,129
    NULL is a define, not a keyword.

  11. #26
    The larch
    Join Date
    May 2006
    Posts
    3,573
    For some reason, my MinGW doesn't let me declare variables anywhere inside loops (initialization fields are banned too), and doesn't let me declare file I/O pointers anywhere but in the top level inside of functions. So it really stinks, and I'm really not sure what kind of compiler it is now.
    It sounds like you are compiling as C, not C++. Do your source files have .cpp extension or simply .c? Or may-be in your IDE you have chosen to compile files as C (e.g specified a project to be C project).
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  12. #27
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    You do realize that if you divide by already found primes rahter than "all" numbers, you're going to benefit. So keep a list of the primes you've found, and use them to divide by, rather than ALL numbers.

    --
    Mats

  13. #28
    </3 Segfaults
    Join Date
    Jul 2007
    Posts
    27
    Quote Originally Posted by matsp View Post
    You do realize that if you divide by already found primes rahter than "all" numbers, you're going to benefit. So keep a list of the primes you've found, and use them to divide by, rather than ALL numbers.

    --
    Mats
    I already did that. What do you think my array is for?

  14. #29
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    I can't even get it to run in cygwin
    Code:
    $ g++ prime_yin.cpp
    $ ./a.exe
    This program outputs prime numbers up to a number.
    Please insert that number.
    100
    2
      23224 [main] a 3140 _cygtls::handle_exceptions: Error while dumping state (probably corrupted stack)
    Segmentation fault (core dumped)
    I was going to time mine against yours.
    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.

  15. #30
    </3 Segfaults
    Join Date
    Jul 2007
    Posts
    27
    Same here, only seems to work with GCC on Linux.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. questions....so many questions about random numbers....
    By face_master in forum C++ Programming
    Replies: 2
    Last Post: 07-30-2009, 08:47 AM
  2. Turn Off Optimization?
    By danlee58 in forum C Programming
    Replies: 6
    Last Post: 12-10-2008, 03:52 AM
  3. A very long list of questions... maybe to long...
    By Ravens'sWrath in forum C Programming
    Replies: 16
    Last Post: 05-16-2007, 05:36 AM
  4. Trivial questions - what to do?
    By Aerie in forum A Brief History of Cprogramming.com
    Replies: 23
    Last Post: 12-26-2004, 09:44 AM
  5. questions questions questions.....
    By mfc2themax in forum A Brief History of Cprogramming.com
    Replies: 1
    Last Post: 08-14-2001, 07:22 AM