schnellster primzahlen algorithmus

[Gast]

Das ist doch genau das, was saulahm ist.

[leo aka qsch]

ich kannte mal eine gute Seite mit wirklichen schnellen Loesungen

sucht mal in google: the evolution of prime

[vergessen]

@leo aka qsch: thx wer ich ma gugge.

@ die die voll die asso algos haben ^^: könnt ihr da vllt mal bissel was zu erklären. die sin ja echt verdammt schnell nur raff ich die algorithmen absolut net! ^^ wär nett wenn jemand mal seine grundgedanken oder so noch postet.

@ alle anderen: kommt schon ich weiß dass ihr was habt. also raus mit euren sources!

.:: vergessen ::.

[borg]

vergessen schrieb:

@ die die voll die asso algos haben ^^: könnt ihr da vllt mal bissel was zu erklären. die sin ja echt verdammt schnell nur raff ich die algorithmen absolut net! ^^ wär nett wenn jemand mal seine grundgedanken oder so noch postet.

hier: http://www.andrew.cmu.edu/user/gschaeff/school/primality_testing_algorithms.pdf
hab ich oben schon geschrieben den link... da werden schnelle primzahlalgorithmen erklärt. und das sogar erstaunlich verständlich.

[rapso]

http://www.forum-3dcenter.org/vbulletin/showthread.php?t=95859

rapso->greets();

[Blue-Tiger]

ist zwar Python und ist auch nicht grad der schnellste Algorithmus (Sieb des Erathostenes) und die schnellste Implementation, aber wenn man schon danach gefragt wird:

import sys

def isPrime(number, primelist):
	"""Return true if number is a prime number.

	divides number through all numbers in primelist,
	and if none of these numbers can divide the number,
	number must be a prime number.

	NOTE: primelist HAS TO contain all prime numbers < number
	      and HAS TO be sorted.
	"""

	for i in primelist:
		if number % i == 0:
			return False

	# just in case primelist doesn't contain all
	# the possible divisors of number, we'll divide
	# number through all the odd numbers from the
	# highest known prime number up to number / 2,
	# just to make sure we've tested every possibility
	limit = number / 2
	if primelist[-1] + 2 < limit:
		for i in range(primelist[-1] + 2, limit, 2):
			if number % i == 0:
				return False

	# no divisor found, number should be a prime
	return True

# start with 2 and 3
# note that 3 is necessary because in the following for-loop
# we start with primelist[-1] + 2 and then continue in steps
# of 2... starting with only 2 in our list we would end up
# testing only even numbers (but all primes except 2 itself
# are odd numbers! The even ones can be divided through 2!)
primelist = [2, 3]
candidate = 5
try:
	candidate = long(raw_input("enter a limit number (2 - " + str(sys.maxint) + "): "))
except ValueError:
	print "What you entered was not a valid number!!!\n"
	print "(feel free to restart and enter something use- and meaningfull! ;-))"

# only accept odd numbers
if candidate % 2 == 0:
	candidate += 1

for i in range(primelist[-1] + 2, candidate, 2):
	if isPrime(i, primelist):
		primelist.append(i)

[volkard]

wenn ihr euch auf nen schnelle geeinigt habt, und vor allem auf das messverfahren, dann postet mal code. würde meine überlegungen gerne mal dagegenstellen.

