Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A regular expression to check for prime numbers (2007)

noulakaz.net

Post reply on HN
Print view View original

91–100 of 102 posts

Re: A regular expression to check for prime numbers (2007)

#91

Post by toth »

eru wrote: post #64
tylerhou wrote: post #7

Technically not a regular expression, as (intuitively) the backreference has to “count” the number of 1’s that were matched. Regular expressions are equivalent to finite state machines, which cannot count arbitrarily high (any state machine that can count arbitrarily high needs an infinite number of states, since there are infinite natural numbers). The 2022 discussion has a more formal proof using the pumping lemma.

If you want something with an actual regular expression, have a look at https://codegolf.stackexchange.com/questions/3503/hard-code-... which is a code golf for regular expressions to test divisibility by 7.

Very cool! The top answer has a 12,731 character regular expression that matches base 10 numbers that are divisible by 7. (There is an answer with only 105 characters, but that uses .NET "regular expressions" which have some pretty gnarly extensions and are definitely not regular languages).

The regex itself is generated from a relatively simple DFA based on mod 7 arithmetic on digits using a program (JFLAP apparently, not familiar).

Just from looking at the start of the regex you can see some cool things. For instance, TIL that all numbers of the form 1555....55554 and 85555....5554 are multiples of 7. Fun exercise to prove it.

Re: A regular expression to check for prime numbers (2007)

#93

Post by mmarx »

cubefox wrote: post #80
mmarx wrote: post #69

Earlier quoted context omitted.

Actually, an algorithm working on unary input tends to have better computational complexity than an algorithm working on binary input: an algorithm that is polynomial in the numeric value will be a polynomial algorithm on unary input, but an exponential algorithm on binary input. Such algorithms are usually called pseudo-polynomial[0]; indeed, this kind of primality testing is pseudo-polynomial. [0] https://en.wikipe…

> an algorithm that is polynomial in the numeric value will be a polynomial algorithm on unary input, but an exponential algorithm on binary input. That's comparing apples to oranges, because the two input types have vastly different lengths relative to their value. Unary input length itself grows exponentially with binary input length, for the same numeric value, cancelling out the unary advantage. So unary isn't fa…

> That's comparing apples to oranges, because the two input types have vastly different lengths relative to their value.

It really is not, because complexity is fundamentally a function of _the length of the input_ (specifically: it measures how the runtime (or space usage) grows with growing input). If you have longer input, your Turing machine can spend more time to compute its answer. Also note that this assumes that _the input_ is encoded in unary, if you get binary input and need to spend time and space to convert it to unary representation, sure, that will lead to an exponential blow-up.

Edit: > Just think about the rough number of steps you would need to add or even multiply two very large numbers, e.g. in a Turing machine. It would be obviously vastly more if the numbers are given in unary rather than in binary.

First, note that those are not actually pseudo-polynomial, as the number of steps needed for addition (or multiplication) depend on the number of digits, not the numeric values involved. Yet, even here unary encoding _does not have worse complexity_, since you still take polynomially many steps in the length of the input (i.e., the length of the unary encodings of the input values). Yes, all the inputs will be exponentially larger, so in practice it's certainly not the better algorithm, but _the complexity_ is not worse, since that's only concerned with the asymptotic behaviour.

Re: A regular expression to check for prime numbers (2007)

#94

Post by oneeyedpigeon »

stevage wrote: post #73
oneeyedpigeon wrote: post #60

Earlier quoted context omitted.

> validating whether a given number is a prime number or not ... It is validating whether a string of consecutive 1's has a prime length. I don't think you've really explained why those two things are different. They're different methods but they're checking the exact same thing.

Well, no. The two things take input in two different forms, and one is substantially easier than the other. It's a bit like if you claimed that a program that voice to text is the same as one that does text to text.

You're totally right; I apologise.

Re: A regular expression to check for prime numbers (2007)

#95

Post by Tainnor »

SerpentJoe wrote: post #90
underdeserver wrote: post #43

Earlier quoted context omitted.

Nobody claimed that.

It's true, the article doesn't make that claim. We think of primes as being mysterious and out of reach, and we're conditioned to think "mathematical / computational breakthrough" when we read the words "prime number" in a headline, but this is only because we've found all of them that aren't huge enough to be mysterious. Computing prime numbers is trivial as long as you don't mind them being the same ones everybody…

