Turing Beat C++ in Performance?!?!

[keyboardwalker]

WARNING A TEXT FILE WITH THE GENERATED PRIME NUMBERS WILL BE SAVED IN A .txt FILE ON YOUR COMPUTER AFTER RUNNING EITHER OF THESE

I've created an algorithm for finding the prime numbers between 1 and the number held by NUMNUMS in Turing and C++. I'm not sure as to why C++'s performance is slower than Turing's. I have a feeling that it has something to do with using vectors in the C++ version. Is there anyway to improve C++'s performance and why is this happening?

Turing:

const NUMNUMS := 1000000 var Nums : array 1 .. NUMNUMS of boolean for i : 1 .. NUMNUMS     Nums (i) := true end for Nums (1) := false for i : 2 .. NUMNUMS     if Nums (i) then         for ii : i + i .. NUMNUMS by i             Nums (ii) := false         end for     end if end for var streamnum : int open : streamnum , "theNums.txt", put for i : 1 .. NUMNUMS     if Nums (i) then         put : streamnum, i     end if end for close (streamnum) put Time.Elapsed

c++:

#include <iostream> #include <fstream> #include <vector> #include <ctime> int main () {         using namespace std;         ofstream myfile;         const int NUMNUMS = 1000000;         clock_t t;         // "Time stamps"         int t1, t2;         t = clock();         t1 = clock();         cout << "Initializing\n";         vector <bool> Nums(NUMNUMS, true);         Nums[1] = false;         cout << "Done Initializing it took " << clock () - t1 << " ms" << endl;         cout << "Deriving Prime Numbers\n";         t1 = clock ();         for (int i = 2 ; i < NUMNUMS; i ++)         {                 if (Nums[i])                 {                         for (int ii = i + i; ii < NUMNUMS; ii += i)                         {                                 Nums [ii] = false;                         }                 }         }         cout << "Done Algorithm took " << clock() - t1 << " ms" << endl;         cout << "Saving\n";         t1 = clock ();         myfile.open ("theNums.txt");         for (int i = 2 ; i < NUMNUMS; i ++)         {                 if (Nums[i])                 {                         myfile << i << endl;                 }         }         myfile.close();         cout << "Done Saving. It took: "  << clock() - t1 << " ms" << endl;         cout << "The entire program took "  << clock() - t << " ms" << endl;         return 0; }

[Insectoid]

It's cheating to use a basic type in one language and a comparatively much slower class in the other. Try rewriting the c++ code to use an array instead of a vector. C++ will have also used much less ram and produce a much smaller program.

[keyboardwalker]

Insectoid @ Fri Feb 28, 2014 8:29 pm wrote:

It's cheating to use a basic type in one language and a comparatively much slower class in the other. Try rewriting the c++ code to use an array instead of a vector. C++ will have also used much less ram and produce a much smaller program.

Agreed, but I haven't been able to make an array of 1 billion elements in C++ like I have in Turing. That's why I used vectors instead of arrays. Unless I don't know the full capabilities of arrays in C++. Which is quite likely.

[Dreadnought]

You can't allocate large arrays on the stack in C++, but the heap is a different story.

code:

bool[] MyBoolArray = new bool[NumElements];

EDIT: or you can do it ala C

code:

bool[] MyBoolArray = (bool)malloc(NumElements * sizeof(bool));

Remember that if your arrays are really large, catching bad_alloc expections or checking for null might be a good idea.

[Insectoid]

c++ can't make a 1 billion element array, but your code only tests up to 1 million and c++ can handle that just fine.

[keyboardwalker]

Insectoid @ Fri Feb 28, 2014 9:25 pm wrote:

c++ can't make a 1 billion element array, but your code only tests up to 1 million and c++ can handle that just fine.

It's only 1 Million because it would take several minutes to calculate the prime numbers between 1 and 1 Billion. I wrote it in C++ to try and reduce this processing time but it appears that it vectors aren't the way to go in this case.

[DemonWasp]

The part that makes the C++ version take forever is the endl, which forces the output stream to flush every time you add one. To avoid that, use the \n escape character.

