Thread: basic prime numbers

  1. #16
    aoeuhtns
    Join Date
    Jul 2005
    Posts
    581
    Quote Originally Posted by sehr alt View Post
    A language without GOTO is NOT TURING COMPLETE. Never.
    Ha ha.
    Are you on this board just to troll? Every post of yours makes it seem as if you were deliberately carrying on like a moron.
    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.

  2. #17
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by sehr alt View Post
    'goto' is a basic jmp command your machine actually is able to understand (literally!).
    This is why goto is executed more quickly than most loops, which usually consist of a combination of many machine commands.
    So - although you are often told to avoid 'goto' and to use loops instead, 'goto' is the more optimized version in most cases.
    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"

  3. #18
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    I'm not sure if this is true but I think I read somewhere that while loops are slightly faster than for loops.

  4. #19
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Quote Originally Posted by mike_g View Post
    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.

    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).

  5. #20
    Registered User
    Join Date
    May 2007
    Posts
    21
    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();
    }

  6. #21
    Dr Dipshi++ mike_g's Avatar
    Join Date
    Oct 2006
    Location
    On me hyperplane
    Posts
    1,218
    Quote Originally Posted by vart View Post
    If you want to increase performace - store all found prime numbers and check the division only to these numbers

    And of course - the internal loop should go only upto sqrt(j)
    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.

  7. #22
    Registered User
    Join Date
    May 2007
    Posts
    21
    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?

  8. #23
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    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

  9. #24
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    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
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  10. #25
    Registered User
    Join Date
    May 2007
    Posts
    58
    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:

    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();
    }
    On my pc, it calculated them in 0 miliseconds, that's perfomance huh?
    Last edited by Govalant; 06-17-2007 at 06:12 PM.

  11. #26
    CS Author and Instructor
    Join Date
    Sep 2002
    Posts
    511
    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).
    Anon is correct

    ..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

  12. #27
    Registered User
    Join Date
    May 2007
    Posts
    58
    The code on my previous post crashed when trying to calculate over 500k.

    change

    Code:
    int primes[max+1];
    for

    Code:
    int* primes;
    
    primes = (int*)malloc(sizeof(int) * (max+1));
    it'll work the same way, and with any number you want (unless you run out of memory)

  13. #28
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    primes = (int*)malloc(sizeof(int) * (max+1));
    This is C++ forum. Isn't it?
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  14. #29
    Captain - Lover of the C
    Join Date
    May 2005
    Posts
    341
    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.
    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;
    }
    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...
    Don't quote me on that... ...seriously

  15. #30
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Finding Prime Numbers
    By dan724 in forum C Programming
    Replies: 11
    Last Post: 12-14-2008, 12:12 PM
  2. prime number program with function
    By mackieinva in forum C Programming
    Replies: 17
    Last Post: 09-20-2007, 08:36 AM
  3. prime numbers code compile error
    By Tony654321 in forum C Programming
    Replies: 5
    Last Post: 10-10-2004, 10:13 AM
  4. the definition of a mathematical "average" or "mean"
    By DavidP in forum A Brief History of Cprogramming.com
    Replies: 7
    Last Post: 12-03-2002, 11:15 AM
  5. prime numbers
    By Unregistered in forum C Programming
    Replies: 17
    Last Post: 08-20-2002, 08:57 PM