Programmierung zum Wochenstart

[1unitedpower]

Das Sieb des Eratosthenes ist ein Algorithmus zur Berechnen von Primzahlen. Die Aufgabe besteht darin den Algorithmus in JavaScript zu implementieren, je nach persönlicher Motivationslage gibt es die Aufgabe in zwei Schwierigkeitsgraden:

Normale Schwierigkeit: Implementiere den Algorithmus, so dass er als Eingabe ein Array von fortlaufenden natürlichen Zahlen (Number) fester länge bekommt, und ein Array mit den darin enthaltenen Primzahlen ausgibt. Eine Eingabeprüfung wird nicht verlangt.

Enorme Schwierigkeit: Implementiere den Algorithmus ohne Eingabe und als Ausgabe soll er einen Iterator liefern, der alle^[1] Primzahlen aufzählt (wenn man ihm genügend Laufzeit zur Verfügung stellt). Insbesondere muss der Algorithmus mit beliebig großen Zahlen^[2] arbeiten können.

Lösungen per PN an mich, die Auflösung gibt es am Sonntag, außer jemand wünscht eine Verlängerung, weil er der Lösung schon so nahe ist.

---

1. Hinweis: Rekursive Lösungen müssen darauf achten, dass der Programmstack nicht überläuft. Es genügt eine Tail-rekursive Lösung. Wer damit selber unzufrieden ist (wegen mangelnder Engine-Unterstützung), darf auch Trampolines verwenden. ↩︎

2. Hinweis: BigInt Proposal ↩︎

[pl]

Insbesondere muss der Algorithmus mit beliebig großen Zahlen arbeiten können.

Seit Diffie Hellman ist die ganze Welt auf der Suche nach einem solchen Algorithmus!

[Rolf B]

Hallo 1unitedpower,

darf die Iteratorlösung nur von beliebiger Laufzeit oder auch von beliebigem Speicher (zum Cachen der gefundenen Primzahlen) ausgehen?

Rolf

[1unitedpower]

darf die Iteratorlösung nur von beliebiger Laufzeit oder auch von beliebigem Speicher (zum Cachen der gefundenen Primzahlen) ausgehen?

Die Heapgröße darfst du als unbeschränkt annehmen, der Stack muss in der Höhe beschränkt sein, Stackframes dürfen auch beliebig groß sein.

[Gunnar Bittersmann]

@@1unitedpower

Sieb des Eratosthenes

Die Aufgabe erinnert mich daran, dass ich meinen LC80 mal wieder vorkramen und das Sieb des Eratosthenes darauf implementieren wollte.

Normale Schwierigkeit: Nichts mit höherer Maschinensprache, nichts mit Assembler – nein, in Z80-Maschinencode! Ein Kibibyte RAM für Programmcode und Daten sollten ausreichen, um die Primzahlen bis 4000 zu berechnen.

Enorme Schwierigkeit: Ein Netzteil auftreiben und das Ding wieder lauffähig machen. Da man da von 8 bis 20 Volt so ziemlich alles reinjagen kann, egal ob Gleich- oder Wechselstrom, fehlt mir eigentlich nur der passende Stecker.

LLAP 🖖

[pl]

Apropos Stecker, im Grunde genommen kannst Du jeden Lautsprecher direkt an das 220 Volt Netz anschließen. Nur das Geräusch macht den Unterschied!

[Gunnar Bittersmann]

@@pl

Apropos Stecker, im Grunde genommen kannst Du jeden Lautsprecher direkt an das 220 Volt Netz anschließen. Nur das Geräusch macht den Unterschied!

Je nach Land brummt der mit 50 oder 60 Hertz.

Und so mancher brummt nicht lange.

LLAP 🖖

[pl]

Na, wenn das mal nicht auf Deinem Bingozettel gestanden hätte 😉

[1unitedpower]

Ich habe korrekte Einsendungen von @Gunnar Bittersmann und @Rolf B bekommen, ich überlasse es euch sie hier vorzustellen.

Ich habe es mit dem rekursiven Lösungsweg versucht, und erstmal naiv angefangen und das Stackwachstum ignoriert:

// Erzeuge alle natürlichen Zahlen beginnend mit 2
function* nats () {
    let start = 2n;
    while (true) {
        yield start++;
    }
}

// Erzeuge alle Primzahlen
function* primes () {
    yield* filterPrimes(nats())
}

