3 ms·

So in summary there is no special thing here about this being a regex: the program described by it basically just brute force tries to divide the given number b

So in summary there is no special thing here about this being a regex: the program described by it basically just brute force tries to divide the given number by every number smaller than it, it’s just written in a way that isn’t obvious to understand. That’s not to detract from the excellent post, just that this isn’t a mathematical trick that exploits some structure of primes but rather an incredibly clever way to write a computer program.

userbinator 2y ago
...and the divide is effectively implemented by "multiplication", i.e. repeating the same match group (via backreference). It's one of those things that looks impossible at first, but you instantly turn to "of course that's how it works!" once you understand. That said, I still think this article is on the verbose side. Also, strictly speaking, it's not a "regular expression" but a "regex", as backreferences make the language more powerful than regular. https://en.wikipedia.org/wiki/Regular_expression#Patterns_for_non-regular_languages https://en.wikipedia.org/wiki/Regular_expression#Patterns_fo...
- Suppafly 2y ago
  >Also, strictly speaking, it's not a "regular expression" but a "regex" And regex is short for regular expression, so you've essentially said nothing.
  - shagie 2y ago
    https://web.archive.org/web/20100112232513/http://dev.perl.org/perl6/doc/design/apo/A05.html https://web.archive.org/web/20100112232513/http://dev.perl.o... AUTHOR Larry Wall <larry@wall.org> Maintainer: Larry Wall <larry@wall.org> Date: 4 Jun 2002 Last Modified: 18 May 2006 Number: 5 Version: 7 This is the Apocalypse on Pattern Matching, generally having to do with what we call "regular expressions", which are only marginally related to real regular expressions. Nevertheless, the term has grown with the capabilities of our pattern matching engines, so I'm not going to try to fight linguistic necessity here. I will, however, generally call them "regexes" (or "regexen", when I'm in an Anglo-Saxon mood).
shagie 2y ago
Part of it also that this isn't a regular language. The PCRE is more powerful a language than a Chomsky type 3 language in that there are strings that can be matched by a PCRE (such as a prime number expressed in unary) that are not recognized in a pure regular language. Extending finite automata to efficiently match Perl-compatible regular expressions - http://dx.doi.org/10.1145/1544012.1544037 http://dx.doi.org/10.1145/1544012.1544037
- bawolff 2y ago
  I don't know why people keep pointing this out - RegEx's not being regular languages has been true for basically all of history (it is not just pcre, traditional unix (basic) regexes also have this). Most people's only experience with "regular" things have been with non-regular regexes. Grep is 51 years old at this point.
  - jraph 2y ago
    Because recognizing a prime number using an actual regular expression would prove that prime numbers form a regular language, which would be an incredible result. And somehow, some people like me are in computer science mode when reading such sentences, such reminders wakes us up: "Oh, ok, not actually regular, not such a big deal"
    - JadeNB 2y ago
      > Because recognizing a prime number using an actual regular expression would prove that prime numbers form a regular language, which would be an incredible result. It would be literally incredible, because the pumping lemma shows that it's false.
      - jraph 2y ago
        > because the pumping lemma shows that it's false Ah yes, I even used to teach this actually. Sorry for the understatement xD.
jimhefferon 2y ago
Everything is easy once you know how.
- JadeNB 2y ago
  > Everything is easy once you know how. I think that this is definitely not true. There are lots of things where an "aha!" moment makes things appear conceptually much simpler after you've internalized the framework, but there are plenty of things in what I consider my area of expertise that are still hard even though I know very well how.
GuB-42 2y ago
The thing is: regex are computer programs. The regex text is code written in a domain specific programming language that is compiled and then run against an input. It was an important point in the design of Perl 6, now named Raku. Perl already had first class support for a powerful regex variant, in Raku, they went a step further to consider it for what they really are. > In Raku, regexes are written in a domain-specific language, i.e. a sublanguage or slang. This page describes this language, and explains how regexes can be used to search for text patterns in strings in a process called pattern matching. > Fundamentally, Raku regexes are very much like subroutines...
- lizmat 2y ago
  > Fundamentally, Raku regexes are very much like subroutines... And if they're part of a grammar, they're essentially methods on a class. And a class that can be sub-classed. Or have roles mixed in, consisting of regexes.
gusfoo 2y ago
> So in summary there is no special thing here about this being a regex No, I think the story is that it's an incredible thing to implement a prime test in a regex. It was a pretty neat thing 20+ years ago when I first saw it and I reckon it's still pretty neat. The "JAPH" thing was a pretty cool thing too. perl -e '$a = q 94a75737420616e6f74686572205065726c204861636b65720a9 and ${qq$\x5F$} = q 97265646f9 and s g..g; qq e\x63\x68\x72\x20\x30\x78$&eggee; {eval if $a =~ s e..eqq qprint chr 0x$& and \x71\x20\x71\x71qeexcess}'

