Code versnellen

Status
Niet open voor verdere reacties.
manhaeve5

manhaeve5

Gebruiker
Lid geworden
9 jan 2007
Berichten
276
Dit is hier m'n code:
Code: 
#include <cstdlib>
#include <iostream>
#include <fstream>
using namespace std;
bool checkpriem(int* getal);
int main()
{
    int aantal;
    ofstream output;
    output.open("priemgetallen.txt");
    cout<<"Alle priemgetallen tot ";
    cin>>aantal;cin.ignore();
    output<<2<<endl<<3<<endl<<5<<endl<<7<<endl;
    for(int a=2;a<aantal;a++)
    {
                             if(a%2!=0&&a%3!=0&&a%5!=0&&a%7!=0){
                                                        if(checkpriem(&a)==true)
                                                                                output<<a<<endl;
                                                        }
    }
    output.close();
    cout<<"Klaar"<<endl;
    cin.get();
   return 0;
}

inline bool checkpriem(int* getal)
{
     bool priem=true;
     for(int a=2;a<*getal;a++)
                              {
                               if(*getal%a==0)
                                             {
                                              priem=false;
                                              break;
                                              }
                               }
     return priem;
}
is er nog een manier om dit te versnellen?
 
Zoiets?

PHP: 
/***************************************************************************
 *   Copyright (C) 2007 by Dropl   *
 *   zwartetoorts@hetnet.nl   *
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 *   This program is distributed in the hope that it will be useful,       *
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
 *   GNU General Public License for more details.                          *
 *                                                                         *
 *   You should have received a copy of the GNU General Public License     *
 *   along with this program; if not, write to the                         *
 *   Free Software Foundation, Inc.,                                       *
 *   59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.             *
 ***************************************************************************/


#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include <iostream>
#include <cstdlib>
#include <vector>

using namespace std;

/**************************************************************************************
	Recursieve functie
	Crasht door stack overflow bij grote getallen
**************************************************************************************/
void next_priem_rec(vector<unsigned long>& vpriem, unsigned long val, unsigned long max)
{
	vector<unsigned long>::iterator it;

	if(val == max)
		return;
	
	it = vpriem.begin();
	while(*it <= val / 2)
	{
		if(val % *it == 0)
		{
			next_priem_rec(vpriem, ++val, max);
			return;
		}
		it++;
	}

	vpriem.push_back(val);
	next_priem_rec(vpriem, ++val, max);
}

/**************************************************************************************
	Alternatieve functie
	Crasht niet door stack overflow bij grote getallen
**************************************************************************************/
void next_priem(vector<unsigned long>& vpriem, unsigned long val, unsigned long max)
{
	vector<unsigned long>::iterator it;

	while(val < max)
	{
		it = vpriem.begin();
		while(*it <= val / 2)
		{
			if(val % *it == 0)
				break;
			else
				it++;
		}
		if(*it > val / 2)
			vpriem.push_back(val);
		val++;
	}
}

int main(int argc, char *argv[])
{
	vector<unsigned long> vpriem;
	unsigned long max = (argc == 2 ? atol(argv[1]) : 30);

	cout << "Alle priemgetallen tot " << max << endl;

	vpriem.push_back(2);
	next_priem(vpriem, 3, max);
/*	of anders:
	next_priem_rec(vpriem,, 3, max);
*/

	vector<unsigned long>::iterator it;
	for(it = vpriem.begin(); it != vpriem.end(); it++)
		cout << *it << endl;

  return EXIT_SUCCESS;
}
 
Ik dacht, ik verander iets aan de basis :shocked:

Jij doorloopt alle getallen en kijkt of ze deelbaar zijn door alle getallen, grofweg
Ik controleer of een getal deelbaar is door de tot dan toe gevonden priemgetallen. Bij grote getallen scheelt dat een heleboel lijkt me.
Ook beperk ik de reeks gevonden priemgetallen tot maximaal de helft van het getal dat gecontroleerd wordt, omdat uitkomst 2 volgens mij de kleinst mogelijke ronde uitkomst is.
Verders werkt jouw methode met meer variabelen, dat vertraagt nogal denk ik.
En waarom je met pointers in je functie werkt, snap ik niet helemaal. Als je dat niet doet en die inline functie __fastcall meegeeft wordt het getal via een register meegegeven en niet via de stack (ligt aan welke compiler je gebruikt). Dat versnel nogal om het dan geen geheugen uit hoeft te lezen.
Overigens ben ik el benieuwd wanneer mijn programma sneller zou kunnen zijn (vanaf welke reeks) omdat dat gedoe met die vector ook veel processortijd en geheugenoperaties vergt.
 
Ik heb voor de gein (en uit nieuwsgierigheid) jouw programma aangepast zodat deze naar cout schrijft. En daarna geoptimaliseerd gecompileerd met gcc (ik zit hier op een linux systeem). Hetzeflde heb ik met mijn programma gedaan.
Vervolgens heb ik ze met het programma ' time' gedraait. Dit meet hoe lang het programma er over doet. Niet om er een strijd van te maken, maar uit nieuwsgierigheid. Mijn programma is toch wel een stuk sneller:

priem is mijn programma, priem2 is jouw programma. Ze tellen zoeken beide alle priemgetallen tot 30000
Code: 
okkel@woonkamer:~/sources/test0/priem/debug/src$ time ../../optimized/src/priem 30000 >/dev/null && time ./priem2 30000 >/dev/null

real    0m0.109s
user    0m0.104s
sys     0m0.004s

real    0m1.541s
user    0m1.480s
sys     0m0.060s

Bij kleine getallen presteren ze gelijk:
Code: 
okkel@woonkamer:~/sources/test0/priem/debug/src$ time ../../optimized/src/priem 100 >/dev/null && time ./priem2 100 >/dev/null

real    0m0.005s
user    0m0.004s
sys     0m0.000s

real    0m0.005s
user    0m0.004s
sys     0m0.000s

Overigens ben ik niet 100% zeker dat mijn programma alle uitkomsten goed geeft. Dus mocht je fouten vinden, laat dat me dan aub weten :p
 
Volgens mij zijn onze uitkomsten gelijk
priem.txt is mijn programma, priem2.txt jouw programma
 

Bijlagen

een lijst gemaakt met alle priemgetallen tot 5 miljoen. Iemand geïntreseerd?
 
lol nope thx :P, wat wil je eigenlijk met die getallen of is het gwn voor de lol?
 
Als je dan toch optimaliseert met zoeken:
Je hoeft maar tot de wortel van een getal te zoeken om een deler te vinden. Want als x = a maal b en a > wortel(x) dan is b < a en dan had je de deler al moeten vinden.
Verder kun je als je gaat zoeken natuurlijk veel beter gebruik maken van de lijst reeds gevonden priemgetallen. Alle andere delers hoef je niet te testen.
 
Er was zo'n soort "wedstrijd" waarbij een bedrijf veel geld biedt/bood voor het googste priemgetal. Dat waren getallen van zo'n 10 miljoen decimalen.
 
Status
Niet open voor verdere reacties.
                    Steun ons                    

Nieuwste berichten

Terug
Bovenaan Onderaan