// Siebe alle Primzahlen aus dem übergebenen Iterator
function* filterPrimes(xs) {
    const p = xs.next().value;
    const rest = dropMutliplesOf(p, xs);
    yield p;
    yield* filterPrimes(rest);
}

// Entferne alle Multiplikativen von p aus dem übergebenen Iterator
function* dropMutliplesOf (p, xs) {
    for (const x of xs) {
        if (x % p !== 0n) {
            yield x
        }
    }
}

JavaScript optimiert keine tail-rekursiven Aufrufe in Generatoren, das habe ich auch erst durch die Aufgabe gelernt, deshalb muss der rekursive Aufruf in filterPrimes aufgelöst werden, das hab ich mit einem Trampoline gelöst:

// Erzeuge alle Primzahlen
function* primes () {
    let [p, next] = step(nats2())
    yield p;
    while (true) {
        [p, next] = next()
        yield p
    }
}

// Erzeuge die nächste Primzahl und eine Funktion zum Erzeugen der Übernächsten Primzahl
function step(xs) {
    const p = xs[Symbol.iterator]().next().value;
    const rest = dropMutliplesOf(p, xs);
    return [p, () => step(rest)];
}

In dem Code steckt aber noch eine verteckte Rekursion, nämlich bei der Benutzung von dropMultiplesOf. Die Rekursion habe ich aufgelöst, indem ich den Callstack explizit in einem Parameter kodiert habe.

// Generiere alle Primzahlen
function* primes () {
    let [p, next] = step([], nats2())
    let primes = [p]
    yield p;
    while (true) {
        [p, next] = next(primes)
        primes.push(p)
        yield p
    }
}

// Nimmt eine Liste von zuvor berechneten Primzahlen und einen Iterator der natürlichen Zahlen (beginnend mit 2n) entgegen, liefert die nächste Primzahl und eine Funktion zum berechnen der übernächsten Primzahl.
function step(primes, xs) {
    const p = dropMutliplesOf(primes, xs).next().value;;
    return [p, (primes) => step(primes, xs)];
}

// Filtere alle zahlen aus xs, die keine Vielfachen einer Zahl aus primes sind.
function* dropMutliplesOf (primes, xs) {
    for (const x of xs) {
        if (primes.every(p => x % p !== 0n)) {
            yield x
        }
    }
}

Fazit: Nach dem Trampolining ist der Code fast nicht mehr zu verstehen, schade eigentlich.

Schließlich habe ich noch eine prozedurale Lösung gebaut, zuerst ohne Optimierungen:

// Generiere alle Primzahlen
function* primes () {
    const primes = []
    forX: for (let x = 2n; true; x++) {
        for (let p of primes) {
            if (x % p === 0n) continue forX;
        }
        primes.push(x)
        yield x
    }
}

Und mit Optimierung:

// Generiere alle Primzahlen
function* primes () {
    yield 2n;
    const primes = [2n];
    forX: for (let x = 3n; true; x = x + 2n) {
        for (let p = primes[1], i = 1; (x >= p * p) && (i < primes.length); i++, p = primes[i]) {
            if (x % p === 0n) continue forX;
        }
        primes.push(x)
        yield x
    }
}

Die schnellste Lösung hat @Rolf B eingereicht, obwohl ich glaube, dass meine letzte Variante den selben Algorithmus benutzt, komme ich damit nicht seine Performance heran. Glückwunsch!

[Gunnar Bittersmann]

@@1unitedpower

Ich hatte mich zuerst an die Aufgabe für Normalos gemacht. Allerdings etwas abgewandelt (so normal bin dann doch nicht 😜): die Funktion bekommt kein mit Zahlen vorausgefülltes Array als Parameter, sondern die Zahl max, bis zu der alle Primzahlen ermittelt werden sollen. Das Array wird innerhalb der Funktion selbst erzeugt und beherbergt keine Zahlen, sondern boolesche Werte, anfangs mit true gefüllt. 0 und 1 sind keine Primzahlen; flags[0] und flags[0] werden auf false gesetzt.