You still need to make sure that the stream gets flushed eventually, but closing it will also do that (which is what happens in Turing).

With this change, the C++ version handily outruns the Turing version. I ran the Turing version on Windows and the C++ version on Linux in a virtual machine, and the C++ version was still more than 10x faster. The numbers output are incorrect (it looks like you are outputting microseconds and calling them milliseconds).

The problem is not with vectors, which are widely used and perform well enough for most tasks (though there are many solutions where they are less convenient than other types).

Edit: see the documentation at http://en.cppreference.com/w/cpp/io/manip/endl

[keyboardwalker]

DemonWasp @ Fri Feb 28, 2014 10:38 pm wrote:

The part that makes the C++ version take forever is the endl, which forces the output stream to flush every time you add one. To avoid that, use the \n escape character.

You still need to make sure that the stream gets flushed eventually, but closing it will also do that (which is what happens in Turing).

With this change, the C++ version handily outruns the Turing version. I ran the Turing version on Windows and the C++ version on Linux in a virtual machine, and the C++ version was still more than 10x faster. The numbers output are incorrect (it looks like you are outputting microseconds and calling them milliseconds).

The problem is not with vectors, which are widely used and perform well enough for most tasks (though there are many solutions where they are less convenient than other types).

Edit: see the documentation at http://en.cppreference.com/w/cpp/io/manip/endl

Your suggestion made a huge difference to saving speeds. As for the timing I think it was close if not the correct time in the C++ but I have calculated it differently now. I'm fairly sure that the times are correct and in milliseconds. You can check the references to see what I mean or to correct me again :p. I implemented arrays and there was a huge performance increase. Here's the updated version. Thank you to everyone who made suggestions.

c++:

#include <iostream> #include <fstream> #include <vector> #include <ctime> int main () {         using namespace std;         ofstream myfile;         const int NUMNUMS = 1000000;         clock_t t;         int t1;         t = clock();         t1 = clock();         cout << "Initializing\n";         bool *Nums = new bool[NUMNUMS];         for (int i = 0; i < NUMNUMS; i ++)         {                 Nums[i] = true;         }         //vector <bool> Nums(NUMNUMS, true);         Nums[1] = false;         cout << "Done Initializing it took " << (float)(clock () - t1)/CLOCKS_PER_SEC * 1000 << " ms" << endl;         cout << "Deriving Prime Numbers\n";         t1 = clock ();         for (int i = 2 ; i < NUMNUMS; i ++)         {                 if (Nums[i])                 {                         for (int ii = i + i; ii < NUMNUMS; ii += i)                         {                                 Nums [ii] = false;                         }                 }         }         cout << "Done. Algorithm took: " << (float)(clock() - t1)/CLOCKS_PER_SEC * 1000 << " ms" << endl;         cout << "Saving\n";         t1 = clock ();         myfile.open ("theNums1.txt");         for (int i = 2 ; i < NUMNUMS; i ++)         {                 if (Nums[i])                 {                         myfile << i << "\n";                 }         }         myfile.close();         cout << "Done Saving. It took: "  << (float)(clock() - t1)/CLOCKS_PER_SEC * 1000 << " ms" << endl;         cout << "The entire program took "  << (float)(clock() - t)/CLOCKS_PER_SEC * 1000 << " ms" << endl;         delete [] Nums;         cout << "Press any key";         cin.get();         return 0; }

[linuxp]

The problem is vector<bool>

In c++ vector<bool> is a specialized version of vector.

normal vector<type> is just a plain array of
[type,type,type]

vector<bool> is a memory optimized container.
each bool takes 1 bit instead of 1 byte.

The result is 1/8 memory but longer operation time.

if you need a normal array of bool
use vector<char> or bool[]

[DemonWasp]

linuxp @ Sat Mar 01, 2014 2:24 pm wrote:

The problem is vector<bool>

No, the problem he was having is because endl unexpectedly flushes the output stream. The operations on vector<bool> aren't that much slower than standard.

[nullptr]

Quote:

c++:

for (int ii = i + i; ii < NUMNUMS; ii += i) {         Nums [ii] = false; }