userbinator 2y ago

...and the divide is effectively implemented by "multiplication", i.e. repeating the same match group (via backreference). It's one of those things that looks impossible at first, but you instantly turn to "of course that's how it works!" once you understand. That said, I still think this article is on the verbose side. Also, strictly speaking, it's not a "regular expression" but a "regex", as backreferences make the language more powerful than regular. https://en.wikipedia.org/wiki/Regular_expression#Patterns_for_non-regular_languages https://en.wikipedia.org/wiki/Regular_expression#Patterns_fo...

Suppafly 2y ago
>Also, strictly speaking, it's not a "regular expression" but a "regex" And regex is short for regular expression, so you've essentially said nothing.
- shagie 2y ago
  https://web.archive.org/web/20100112232513/http://dev.perl.org/perl6/doc/design/apo/A05.html https://web.archive.org/web/20100112232513/http://dev.perl.o... AUTHOR Larry Wall <larry@wall.org> Maintainer: Larry Wall <larry@wall.org> Date: 4 Jun 2002 Last Modified: 18 May 2006 Number: 5 Version: 7 This is the Apocalypse on Pattern Matching, generally having to do with what we call "regular expressions", which are only marginally related to real regular expressions. Nevertheless, the term has grown with the capabilities of our pattern matching engines, so I'm not going to try to fight linguistic necessity here. I will, however, generally call them "regexes" (or "regexen", when I'm in an Anglo-Saxon mood).

shagie 2y ago

Part of it also that this isn't a regular language. The PCRE is more powerful a language than a Chomsky type 3 language in that there are strings that can be matched by a PCRE (such as a prime number expressed in unary) that are not recognized in a pure regular language. Extending finite automata to efficiently match Perl-compatible regular expressions - http://dx.doi.org/10.1145/1544012.1544037 http://dx.doi.org/10.1145/1544012.1544037

bawolff 2y ago
I don't know why people keep pointing this out - RegEx's not being regular languages has been true for basically all of history (it is not just pcre, traditional unix (basic) regexes also have this). Most people's only experience with "regular" things have been with non-regular regexes. Grep is 51 years old at this point.
- jraph 2y ago
  Because recognizing a prime number using an actual regular expression would prove that prime numbers form a regular language, which would be an incredible result. And somehow, some people like me are in computer science mode when reading such sentences, such reminders wakes us up: "Oh, ok, not actually regular, not such a big deal"
  - JadeNB 2y ago
    > Because recognizing a prime number using an actual regular expression would prove that prime numbers form a regular language, which would be an incredible result. It would be literally incredible, because the pumping lemma shows that it's false.
    - jraph 2y ago
      > because the pumping lemma shows that it's false Ah yes, I even used to teach this actually. Sorry for the understatement xD.

jimhefferon 2y ago

Everything is easy once you know how.

JadeNB 2y ago
> Everything is easy once you know how. I think that this is definitely not true. There are lots of things where an "aha!" moment makes things appear conceptually much simpler after you've internalized the framework, but there are plenty of things in what I consider my area of expertise that are still hard even though I know very well how.

GuB-42 2y ago

The thing is: regex are computer programs. The regex text is code written in a domain specific programming language that is compiled and then run against an input. It was an important point in the design of Perl 6, now named Raku. Perl already had first class support for a powerful regex variant, in Raku, they went a step further to consider it for what they really are. > In Raku, regexes are written in a domain-specific language, i.e. a sublanguage or slang. This page describes this language, and explains how regexes can be used to search for text patterns in strings in a process called pattern matching. > Fundamentally, Raku regexes are very much like subroutines...

lizmat 2y ago
> Fundamentally, Raku regexes are very much like subroutines... And if they're part of a grammar, they're essentially methods on a class. And a class that can be sub-classed. Or have roles mixed in, consisting of regexes.

gusfoo 2y ago

> So in summary there is no special thing here about this being a regex No, I think the story is that it's an incredible thing to implement a prime test in a regex. It was a pretty neat thing 20+ years ago when I first saw it and I reckon it's still pretty neat. The "JAPH" thing was a pretty cool thing too. perl -e '$a = q 94a75737420616e6f74686572205065726c204861636b65720a9 and ${qq$\x5F$} = q 97265646f9 and s g..g; qq e\x63\x68\x72\x20\x30\x78$&eggee; {eval if $a =~ s e..eqq qprint chr 0x$& and \x71\x20\x71\x71qeexcess}'