Dann beginnt das Sieben: das jeweils nächste Element, das true ist, steht für eine Primzahl; alle Vielfachen davon werden auf false gesetzt. Man muss nicht ewig sieben, als mögliche Primfaktoren kommen nur Primzahlen bis √max in Betracht.

	for (
		let currentPrime = 2;
		currentPrime <= sqrtMax;
		currentPrime = flags.indexOf(true, currentPrime + 1)
	)
	{
		for (let i = 2 * currentPrime; i < flags.length; i += currentPrime)
		{
			flags[i] = false;
		}
	}

Am Ende ist flags[i] nur noch für diejenigen i true, die Primzahlen sind; diese werden in einem zweiten Array gesammelt.

Das Ganze zu sehen in diesem Pen.

Eine Optimierung besteht nun darin, die 2 gesondert zu nehmen und im Weiteren nur noch die ungeraden Zahlen zu betrachten. Das Array ist dann nur noch halb so groß. Eine Hilfsfunktion getNumberFromIndex() stellt die Zuordnung Index–Zahl her. Zu sehen in [jenem Pen](https://codepen.io/gunnarbittersmann/pen/JebxNp ?editors=0012).

An die lächerliche Geschwindigkeit – äh wahnsinnige Geschwindigkeit – äh enorme Schwierigkeit hab ich mich später gewagt; dazu später mehr.

LLAP 🖖

[Gunnar Bittersmann]

@@Gunnar Bittersmann

An die lächerliche Geschwindigkeit – äh wahnsinnige Geschwindigkeit – äh enorme Schwierigkeit hab ich mich später gewagt; dazu später mehr.

Beim Itarator habe ich erst gerätselt, wie ich das n Elemente große Array, in welchem gesiebt wird, denn schrittweise erweitern sollte, wenn man an dessen Ende ankommt:

• jeweils um die nächsten n Elemente: n → 2n → 3n → 4n …?
• verdoppeln: n → 2n → 4n → 8n …?
• oder gar um den Faktor der nächsten Primzahl: n → 2n → 6n → 30n …?

Gar nicht. Ich nutze eine andere Datenstruktur: ein zweidimensionales Array: in primes[i][0] stehen die Primzahlen; in primes[i][1] jeweils Vielfache davon. In primes[0][0] steht dann die 3; in primes[0][1] wird durchgezählt: 6, 9, 12, …

Wie schon zuvor, wird die 2 extra ausgeheben und nur noch ungerade Zahlen betrachet: current zählt munter durch: 3, 5, 7, 9, …

Die Vielfachen der vorher schon ermittelten Primzahlen werden solange hochgezählt, bis eine Zahl ≥ current rauskommt. Bei Gleichheit ist current ein Vielfaches, also keine Primzahl. → Nächstes current untersuchen.

Bei Ungleichheit: nächste Primzahl aus dem Array prüfen, ob current ein Vielfaches davon ist. Bei √current kann man aufhören. Wenn current bis dahin kein Vielfaches einer Primzahl war, ist current selbst eine Primzahl und wird zum Array hinzugefügt.

current | primes 3 | [[3, 6]] 5 | [[3, 6], [5, 10]] 7 | [[3, 6], [5, 10], [7, 14]] 9 | [[3, 9], [5, 10], [7, 14]] 11 | [[3, 12], [5, 10], [7, 14], [11, 22] 13 | [[3, 15], [5, 10], [7, 14], [11, 22], [13, 26]] 15 | [[3, 15], [5, 10], [7, 14], [11, 22], [13, 26]] 17 | [[3, 18], [5, 10], [7, 14], [11, 22], [13, 26], [17, 34]] 19 | [[3, 21], [5, 10], [7, 14], [11, 22], [13, 26], [17, 34], [19, 38]] 21 | [[3, 21], [5, 10], [7, 14], [11, 22], [13, 26], [17, 34], [19, 38]] 23 | [[3, 24], [5, 10], [7, 14], [11, 22], [13, 26], [17, 34], [19, 38], [23, 46]] 25 | [[3, 27], [5, 25], [7, 14], [11, 22], [13, 26], [17, 34], [19, 38], [23, 46]] 27 | [[3, 27], [5, 25], [7, 14], [11, 22], [13, 26], [17, 34], [19, 38], [23, 46]] 29 | [[3, 30], [5, 30], [7, 14], [11, 22], [13, 26], [17, 34], [19, 38], [23, 46], [29, 58]] 31 | [[3, 33], [5, 35], [7, 14], [11, 22], [13, 26], [17, 34], [19, 38], [23, 46], [29, 58], [31, 62]] 33 | [[3, 33], [5, 35], [7, 14], [11, 22], [13, 26], [17, 34], [19, 38], [23, 46], [29, 58], [31, 62]] 35 | [[3, 36], [5, 35], [7, 14], [11, 22], [13, 26], [17, 34], [19, 38], [23, 46], [29, 58], [31, 62]] 37 | [[3, 39], [5, 40], [7, 14], [11, 22], [13, 26], [17, 34], [19, 38], [23, 46], [29, 58], [31, 62], [37, 74]] 39 | [[3, 39], [5, 40], [7, 14], [11, 22], [13, 26], [17, 34], [19, 38], [23, 46], [29, 58], [31, 62], [37, 74]] 41 | [[3, 42], [5, 45], [7, 14], [11, 22], [13, 26], [17, 34], [19, 38], [23, 46], [29, 58], [31, 62], [37, 74], [41, 82]] 43 | [[3, 45], [5, 45], [7, 14], [11, 22], [13, 26], [17, 34], [19, 38], [23, 46], [29, 58], [31, 62], [37, 74], [41, 82], [43, 86]] 45 | [[3, 45], [5, 45], [7, 14], [11, 22], [13, 26], [17, 34], [19, 38], [23, 46], [29, 58], [31, 62], [37, 74], [41, 82], [43, 86]] 47 | [[3, 48], [5, 50], [7, 14], [11, 22], [13, 26], [17, 34], [19, 38], [23, 46], [29, 58], [31, 62], [37, 74], [41, 82], [43, 86], [47, 94]] 49 | [[3, 51], [5, 50], [7, 49], [11, 22], [13, 26], [17, 34], [19, 38], [23, 46], [29, 58], [31, 62], [37, 74], [41, 82], [43, 86], [47, 94]] 51 | [[3, 51], [5, 50], [7, 49], [11, 22], [13, 26], [17, 34], [19, 38], [23, 46], [29, 58], [31, 62], [37, 74], [41, 82], [43, 86], [47, 94]] 53 | [[3, 54], [5, 55], [7, 56], [11, 22], [13, 26], [17, 34], [19, 38], [23, 46], [29, 58], [31, 62], [37, 74], [41, 82], [43, 86], [47, 94], [53, 106]]

☞ Implementierung: eratosthenesIteratorFunction.js ∙ Testseite

function eratosthenesIteratorFunction()
{
	let current = 2, primes = [];
		
	return {
		next: function()
		{
			let isPrime;
			
			if (current === 2)
			{
				current--; /* following `current += 2` results in 3 */
				return { value: 2, done: false };
			}
			
			do
			{
				current += 2;
				
				if (current >= Number.MAX_SAFE_INTEGER)
				{
					return { done: true };
				}
				
				let sqrtCurrent = Math.sqrt(current);
				isPrime = true;
				
				for (let i = 0; isPrime && primes.length && primes[i][0] <= sqrtCurrent; i++)
				{
					while (primes[i][1] < current)
					{
						primes[i][1] += primes[i][0];
					}
				
					isPrime = (primes[i][1] !== current);
				}
			}
			while (!isPrime);
			
			primes.push([current, 2 * current]);						
			return { value: current, done: false };
		}
	};
}

Da bislang kein anständiger Browser BigInt unterstützt, hab ich das zunächst mit normalen Zahlen implementiert. Und dann nochmal: eratosthenesIteratorFunction-bigint.js.

Welches Script geladen wird, wird per feature detection ermittelt:

<script>
	if (typeof BigInt === 'function')
	{
		document.write('<script src="eratosthenesIteratorFunction-bigint.js"><\/script>');
	}
	else
	{
		document.write('<script src="eratosthenesIteratorFunction.js"><\/script>');
	}
</script>

Ist document.write() an der Stelle OK oder gibt’s da was Besseres?

LLAP 🖖

[Rolf B]

Hallo,

hier ist meine Lösung, 1:1 kopiert aus der Nachricht an 1UP. Sie verwendet BigInt, und ist vermutlich deshalb schneller, weil meine Klasse SieveFactor es vermeidet, bei der sieve(c)-Prüfung zu dividieren. Eine BigInt Division dürfte relativ langsam sein. Deswegen addiere ich hoch - also genau das, was man in Erastosthenes so macht. Die Kunst war, die Siebschleife jedes Primfaktors unterbrechbar zu machen und nur bei Bedarf so weit wie nötig laufen zu lassen.

Die Geschwindigkeit lässt sich übrigens beinahe verdoppeln (bei mir von 3500ms auf 2000ms für die Primzahlen bis 1000.000), wenn man Speicher investiert und dem SieveFactor ein Property fsquare gönnt, in dem das Quadrat des Faktors steht. Dann muss man in isAbort nicht jedesmal neu quadrieren. Ich habe das mal auskommentiert hinzugefügt. Das Doppelte des Faktors zu speichern um eine Addition in der while-Schleife zu sparen hat sich nicht gelohnt.

Speicher für unnötige BigInt Objekte (weil die meisten SieveFactor Objekte nicht zum Sieben gebraucht werden) könnte man noch sparen, indem man this.value und this.fsquare erst in der sieve-Methode erzeugt, wenn diese das erste Mal verwendet wird. Die Abfrage auf Initialisiertheit bremst sieve aber etwas ab - es sei denn, man hext sich was mit Funktionsreferenzen zurecht. Habe ich getestet, aber bei den Zahlen bis 1000.000 ist der Speicher kaum relevant und die Laufzeit unterscheidet sich so wenig, dass es in den Mess-Schwankungen untergeht. Die Hexerei SCHEINT ein paar ms zu bringen, aber bei Messwerten von 1900ms bis 2050ms ist das nicht signifikant genug.

Akrobatische Kunststücke auf Trampolins waren mir nicht geheuer, das hab ich seingelassen.

let getPrimes = (function() {
   // SieveFactor repräsentiert eine Primzahl und ihre (2n+1)-fachen für den
   // Erastothenes-Algorithmus und stellt eine Eliminier-Schleife für einen
   // Primfaktor im Siebalgorithmus dar, die gerade so weit läuft wie für einen
   // Kandidaten nötig ist und dann Pause macht.
   // Die (2n)-fachen des Primfaktors interessieren nicht, das sind
   // gerade Zahlen und werden vom Generator gar nicht erst angefragt.
   class SieveFactor {
      // Speichere das 2n+1-fache als value-Property
      // Hat diverse Vorteile: es ist fixer und man muss nicht wissen, ob n ein BigInt ist 
      // oder nicht. 
      constructor(n) {
         this.factor = n;
         this.value = n;
//  ->   this.fsquare = n*n;
      }
      // Endebedingung: eine bekannte Primzahl ist größer als sqrt(Kandidat)
      isAbort(c) {
         return c < this.factor*this.factor;   /* c < this->fsquare */
      }
      // Versuche den Kandidaten auszusieben. Die Methode liefert true, wenn
      // die Abbruchbedingung erreicht ist, oder wenn der Kandidat ein (2n+1)-faches des
      // Faktors ist.
      sieve(c) {
         if (this.isAbort(c)) 
            return true;
         // Ist der Value kleiner als der Kandidat, ist die Erastothenes-Schleife für 
         // diesen Primfaktor noch nicht weit genug gelaufen. Diese Durchläufe jetzt
         // durchführen. 
         while (this.value < c)
             this.value += this.factor + this.factor;
         // Ok, jetzt kann geprüft werden ob der Kandidat ein Vielfaches des Faktors ist.
         return this.value == c;
      }
   }

   // Generatorfunktion für Primzahlen. 
   return function* () {
      // 2 ist eine. 
      yield BigInt(2);
   
      // Gefundene Siebfaktoren
      let factors = [];

      // Ab geht's, Endlosschleife ab 3 in 2-er Schritten 
      for (let candidate = BigInt(3); true; candidate += BigInt(2)) {
         // Versuche den Kandidaten auszusieben
         let factor = factors.find(s => s.sieve(candidate));
         // Kein Sandkorn oder eins mit Abbruch-Bedingung -> Kandidat ist prim
         if (!factor || factor.isAbort(candidate)) {
            yield candidate;
            factors.push(new SieveFactor(candidate));
         }
      }
   };
})();

// Test, liefert bei mir 78499 Primzahlen in 2 Sekunden.
console.clear();
console.log("begin");
let num = 0;
let start = Date.now();
for (let p of getPrimes()) {
   //console.log(p);
   num++;
   if (p > 1000000) break;
}
console.log("found " + num + " primes in " + (Date.now()-start) + "ms");

Rolf