One more thing -- instead of starting at i + i, you can start at i * i to get faster code in both languages.

[keyboardwalker]

nullptr @ Sat Mar 01, 2014 9:52 pm wrote:

Quote:

c++:

for (int ii = i + i; ii < NUMNUMS; ii += i) {         Nums [ii] = false; }

One more thing -- instead of starting at i + i, you can start at i * i to get faster code in both languages.

Do you really mean i * i (i^2) or do you mean i*2 instead of i + i. If you actually meant i * i could you please elaborate?

[nullptr]

keyboardwalker @ Sun Mar 02, 2014 6:36 pm wrote:

nullptr @ Sat Mar 01, 2014 9:52 pm wrote:

Quote:

c++:

for (int ii = i + i; ii < NUMNUMS; ii += i) {         Nums [ii] = false; }

One more thing -- instead of starting at i + i, you can start at i * i to get faster code in both languages.

Do you really mean i * i (i^2) or do you mean i*2 instead of i + i. If you actually meant i * i could you please elaborate?

Yep, I meant i^2. Here's my proof: suppose we have found a prime N, and that every number divisible by a prime less than N has already been marked as composite. Suppose there is a composite number X which is less than N^2, but is divisible by N. X must have some prime factor other than N, since it is less than N^2. Furthermore, that factor must be less than N, or else X would be greater than N^2. But every number divisible by a prime less than N has already been marked as composite! Therefore this algorithm will not leave any composite numbers divisible by N without marking them. We are allowed to assume that every number divisible by a prime less than N has already been marked because, for N=2, there are no primes less than N, and for any N, this assumption still holds true for the next prime after N.

[Panphobia]

Thats the sieve of eratosthenes,

code:

for (int i = 2; i * i <= N; i++) {         if (isPrime[i]) {             for (int j = i; i * j <= N; j++) {                 isPrime[i * j] = false;             }         }     }

There is my code for it, where N is your NUMNUMS, I am pretty sure this is more efficient, but not completely .

[keyboardwalker]

c++:

#include <iostream> #include <fstream> #include <vector> #include <ctime> int main () {         using namespace std;         ofstream myfile;         const int NUMNUMS = 1000000;         clock_t t;         int t1;         t = clock();         t1 = clock();         cout << "Initializing\n";         bool *Nums = new bool[NUMNUMS];         for (int i = 0; i < NUMNUMS; i ++)         {                 Nums[i] = true;         }         //vector <bool> Nums(NUMNUMS, true);         Nums[1] = false;         cout << "Done Initializing it took " << (float)(clock () - t1)/CLOCKS_PER_SEC * 1000 << " ms" << endl;         cout << "Deriving Prime Numbers\n";         t1 = clock ();         for (int i = 4 ; i < NUMNUMS; i += 2)         {                 Nums [i] = false;         }         for (int i = 3 ; i * i < NUMNUMS; i += 2)         {                 if (Nums[i])                 {                         for (int j = i * i; j < NUMNUMS; j += i * 2)                         {                                 Nums [j] = false;                         }                 }         }                 cout << "Done. Algorithm took: " << (float)(clock() - t1)/CLOCKS_PER_SEC * 1000 << " ms" << endl;         cout << "Saving\n";         t1 = clock ();         myfile << 2 << "\n";         for (int i = 3 ; i < NUMNUMS; i += 2)         {                 if (Nums[i])                 {                         myfile << i << "\n";                 }         }         myfile.close();         cout << "Done Saving. It took: "  << (float)(clock() - t1)/CLOCKS_PER_SEC * 1000 << " ms" << endl;         cout << "The entire program took "  << (float)(clock() - t)/CLOCKS_PER_SEC * 1000 << " ms" << endl;         delete [] Nums;         cout << "Press any key";         cin.get();         return 0; }

These are great suggestions and I made one more improvement to the sieve.

I can do this j += i * 2 since an odd number (all primes except for 2) multiplied an even number of times is always an even number and therefore a factor of 2 and not a prime number. i * (i + 1) is not a prime number such that i is a prime number greater than 2.

I didn't see this in the optimized version of http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

I wonder why.