Aus dem Leben gegriffen: Von einer Primzahl, die keine war
Kommentare

Es gibt einen regulären Ausdruck, der eine Zahl daraufhin überprüft, ob sie eine Primzahl ist oder nicht. Zusammen mit einem Freund hat Andrei Zmievksi damit experimentiert – und herausgefunden:

Es gibt einen regulären Ausdruck, der eine Zahl daraufhin überprüft, ob sie eine Primzahl ist oder nicht. Zusammen mit einem Freund hat Andrei Zmievksi damit experimentiert – und herausgefunden: abstract, pure, good ideas can still fail in the messy world of software and hardware.

/^1?$|^(11+?)1+$/

Das also war der Stein, der alles ins Rollen brachte. Alles was man benötigt ist eine Zahl, die in Einsen dargestellt wird – aus einer 7 wird also 1111111, aus einer 3 111, und so weiter. Danach geschieht folgendes:

The (11+?) sub-pattern matches strings 11, 111, etc. The 1+ matches whatever the sub-pattern matched, one or more times. So on the first try, the engine will match 11 and then attempt to match the same thing one or more times in the rest of the string. If it succeeds, the number is not a prime. Why? Because it just proved that the length of the string is divisible by 2 (the length of 11), therefore the original number is divisible by 2. If the overall match fails, the engine backtracks to the beginning and tries to match 111 two or more times and so on successively. If the first sub-pattern gets long enough (n/2 basically), and the overall match still fails, the number is a prime.Andrei Zmievski, 2010

So einfach wie genial. Leider sind die beiden ziemlich schnell auf ein Problem gestoßen: wurde die erstellte PHP-Funktion mit 99999999 gefüttert, kam ein Ergebnis heraus, das nicht stimmen konnte. Also schrieb Andrei einen Test, der die Ergebnisse der Funktion mit den Sieve-Algorithmus verglich, um herauszufinden, wo es hakt. Und siehe da: das erste fehlerhafte Ergebnis lieferte die Zahl 22201.

Nach einigem tüfteln kam er schließlich auf des Rätsels Lösung. Das Problem liegt in der Einstellung pcre.backtrack_limit. In our case, backtracking is used to break up the string of 1s into successively larger chunks, and, with very long strings, the engine may run into this backtracking limit, which is set to 100000 by default. My guess was that with the 22201-character-long string, the default was not enough. Once the limit is reached, the match fails, and the number is declared prime.

Eine Erhöhung des Limits brachte dann das gewünschte Ergebnis. Allerdings auch eine unschöne Randerscheinung: 14 Sekunden brauchte das Programm. Auf einem neuen i5 MacBook Pro.

Natürlich ist dieser reguläre Ausdruck für den Einsatz in der richtigen Welt kaum zu gebrauchen – aber wie Andrei schon sagte: just appreciate it for its elegance.

Unsere Redaktion empfiehlt:

Relevante Beiträge

Meinungen zu diesem Beitrag

X
- Gib Deinen Standort ein -
- or -