it's highly inefficient tho
Regular Expression That Checks If A Number Is Prime
111–117 of 117 posts
Re: Regular Expression That Checks If A Number Is Prime
#112Can't quite get this to work in vim [1]: \(^1\{-,1}$\)\|\(^\(11\+\)\1\+$\) The two parts match what you'd expect on their own but the OR-ing screws it up: it means the whole regex matches everything . Is this something vim gets right and every other engine wrong, the other way around, or...? _____________ [1] I'm matching 1's rather than dots to avoid highlighting every bit of text ever anywhere all the time. Also, t…
> Also, that way it's so much more pleasing to the eye and easy to read, don't you think? No, it's harder to read. For ease of reading, you need to match something that isn't already part of the expression, like 2s or Ks.
>> No, it's harder to read.
Don't worry, I had my humour removed at birth also. It grows back, eventually.
Re: Regular Expression That Checks If A Number Is Prime
#113Hi! I wet & wanna masturbate with you now. We will play? Im here - http://u.to/aeg3Dw
Re: Regular Expression That Checks If A Number Is Prime
#114how does it fare on time complexity compared to normal tests like say AKS?
It's very clever, but obnoxiously slow. It's useful for code golf and as a pretty impressive party trick. But like your banker will not be impressed with your college funding plan of pulling a quarter out of his ear, this is not going to make it in any real use. Imagine naive absolute-beginner-programmer trial division. This is worse. Now add the overhead of counting via regex backtracking and integer comparison via…
Why is AKS only of theoretical interest? Isn't it proven to be a deterministic test of primality?
Also, what is the fastest way to test for primality that's practically feasible?
Re: Regular Expression That Checks If A Number Is Prime
#115Earlier 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.
Perl started with Henry Spenser's regular expression library, which was written in the mid-1980s. That got used in a lot of places, and may have been used in sed. It includes backreferences. I don't know what predates that.
Perl used that as a starting place and began adding extensions such as the difference between .* and .*?.
So using "non-regular thing" as a regular expression predates Perl. But the dialect we standardized on with the features people now expect is due to Perl's influence.
Re: Regular Expression That Checks If A Number Is Prime
#116Earlier quoted context omitted.
perl -wle 'print "Prime" if (1 x shift) !~ /^1?$|^(11+?)\1+$/' [number] (My first exposure to that was in '97 or so as a .sig from abigail in comp.lang.perl.misc)
Some asshole gave me this in an interview for a Perl dev job, and asked me what it did.
Wasn't at an interview, but I remember quizzing the "new guy" Perl dev with "So explain what this one does":
@sorted = map { $_->[0] }
sort { $a->[1] cmp $b->[1] }
map { [$_, foo($_)] }
@unsorted;
Re: Regular Expression That Checks If A Number Is Prime
#117Earlier quoted context omitted.
It's very clever, but obnoxiously slow. It's useful for code golf and as a pretty impressive party trick. But like your banker will not be impressed with your college funding plan of pulling a quarter out of his ear, this is not going to make it in any real use. Imagine naive absolute-beginner-programmer trial division. This is worse. Now add the overhead of counting via regex backtracking and integer comparison via…
Why is AKS only of theoretical interest? Isn't it proven to be a deterministic test of primality? Also, what is the fastest way to test for primality that's practically feasible?
It is a proven deterministic test of primality. We already had those before AKS, and they are significantly faster than AKS (even the various improvements). But they don't check all the boxes that are useful for stating things in computational complexity proofs without a paragraph of weasel words. So from the theory side of things, it's great since we don't particularly care about the actual execution time, but the asymptotic behavior and whether it is solidly shown to be in P.
Lots of math packages have deterministic primality tests, but none use AKS as a primary method, because AKS offers no benefits over other methods and is many orders of magnitude slower.
For inputs of special form, there are various fast tests. E.g. Mersenne numbers, Proth numbers, etc.
The fastest method depends on the input size and how much work you want to put in. For tiny inputs, say less than 1M, trial division is typically fastest. For 32-bit inputs, a hashed single Miller-Rabin test is fastest. For 64-bit inputs, BPSW is fastest (debatable vs. hashed 2/3 test). The BLS methods from 1975 are significantly faster than AKS up to at least 80 digits, but ECPP and APR-CL easily beat those. ECPP is the method of choice for 10k+ digit numbers, with current records a little larger than 30k digits.