This is a discussion on basic prime numbers within the C++ Programming forums, part of the General Programming Boards category; Originally Posted by sehr alt A language without GOTO is NOT TURING COMPLETE. Never. Ha ha. Are you on this ...
There are 10 types of people in this world, those who cringed when reading the beginning of this sentence and those who salivated to how superior they are for understanding something as simple as binary.
ROFL - SIF! Absolutely ludicrous!
Using goto actually makes it harder for a compiler to understand the program flow and hence is harder for a compiler to optimise.
First up, good luck convincing anyone that a goto is faster than a for( ; ; )!
Goto is an unconditional branch; Not very useful on its own. You typically have to put it inside an if statement, making it exactly the same as either an if statement or a do-while loop, depending on whether it goes forwards or back.
I'm quite certain you wont find any compiler anywhere that will generate faster code for a goto than a loop construct. I'd be very happy for you to start poking around with the assembly output of some code so that you can see how wrong you are too.
Oh and of course, only release mode with optimisations on is of any consequence.
My homepage
Advice: Take only as directed - If symptoms persist, please see your debugger
Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"
I'm not sure if this is true but I think I read somewhere that while loops are slightly faster than for loops.
Well, I think I've read the opposite.
Anyway, if you want a major speed boost, you'll need to use a more efficient algorithm. Whether you use for, while or goto makes very little difference.
As to Turing completeness, I thought only a while-like (loop+conditional branching in one) was required of a language (e.g Brain........ - given it can use infinite memory - is said to be Turing-complete without any GOTO).
I might be wrong.
Quoted more than 1000 times (I hope).Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
Ok I've ended up with 3 different logics, the first two are very similar in speed, while the last one is quite a bit slower then causes one of those windows program has encountered an error and has to close, which makes me think the code has bugs, but i dont know where.
Any further comments would be great =)
Code1:
Code:#include <iostream> #include <cmath> #include <ctime> using namespace std; int main() { unsigned stime=(unsigned)clock(); for (unsigned long j=1; j <=1000000; j += 2) { unsigned long k = (unsigned long)(sqrt(j) + .5); unsigned long i; for (i=3; i <=k; i += 2) { if (j%i==0) {goto moo;} } cout << j <<endl; moo:; } cout << endl << (unsigned)clock()-stime; cin.get(); }
Code2:
Code:#include <iostream> #include <cmath> #include <ctime> using namespace std; int main() { unsigned stime=(unsigned)clock(); for (unsigned long j=1; j <=1000000; j += 2) { unsigned long k = (unsigned long)(sqrt(j) + .5); unsigned long i; for(i = 3; (j%i!=0) && i<=k; i += 2); if(i > k) {cout << j << endl; } } cout << endl << (unsigned)clock()-stime; cin.get(); }
Code3:
Code:#include <iostream> #include <cmath> #include <ctime> using namespace std; int main() { unsigned stime=(unsigned)clock(); int i,j; int max=100000; int primes[max]; for (int l=0;l<=max;++l){ primes[l]=1; } for(i=2;i<=max/2;++i) { for(j=2;j<=max/2;++j) { if(i*j>max) break; primes[i*j]=0; } } for (int l=0;l<=max;++l){ if(primes[l]==1) { cout <<l<<endl; } } cout << endl << (unsigned)clock()-stime; cin.get(); }
For your third prog, If you are pre-calculating the primes, then you would generally start the clock after the pre-calc.
[edit]Pre calculation can speed stuff up a lot, but is only useful if you are going to call it at least several times. An example could be building a sin/cos table when the prog starts then whenever you use them you can check the table instead of calculating it each time. For a prog like yours that only checks the list once using precalc will slow it down instaed.[/edit]
Last edited by mike_g; 06-17-2007 at 09:27 AM.
Yeah, i was thinking about adding to the list as it was finding primes so there was no precalc, it just did it as you went along, but i don't know how to impliment that kind of variable array or whatever. Any suggestions?
std::vector
With regards to loop speed, there is absolutely no difference in principle between while and for loops. All while loops can be trivially written as for loops. All for loops can be easily refactored into while loops. (Thus, for the question of turing completeness, they are of course equivalent.) The only way a performance difference can possibly occur is that the compiler treats them differently during optimization.
All the buzzt!
CornedBee
"There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
- Flon's Law
you can replace endl; with '\n' to gain the additional performance boost for "free" - your constant flushes of the outgoing stream has nothing to do with the algorith performance itself
The first 90% of a project takes 90% of the time,
the last 10% takes the other 90% of the time.
Man, you're checking the time after you print the values. Printf is not fasta t printing, is about 300 lines a second i think.
*If anyone saw my post before editing i'm sorry, i posted without looking right
Here's your code, if it was an assignment you'll get an a:
On my pc, it calculated them in 0 miliseconds, that's perfomance huh?Code:#include <iostream> #include <cmath> #include <ctime> using namespace std; int main() { unsigned stime=(unsigned)clock(); int i,j; int max=100000; int primes[max+1]; for (int l=0;l<=max;++l){ primes[l]=1; } for(i=2;i<=max/2;++i) { for(j=2;j<=max/2;++j) { if(i*j>max) break; primes[i*j]=0; } } cout << "Numbers calculated in:" << (unsigned)clock()-stime << " miliseconds\nPress a key to print"; cin.get(); for (int l=0;l<=max;++l){ if(primes[l]==1) { cout <<l<<endl; } } cin.get(); }
Last edited by Govalant; 06-17-2007 at 06:12 PM.
Anon is correctAs to Turing completeness, I thought only a while-like (loop+conditional branching in one) was required of a language (e.g Brain........ - given it can use infinite memory - is said to be Turing-complete without any GOTO).
..Bohm and Jacopini in 1960's stated that a Turing compatable language is a language can be used to solve any solvable problem. It was proved by them that in terms of controls structures, only computablity requirements are
1. ability to state a sequence of statements
2. the WHILE LOOP construct- with it it is possible to produce any other control structure...
Paraphrase from Cooke, 2003.
You can also use flags to eliminate GOTO's...
Mr. C: Author and Instructor
The code on my previous post crashed when trying to calculate over 500k.
change
forCode:int primes[max+1];
it'll work the same way, and with any number you want (unless you run out of memory)Code:int* primes; primes = (int*)malloc(sizeof(int) * (max+1));
This is C++ forum. Isn't it?primes = (int*)malloc(sizeof(int) * (max+1));
The first 90% of a project takes 90% of the time,
the last 10% takes the other 90% of the time.
Oh Boy! I love optimizing. Just can't help but put my two cents in. I'm willing to bet it is the faster so far and will not be beaten. It does have the memory requirement issue but there's always that memory vs speed trade-off.
Basically, 2 is the first prime number. We can eliminate all the other numbers divisible by 2. The first number after 2 not eliminated is 3. We can elimate all the remaining numbers divisible by 3. The first number after 3 not eliminated is 5 and so on...Code:#include <iostream> #include <cmath> #include <ctime> using namespace std; int main() { unsigned stime=(unsigned)clock(); const unsigned long HIGHNUM = 1000000; unsigned long i; bool *primes = new bool[HIGHNUM + 1]; for (i = 2; i <= HIGHNUM; i++) primes[i] = true; for (i = 2; i <= HIGHNUM; i++) if (primes[i]) for (unsigned long j = (i << 1); j <= HIGHNUM; j += i) primes[j] = false; cout << "Primes found in " << (unsigned)clock()-stime << " milliseconds.\n"; cin.get(); for (i = 2; i <= HIGHNUM; i++) if (primes[i]) cout << i << '\n'; cin.get(); return 0; }
Don't quote me on that... ...seriously
Do your four levels of brace-less control statements also contribute to the optimization, or is that just obfuscation?
This algorithm is called the Sieve of Erastothenes, by the way.
All the buzzt!
CornedBee
"There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
- Flon's Law