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

71–80 of 102 posts

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

#71

Post by yard2010 »

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.

Fun fact about the pumping lemma - my best friend's grandparent worked on it (Eli Shamir). When we were taught it during my bsc the TA who knew he was the grandson of one of the inventors, asked during the lecture where he was, if he could say something about his grandfather, and it turns out he played hockey from the class to work on something else, embarrassing!

The pumping lemma is a great milestone in this field, so simple, yet so powerful.

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

#73

Post by stevage »

oneeyedpigeon wrote: post #60
stevage wrote: post #29

Took me a while to realise that it is not actually 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. In other words, it can't tell whether "3" is prime, unless you express it as "111". Much less exciting.

> 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.

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

#74

Post by venusenvy47 »

vignesh_warar wrote: post #4

Interesting! If anyone is seeking a math formula for primes, here is one: https://en.wikipedia.org/wiki/Formula_for_primes There is also a good YouTube video that explains this: https://www.youtube.com/watch?v=j5s0h42GfvM

That's cool. I had no idea there was a symbol for the floor function.

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

#75

Post by remram »

yard2010 wrote: post #71
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.

Fun fact about the pumping lemma - my best friend's grandparent worked on it (Eli Shamir). When we were taught it during my bsc the TA who knew he was the grandson of one of the inventors, asked during the lecture where he was, if he could say something about his grandfather, and it turns out he played hockey from the class to work on something else, embarrassing! The pumping lemma is a great milestone in this field,…

> he played hockey from the class to work on something else

Sorry I can't parse that

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

#76

Post by thedailymail »

remram wrote: post #75
yard2010 wrote: post #71

Earlier quoted context omitted.

Fun fact about the pumping lemma - my best friend's grandparent worked on it (Eli Shamir). When we were taught it during my bsc the TA who knew he was the grandson of one of the inventors, asked during the lecture where he was, if he could say something about his grandfather, and it turns out he played hockey from the class to work on something else, embarrassing! The pumping lemma is a great milestone in this field,…

> he played hockey from the class to work on something else Sorry I can't parse that

I think hockey is supposed to be hooky.

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

#77

Post by dgfitz »

yard2010 wrote: post #71
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.

Fun fact about the pumping lemma - my best friend's grandparent worked on it (Eli Shamir). When we were taught it during my bsc the TA who knew he was the grandson of one of the inventors, asked during the lecture where he was, if he could say something about his grandfather, and it turns out he played hockey from the class to work on something else, embarrassing! The pumping lemma is a great milestone in this field,…

Did you mean "played hooky" instead of "played hockey" by chance? :)

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

#78

Post by jappgar »

remram wrote: post #75
yard2010 wrote: post #71

Earlier quoted context omitted.

Fun fact about the pumping lemma - my best friend's grandparent worked on it (Eli Shamir). When we were taught it during my bsc the TA who knew he was the grandson of one of the inventors, asked during the lecture where he was, if he could say something about his grandfather, and it turns out he played hockey from the class to work on something else, embarrassing! The pumping lemma is a great milestone in this field,…

> he played hockey from the class to work on something else Sorry I can't parse that

Pretty sure they meant "playing hooky" :)

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

#80

Post by cubefox »

mmarx wrote: post #69
cubefox wrote: post #63

Earlier quoted context omitted.

The problem with the unary numeral system is that numerals grow linearly with value, while for binary (ternary etc) they only grow logarithmically. So they need much less space and can be much faster read and written. An algorithm with relies on unary numerals probably has worse computational complexity than one that uses binary or higher.

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 faster than binary.

In fact, I think it's pretty clear that unary representation is slower and takes more space. 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.

Post reply on HN