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

Regular Expression That Checks If A Number Is Prime

iluxonchik.github.io

Post reply on HN
Print view View original

101–110 of 117 posts

Re: Regular Expression That Checks If A Number Is Prime

#101

Post by OskarS »

Chinjut wrote: post #76
School-Cotton wrote: post #67

Earlier quoted context omitted.

"regular" has a fairly simple mathematical definition: the set of languages that can be matched with a finite state automaton. You can think of this as the languages that can be matched with an algorithm that is bounded (i.e., O(1) ) in memory, no matter what is the string to be matched. The following pseudocode is not bounded in memory -- can you guess why? bool is_prime(Number n) { for (Number i = 2; i

The value i can take an a priori unbounded amount of memory. It should be noted, so can the value n, but in defining regular languages in this way, we allow our O(1) memory algorithms to be fed the characters of an a priori unbounded input string one by one sequentially.

Yeah, the O(1) refers to the size of the EXTRA memory you need, aside from the input. Defining it any other way would be strange. So, for instance, binary search over a sorted list needs O(log n) of memory (for the same reason as the prime algorithm, the pointer in the array is size O(log n) of the size of the array), even though the input is O(n).

Re: Regular Expression That Checks If A Number Is Prime

#102

Post by OskarS »

gerty wrote: post #81
School-Cotton wrote: post #67

Earlier quoted context omitted.

"regular" has a fairly simple mathematical definition: the set of languages that can be matched with a finite state automaton. You can think of this as the languages that can be matched with an algorithm that is bounded (i.e., O(1) ) in memory, no matter what is the string to be matched. The following pseudocode is not bounded in memory -- can you guess why? bool is_prime(Number n) { for (Number i = 2; i

FWIW, (i < n) can be replaced by (i <= floor(sqrt(n))) to avoid unnecessary iterations.

Yeah, obviously, there are lots of ways to improve that code. First off all, much more efficient to to do (i * i You can also do a separate test for 2, then start at 3 and use i+=2 instead of i++, that cuts the test time in half. Once you've done that, you can observe that all primes are 6k +/- 1 except 2 and 3, which makes your code 3 times faster than the naive version.

At this point, you've basically got a simple wheel primality testing algorithm going, so why not go all the way?

I don't think the parent poster was making the point that his was the most efficient algorithm for testing primes. I think his point was that regular numbers are O(log n) in CS terms, not O(1), which is not obvious at first.

Re: Regular Expression That Checks If A Number Is Prime

#103

Post by UlyssesSKrunk »

greydius wrote: post #55
db48x wrote: post #39

Earlier quoted context omitted.

"regular language" is a mathematical term. You can add any features you want to your matcher, but some features allow you to match languages that are not "regular". However, most programmers are not mathematicians or computer scientists, and so are effectively using lay terminology which is similar to but not precisely the same as the mathematical terminology. Most programmers only care that their regex library allow…

I don't buy the layman argument. Programmers might not be mathematicians or computer scientists, but they should be professionals and held to the same standards as professionals in other fields. For example, a mechanical engineer doesn't use a "laymen" definition of tensile strength when choosing materials for a design.

What the fuck are you talking about? Those aren't even remotely the same thing at all.

Re: Regular Expression That Checks If A Number Is Prime

#104

Post by OskarS »

eponeponepon wrote: post #64
greydius wrote: post #55

Earlier quoted context omitted.

I don't buy the layman argument. Programmers might not be mathematicians or computer scientists, but they should be professionals and held to the same standards as professionals in other fields. For example, a mechanical engineer doesn't use a "laymen" definition of tensile strength when choosing materials for a design.

No, but he probably does use layman's terms when describing molecular lattices and electron shells. If he ever does. The point here is that users of (colloquial) regular expressions, however professional they are or aren't, are just engaging with the surface of a deeper set of mathematical principles that require greater nuances of meaning to discuss than their applications do.

I basically agree, but I would say that a slightly deeper understanding of regular expressions is a really useful thing to know for basically all professional programmers. If for no other reason they can recognize the "pathological" cases where backtracking implementations (i.e. almost all modern regex implementations) would need until the heat death of the universe to evaluate.

Re: Regular Expression That Checks If A Number Is Prime

#105

Post by dllthomas »

Normal_gaussian wrote: post #69
dllthomas wrote: post #65

Earlier quoted context omitted.

When were back-references introduced in sed?

http://sed.sourceforge.net/sedfaq3.html > Grouping and backreferences: All versions of sed support grouping and backreferences on the LHS and backreferences only on the RHS.

I saw that. I wasn't sufficiently confident as to whether it meant "all historical versions" or just "all current versions."

If the former, then it predated perl by quite a bit, of course.

Re: Regular Expression That Checks If A Number Is Prime

#106

Post by Chinjut »

OskarS wrote: post #101
Chinjut wrote: post #76

Earlier quoted context omitted.

The value i can take an a priori unbounded amount of memory. It should be noted, so can the value n, but in defining regular languages in this way, we allow our O(1) memory algorithms to be fed the characters of an a priori unbounded input string one by one sequentially.

Yeah, the O(1) refers to the size of the EXTRA memory you need, aside from the input. Defining it any other way would be strange. So, for instance, binary search over a sorted list needs O(log n) of memory (for the same reason as the prime algorithm, the pointer in the array is size O(log n) of the size of the array), even though the input is O(n).

Yup. Note that the method of specifically being fed the input sequentially, one by one, means that, for example, "Strings of odd length whose middle character is 'X'" does not comprise a regular language, even though one might naively reason this to be trivial to detect with O(1) memory ("Just go look at the middle character!").

Re: Regular Expression That Checks If A Number Is Prime

#108

Post by Normal_gaussian »

dllthomas wrote: post #105
Normal_gaussian wrote: post #69

Earlier quoted context omitted.

http://sed.sourceforge.net/sedfaq3.html > Grouping and backreferences: All versions of sed support grouping and backreferences on the LHS and backreferences only on the RHS.

I saw that. I wasn't sufficiently confident as to whether it meant "all historical versions" or just "all current versions." If the former, then it predated perl by quite a bit, of course.

Ah I get you.

I've tried finding some source for early versions but all the links I've found are dead. It's an interesting question!

Re: Regular Expression That Checks If A Number Is Prime

#109

Post by btilly »

Chinjut wrote: post #45
btilly wrote: post #33

Earlier quoted context omitted.

No, it is not. You can invent a variety of notations to describe a DFA. But you can't change the formal definition of a DFA, or what kinds of things a DFA can match without making it not a DFA.

I'll say to you what I said above, but even moreso: Er... I'm not sure what you're saying here, so I'll clarify what I was saying. What I mean is, we all agree on what DFAs are, and so we all agree on what regular languages in the original, Kleene sense are. But once we start admitting non-regular languages into our notion of "regular expression" because they're "straightforwardly tacked on", it's unclear what the li…

What I am saying is that you can come up with a lot of extensions of the basic regular expression language. But there is no subjectivity at all in whether the extensions can be implemented by a DFA. Either you can, or you can't.

Re: Regular Expression That Checks If A Number Is Prime

#110

Post by thaumasiotes »

iluxonchik wrote: post #95
thaumasiotes wrote: post #80

Earlier quoted context omitted.

I'm another one who thinks the letter "in front" is the one that comes first. May I ask how you were thinking about the "front" and "back" of text?

Well, we read from left to right, naturally that is the order of the letters, so the one on the right is "in front" of the left one.

I guess if you imagine a person walking from the beginning of the text to the end, their front (the side with the face on it) would face the end of the text.

But English never conceives of text in this manner; we view text as being arranged in a chronological order, where text that occurs chronologically earlier comes "before" text that occurs chronologically later. This mirrors the application of "before" and "after" to time in the rest of the language. Whether you conceive of reading as the reader traveling through text from the beginning to the end, or as text arriving at the reader, the reader will always encounter text on the left before text on the right, and therefore the text on the left is in front of the text on the right.

(In the only other language I'm qualified to talk about this for, mandarin chinese, earlier and later time might be indicated by either of two spatial metaphors: "up" for the past and "down" for the future ["up" is also used as a metaphor for beginning things]; or "front" for earlier and "back" for later. When text is read from left to right, "front" is used to indicate text on the left.)

Here ( http://www.friesian.com/egypt.htm ) is someone writing about the ancient Egyptian writing system, inadvertently assuming that the front of text is its beginning and the back of text is its end:

> Note that Egyptian glyphs have a front and a back. All the images above and below face to the left, [...] which indicates that the text is to be read from left to right. This is conformable with the usage of English and other European languages. However, although this would be familiar and agreeable to the Egyptians, Egyptian usage was ordinarily to write from right to left, as today is done in Hebrew and Arabic. They indicated this direction by having all the glyphs face to the right instead of to the left

(Egyptian glyphs often depict a person or an animal with an actual face. They face towards the beginning of the text, not the end.)

You seem to speak English at a fully native level, based on your writeup here. (Although you don't seem to have picked up on the idea that if a quantifier "precedes" a '?', it must be "in front" of that '?'.) Do you have another native language? Are you based in a country that primarily speaks some other language? What is the metaphor that determines that later words are "in front" of earlier words?

Post reply on HN