# Various optimization questions

Show 80 post(s) from this thread on one page
Page 2 of 4 First 1234 Last
• 07-30-2007
CrazyNorman
Just wondering, is there anywhere we can join in on the competition, or is it closed?
• 07-30-2007
Differ
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.
• 07-30-2007
laserlight
Quote:

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.
• 07-30-2007
Differ
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.
• 07-30-2007
laserlight
Quote:

Wait, so it's standard to use lowercase words?
Yes, in C++.

Quote:

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
• 07-30-2007
Differ
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?
• 07-30-2007
• 07-30-2007
Differ
Quote:

I guess I used a faster version of the Sieve of Eratosthenes.
• 07-30-2007
laserlight
Quote:

Is null also supposed to be lowercase?
No, uppercase, though you can also use 0.
• 07-30-2007
robwhit
NULL is a define, not a keyword.
• 07-31-2007
anon
Quote:

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).
• 07-31-2007
matsp
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
• 07-31-2007
Differ
Quote:

Originally Posted by matsp
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?
• 07-31-2007
Salem
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.
• 07-31-2007
Differ
Same here, only seems to work with GCC on Linux.
Show 80 post(s) from this thread on one page
Page 2 of 4 First 1234 Last