Not sure what you mean by "trivial", I mean a simple prime finding algorithm is easy to write down, but it will be very inefficient, especially for large primes (the very ones you use in cryptography).

Coming up with an efficient prime-finding algorithm like Miller-Rabin* is far from trivial.

* Technically it's just a prime-checking algorithm, but you can just generate random numbers until you've verified one of them is prime.

Re: A regular expression to check for prime numbers (2007)

#96

Post by cubefox »

mmarx wrote: post #93
cubefox wrote: post #80

Earlier quoted context omitted.

> an algorithm that is polynomial in the numeric value will be a polynomial algorithm on unary input, but an exponential algorithm on binary input. That's comparing apples to oranges, because the two input types have vastly different lengths relative to their value. Unary input length itself grows exponentially with binary input length, for the same numeric value, cancelling out the unary advantage. So unary isn't fa…

> That's comparing apples to oranges, because the two input types have vastly different lengths relative to their value. It really is not, because complexity is fundamentally a function of _the length of the input_ (specifically: it measures how the runtime (or space usage) grows with growing input). If you have longer input, your Turing machine can spend more time to compute its answer. Also note that this assumes t…

When we deal with algorithms involving numbers, we are interested in actual numbers, not in their numeral representation. It would be absurd to compare unary and binary addition relative to the same numeral length. We are ultimately interested in numbers, not numerals. Adding one million to one million is simply much faster for binary addition than for unary addition, even if unary addition has better complexity relative to its own encoding than binary addition has to its encoding. We are interested in complexity relative to the numerical value, not in the length of their respective encodings.

Edit: By the way, as the Wikipedia piece notices, the binary addition algorithm is O(log(n)) in time _relative to the value_, while unary addition is presumably O(n) relative to the value (just writing the numeral out alone takes O(n) steps). So the time complexity is in fact better. Probably the same holds for space complexity. Moreover, only in this case makes a comparison even sense, since we are comparing the same values in both cases, while for the numeral case we would be comparing the lengths of two different types of numerals, apples to oranges.

Re: A regular expression to check for prime numbers (2007)

#97

Post by finitemonkey »

petters wrote: post #33
finitemonkey wrote: post #27

Earlier quoted context omitted.

> and now they are incredibly powerful but can take basically infinite memory and time. Which is why the "RE" in the article is excrutiatingly slow, given that it needs to perform insane amounts of backtracking. In contrast, "real" regular expression checkers run in linear time. Also, nitpicking, but they take unbounded time. It's still finite.

They said “basically,” so no need to nitpick. And I’m not sure about unbounded; surely it is bounded by a suitable exponential function?

> They said “basically,” so no need to nitpick.

The inflationary use of "infinite" especially in tech crowds that should know better deserves pushback.

There are models of computation that actually model infinite computation. A well-studied one is Büchi automata, basically a generalization of finite state automata to infinite sequences.

> And I’m not sure about unbounded; surely it is bounded by a suitable exponential function?