beim messverfahren ist vor allem wichtig, ob nur fortlaufende primzahlen gefragt sind (dann eratosthenes für nubes und quadric sieve für profis) oder nur primalität von einzelzahlen abgefragt wird (dann wird's auch recht spannend und ist eher mein gebiet)).

edit: und natürlich, in welchem wertebereich die zahlen liegen können. für zahlen kleiner als 100 nimmt man bestimmt ne tabelle. für zahlen kleiner 1000 wohl trial division (und schaut die primteiler bis 31 auch in ner tabelle nach). bis 2^32 oder 2^62 isn dann schon gemeine grenzen, wo man mit tricks aurbeiten darf (bis 2^64 sehe ich noch keine sonne).

zur erheiterung ein altes sieb von mir:

#ifndef BITFIELD_H
#define BITFIELD_H

//typedef unsigned int u32;

class BitField
{
	static inline void setBitTrue(u32* x,u32 pos){//TODO: asm.h benutzen
		*x|=(1<<pos);
	}
	static inline u32 findFirstBitFalse(u32 x){//TODO: asm.h benutzen
		u32 result=0;
		while((x&1)==1){
			x>>=1;
			++result;
		}
		return result;
	}
private:
   u32 *data;
   size_t size;
   BitField(const BitField &);
   BitField &operator=(const BitField &);
public:
   BitField(size_t _size)
		:size(_size){
		size_t wordCount=(size+31)/32;
		data=new u32[wordCount+2];
		data[wordCount]=0;//such-ende-marke
		data[wordCount+1]=u32(-1);//such-ende-marke
		clearAll();
	}
	~BitField(){
		delete[] data;
	}
	void clearAll(){
		size_t wordCount=(size+31)/32;
		for(size_t i=0;i<wordCount;++i)
			data[i]=0;
	}
	void set(size_t pos){
		size_t wordPos=pos/32;
		size_t bitPos=pos%32;
		setBitTrue(&data[wordPos],bitPos);
	}
	size_t findFirstFalse(){
		return findNextFalse(size_t(-1));
	}
	size_t findNextFalse(size_t pos){
		++pos;
		size_t wordPos=pos/32;
		size_t bitPos=pos%32;
		u32 word=data[wordPos];
		if(bitPos!=0)
			word=(word>>bitPos) | (-1<<(32-bitPos));
		while(word==size_t(-1)){
			word=data[++wordPos];
			bitPos=0;
		}
		size_t r=findFirstBitFalse(word)+bitPos+32*wordPos;
		if(r>=size) 
			r=size_t(-1);
		return r;
	}
};

#endif

#ifndef PRIMEGENERATOR_H
#define PRIMEGENERATOR_H

#include <iostream>
#include "BitField.h"

//typedef unsigned long long u64;

/*Mit dem Sieb des Eratostenes werden Primzahlen gesucht. Weil ich nicht den 
Speicher für 2^32 Bits habe, geschieht das Abschnittweise. Dabei ist zu beachten, 
daß für einen neuen Abschnitt von z1 bis z2 alle Teiler bis sqrt(z2) ausgestrichen 
werden müssen. Um das zu beschleunigen, gibt es noch ein kleines Sieb, das zur 
Generierung der Streich-Zahlen zuständig ist. Das wiederum wird nicht mehr von 
einem Sieb versorgt, sondern nur von der Funktion nextPrime().
*/
namespace PrimeGeneratorPrivate{

size_t const BIGSIZE=128*256;//Soll ja in den 1st-Level-Cache des Prozessors passen
size_t const SMALLSIZE=256;

class PrimeGeneratorLevel0{
private:
	u64 pos;
	static bool isPrime(u64 p){
		for(u64 t=2;t*t<=p;++t)
			if(p%t==0)
				return false;
		return true;
	}
	static u64 nextPrime(u64 p){
		do
			++p;
		while(!isPrime(p));
		return p;
	}
public:
	u64 findFirst(){
		pos=2;
		return pos;
	}
	u64 findNext(){
		pos=nextPrime(pos);
		return pos;
	}
};

class PrimeGeneratorLevel1{
private:
	static size_t const SIZE=SMALLSIZE;
	BitField field;
	size_t pos;
	u64 start;
public:
	PrimeGeneratorLevel1()
		:field(SIZE){
	};
	u64 findFirst(){
		for(u64 t=3;t*t<=2*SIZE;t+=2){
			for(size_t s=t+t/2;s<SIZE;s+=t)
				field.set(s);
		}
		pos=0;
		start=0;
		return 2;
	}
	void calculateNextPage(){
		do{
			start+=2*SIZE;
			field.clearAll();
			PrimeGeneratorLevel0 p;
			p.findFirst();
			for(u64 t=p.findNext();t*t<=start+2*SIZE;t=p.findNext()){
				size_t s=(t-start%t)%t;s+=(s%2==0?t:0);s/=2;
				while(s<SIZE){
					field.set(s);
					s+=t;
				}
			}
			pos=field.findFirstFalse();
		}while(pos==size_t(-1));
	}
	u64 findNext(){
		pos=field.findNextFalse(pos);
		if(pos==size_t(-1))
			calculateNextPage();
		return 2*pos+start+1;
	}
};
class PrimeGeneratorLevel2{
private:
	static size_t const SIZE=BIGSIZE;
	BitField field;
	size_t pos;
	u64 start;
public:
	PrimeGeneratorLevel2()
		:field(SIZE){
		start=u64(-1);
	}
	u64 findFirst(){
		if(start!=0){
			for(u64 t=3;t*t<=2*SIZE;t+=2){
				for(size_t s=t+t/2;s<SIZE;s+=t)
					field.set(s);
			}
			start=0;
		}
		pos=0;
		return 2;
	}
	void calculateNextPage(){
		do{
			u64 old=start;
			start+=2*SIZE;
			if(start<old)
				pos=u64(-1);
			field.clearAll();
			PrimeGeneratorLevel1 p;
			p.findFirst();
			for(u64 t=p.findNext();t*t<=start+2*SIZE;t=p.findNext()){
				size_t s=(t-start%t)%t;s+=(s%2==0?t:0);s/=2;
				while(s<SIZE){
					field.set(s);
					s+=t;
				}
			}
			pos=field.findFirstFalse();
		}while(pos==size_t(-1));
	}
	u64 jumpNext(u64 x){
		start=x-2*SIZE;
		calculateNextPage();
		return 2*pos+start+1;
	}
	u64 findNext(){
		pos=field.findNextFalse(pos);
		if(pos==size_t(-1)){
			calculateNextPage();
			if(pos==size_t(-1)) return pos;
		}
		return 2*pos+start+1;
	}
};
/*bool test(){
	//nicht nach 64-bittigkeit umgesetzt
	std::cout<<"testing class PrimeGenerator:\n";
	PrimeGeneratorLevel2 p;
	PrimeGeneratorLevel0 ps;

	u64 i=p.findFirst();
	u64 is=ps.findFirst();
	u16 c=0;
	while(i<1000000000){
		if(!++c) std::cout<<i32(i)<<'\r'<<std::flush;
		if(i!=is){
			std::cout<<"Fehler bei "<<i32(i)<<'\n';
			return false;
		}
		i=p.findNext();
		is=ps.findNext();
	}
	std::cout<<"OK\n";
	return true;
}*/

}//namespace PrimeGeneratorPrivate

typedef PrimeGeneratorPrivate::PrimeGeneratorLevel2 PrimeGenerator;

/*
class PrimeTwinGenerator
{//nicht getestet!!!
private:
	PrimeGenerator pg;
	u64 pos;
public:
	u64 findFirst()
	{
		pg.findFirst();
		pg.findNext();
		pos=pg.findNext();
		return 3;
	};
	u64 findNext()
	{
		u64 o;
		do
		{
			o=pos;
			pos=pg.findNext();
		}while(pos-o!=2);
		return o;
	};
};*/

#endif

[vergessen]

naja also ich würd sagen, dass man einfach die zeit mist bis der algo alle primzahlen bis 1 mio und 10 mio gefunden hat misst und die dann postet.
und zum messverfahren (also welche funktion) kann ich nix sagen. ich weiß net was da sehr genau is. ich hatte glaub ich GetTickCount() benutzt.

.:: vergessen ::.

[rapso]

ich würde 10 zahlen im bereich von 2^64 testen lassen und die zeit messen

rapso->greets();

[Vertexwahn]

Hab bis jetzt noch keine Eratosthenes Implementierung gesehen, die keine Arrays verwendet - hab für mein Praktikum programmieren mal eine gemacht:

class Eratosthenes
{
	static public void main(String[] args)
	{
		print(100);
	}

	/*
	 *	Anzahl der Primzahlen, die ausgegeben werden soll 
	 */
	public static void print(int numOfPrimes)
	{
		if(numOfPrimes < 0)
			return;

		// Naturals ist eine Sequence der natuerlichen Zahlen
		Naturals nat = new Naturals();

		// KillOne ist ein Filter der alle Zahlen außer der eins durchläßt
		Filter x = new KillOne(nat);	

		for(int i = 0; i < numOfPrimes; i++)
		{

			int p = x.nextElement();
			System.out.println("Primzahl: " + p);// liefert Primzahl
			x = new ZapMultiples(x, p);
		}
	}
}

abstract class Filter extends Sequence
{
	// Ein Filter hat eine Zahlenfole und ist eine Zahlemfolge
	private Sequence sequence;	

	abstract boolean absorb(int number);

	int nextElement()
	{
		int x = sequence.nextElement();

		while(absorb(x))
			x = sequence.nextElement();

		return x;
	}

	int preview(int destination)
	{
		if(sequence.preview(1)!=-1)
		{
			int x = sequence.preview(1);

			int counter = 1;

			while(absorb(x))
			{
				counter++;

				if(sequence.moreElements())
					x = sequence.preview(counter);
				else
					return -1;
			}

			return x;
		}
		else
			return -1;
	}
}

/*
 * Die natürlichen Zahlen (1, 2, 3, ...) sind eine konkrete 
 * Zahlenfolge. Der erste Aufruf von nextElement liefert 1, 
 * der nächste 2, dann 3 und so weiter. moreElements ist 
 * immer true
 */

class Naturals extends Sequence
{
	private int n = 0;

	int nextElement()
	{
		n++;			// erhoehe internen Zaehler
		return n;
	}

	int preview(int destination)
	{
		return n + destination;
	}
}

// KillOne ist ein Filter der alle Zahlen außer der eins durchläßt

class KillOne extends Filter
{
	KillOne(Sequence sequence)
	{
		this.sequence = sequence;
	}

	boolean absorb(int number)
	{
		if(number == 1)
			return true;
		else
			return false;
	}
}

class ZapMultiples extends Filter
{
	private int		 base;		// Vielfache

	ZapMultiples(Sequence sequence, int base)
	{
		this.sequence = sequence;
		this.base = base;
	}

	boolean absorb(int number)
	{
		if(number%base==0)
			return true;
		else
			return false;
	}
}

abstract class Sequence
{
	// gibt Auskunft, ob diese Folge noch weitere Elemente enthaelt 
	// (true) oder nicht (false)
	boolean moreElements()
	{
		if(preview(1) != -1)
			return true;
		else
			return false;
	}

	// liefert das nächste Element der Folge. Darf nur dann aufgerufen 
	// werden, wenn moreElements das Ergebnis true geliefert hat.
	abstract int nextElement();

	// mit dieser Funktion kann man herausfinden welche Elemente folgen
	// bei dem nächsten (destination = 1), übernächsten (destination = 2)
	// usw. Aufruf der Funktion nextElements
	abstract int preview(int destination);

	// gibt die ersten 10 Elemente einer beliebigen Folge aus. Wenn 
	// die Folge bloß 10 oder weniger Elemente hat, wird anschließend 
	// das Wort "end" ausgegeben, ansonsten "more"
	void print()
	{
		for(int i = 1; i <= 10; i++)
		{
			if(!moreElements())
				break;

			System.out.println(nextElement() + " ");
		}

		if(moreElements())
			System.out.println("more");
		else
			System.out.println("end");
	}
}

[volkard]

Vertexwahn schrieb:

Hab bis jetzt noch keine Eratosthenes Implementierung gesehen, die keine Arrays verwendet

hab vor 2 monaten was gebaut, was fast wie eratosthenes aussieht, aber kein array (also keins über den ganzen zahlenbereich) benutzt. hat aber keine chance gegen normalen era. hat dafür aber keine wartezeit vor der ausgabe der ersten zahl.

template<typename POS,size_t SIZE>
class WheelGenerator{
private:
	struct Jumper{
		POS pos;
		POS step;
		Jumper(POS _pos,POS _step):
		pos(_pos),
		step(_step){
		}
		Jumper(){
		}
		friend bool operator<(Jumper const& a,Jumper const& b){
			return a.pos<b.pos;
		}
		friend bool operator>(Jumper const& a,Jumper const& b){
			return a.pos>b.pos;
		}
		void* operator new(size_t ,void* p){
			return p;
		}
	};
	POS pos;
	Jumper begin[SIZE];
	Jumper* rbegin;
public:
	WheelGenerator(){
	}
	void addJumper(POS pos,POS step){
		new(rbegin) Jumper(pos,step);
		++rbegin;
		new(rbegin) Jumper(POS(-1),POS(-1));
	}
	POS findFirst(){
		rbegin=begin;
		new(rbegin) Jumper(POS(-1),POS(-1));
		pos=1;
		return 2;
	}
	void sortInChangedJumper(Jumper* p){
		while(*p>*(p+1)){
			vhlib::swap(*p,*(p+1));
			++p;
		}
	}
	void sortInNewJumper(Jumper* p){
		while(p>begin && *p<*(p-1)){
			vhlib::swap(*p,*(p-1));
			--p;
		}
	}
	POS findNext(){
		for(;;){
			pos+=2;
			if(pos!=begin->pos){
				if(rbegin<begin+SIZE-1)
					addJumper(pos*pos,2*pos);
				break;
			}
			do{
				begin->pos+=begin->step;
				sortInChangedJumper(begin);
			}while(pos==begin->pos);
		}
		return pos;
	}
	POS findFirst(POS newPos){
		rbegin=begin;
		new(rbegin) Jumper(POS(-1),POS(-1));
		pos=(newPos|1)-2;
		POS p=3;
		for(size_t i=0;i<SIZE-1;++i){
			POS start=pos+p-(pos+p)%(2*p)+p;
			if(start==p)
				break;
			addJumper(start,2*p);
			sortInNewJumper(rbegin-1);
			p=nextPrime(p);
		}
		return findNext();
	}
};