Nope. You can nest them and for any function that you give you can produce a RE that takes longer than that function to evaluate. (That's literally what "unbounded" means. There is no bound. Doesn't mean it's "infinite". All those computations terminate, which is literally what "finite" means in this context.)

Re: A regular expression to check for prime numbers (2007)

#98

Post by finitemonkey »

staunton wrote: post #40
finitemonkey wrote: post #25

Earlier quoted context omitted.

> The machine I'm using to type this comment is also a finite state machine, as due to having non-infinite memory, it also cannot count arbitrarily high. Right. And if you really want to push that argument further then there are numbers for which your machine can't decide whether they are prime or not. Most of them, in fact, i.e., for all but a finite number of primes and non-primes, your machine can't tell. For the…

> And then people would need to take those classes as well, and not just claim they can write React apps just fine without a degree. Weird tangent. They can write React apps without a degree, can't they? What's wrong with that? The amount of complexity reasoning you need for something like that is around "this part seems slow, maybe there's a better algorithm somewhere" or "that's a lot of nested loops, maybe I can d…

> On the other hand, knowing the complexity of all algorithms and blindly assuming "good complexity = good performance" while never checking is a recipe for desaster.

Exactly. That's the difference between an actual education and having looked up some Big-O notation on Wikipedia.

Re: A regular expression to check for prime numbers (2007)

#99

Post by mmarx »

cubefox wrote: post #96
mmarx wrote: post #93

Earlier quoted context omitted.

> That's comparing apples to oranges, because the two input types have vastly different lengths relative to their value. It really is not, because complexity is fundamentally a function of _the length of the input_ (specifically: it measures how the runtime (or space usage) grows with growing input). If you have longer input, your Turing machine can spend more time to compute its answer. Also note that this assumes t…

When we deal with algorithms involving numbers, we are interested in actual numbers, not in their numeral representation. It would be absurd to compare unary and binary addition relative to the same numeral length. We are ultimately interested in numbers, not numerals. Adding one million to one million is simply much faster for binary addition than for unary addition, even if unary addition has better complexity rela…

> It would be absurd to compare unary and binary addition relative to the same numeral length.

Why? The Turing machine has no concept of numeric values, it only knows about the length of whatever the input is.

> Adding one million to one million is simply much faster for binary addition than for unary addition, even if unary addition has better complexity relative to its own encoding than binary addition has to its encoding.

From a complexity standpoint, adding one million to one million is O(1), irregardless of the encoding.

> We are interested in complexity relative to the numerical value, not in the length of their respective encodings.

But the complexity relative to the numerical value is not even well-defined, since it _depends_ on the choice of the encoding.

> By the way, as the Wikipedia piece notices, the binary addition algorithm is O(log(n)) in time _relative to the value_, while unary addition is presumably O(n) relative to the value (just writing the numeral out alone takes O(n) steps). So the time complexity is in fact better.

It really is not better. Time complexity is _always_ measured relative to the length of the input, and for binary encoding, the length of the input is O(log(n)), so, taking O(log(n)) steps for the addition is linear, same as the linear time needed for adding numbers in unary encoding (which is basically just copying the input to the output).

> Moreover, only in this case makes a comparison even sense, since we are comparing the same values in both cases, while for the numeral case we would be comparing the lengths of two different types of numerals, apples to oranges.

But _the numeral is not the input_, its _encoding_ is. This is really the whole point, and it is _precisely_ because you get different complexities for different encodings.

Re: A regular expression to check for prime numbers (2007)

#100

Post by eru »

knome wrote: post #84
eru wrote: post #66

Earlier quoted context omitted.

Alas that approach only works well for your basic regular expressions that support Kleene-Star, concatenation and union. Regular languages are also closed under intersection and taking prefix etc (see https://en.wikipedia.org/wiki/Regular_language#Closure_prope... ), and if you want to expose those operators in your regular expressions, Russ Cox's technique doesn't really work.

I suspect it should be possible to transform two intersected (K*,C,U) expressions into a new (K*,C,U) expression by walking over the two, dropping incompatible terms, reducing sets, and redistributing and expanding sub-expressions to combine the two, though I do not have time to take a serious look at this at the moment. I also suspect that this might result in a combinatorial explosion of fused terms, but that's irr…

You can still explicitly build the finite automaton for your closure-extended regular language. That one might be big, but matching is still linear in the length of the text you are searching through.

As you point out Russ Cox's method can not deal with complement and intersection. You can hack it up by putting a compiler in front, but then you might as well compile to finite automata directly. Or you use derivatives: https://en.wikipedia.org/wiki/Brzozowski_derivative or https://www.ccs.neu.edu/home/turon/re-deriv.pdf (or https://well-typed.com/blog/2020/06/fix-ing-regular-expressi... for a Haskell flavour).

> Nothing in the wiki article mentions taking a prefix, but that just sounds like `(prefix|)`?

They implicitly mention prefixes, when they talk about 'the trio operations: string homomorphism, inverse string homomorphism, and intersection with regular languages.' If I remember right, the prefix operation is:

Take a language L, restrict it to the strings that have the right prefix: `L' := L & (prefix.*)` then chop off that prefix from every member of L'.

See https://en.wikipedia.org/wiki/Quotient_of_a_formal_language which this is a special case of. The Brzozowski derivative article also explains it in more detail.

Post reply on HN