100% of the time, baby =)
If you scaled it based on the size of the integer you could get that up to 99.9% test accuracy. Like if it’s less than 10 give it 50% odds of returning false, if it’s under 50 give it 10% odds, otherwise return false.
That would make it less accurate. It’s much more likely to return true on not a prime than a prime
Correct. Not are why people are upvoting. If 10% of numbers are prime in a range, and you always guess false, you get 90% right. If you randomly guess true 10% of the time, you get ~80% right.
More random means more towards 50% correctness.
And 2,3,5,7 are primes of the first numbers, making always false 60% correct and random chance 50%
Code proof or it didn’t happen.
Extra credit for doing it in Ruby
Now you’re thinking with
portalsprimes!Makes me wonder where the actual break even would be. Like how long does making one random number take versus sins lookups. Fuck it, do it in parallel. Fastest wins.
Reminds me of this xkcd:
info
View the source to see how I embedded the picture without copying it. The hover text had to be copied though.
More like: https://xkcd.com/2236/
info
View the source to see how I embedded the picture without copying it. The hover text had to be copied though.
My favorite part of this is that they test it up to 99999 and we see that it fails for 99991, so that means somewhere in the test they actually implemented a properly working function.
No, it’s always guessing false and 99991 is prime so it isn’t right. This isn’t the output of the program but the output of the program compared with a better (but probably not faster) isprime program
Yes, that’s what I said. They wrote another test program, with a correct implementation of IsPrime in order to test to make sure the pictured one produced the expected output.
Plot twist: the test just checks to see if the input exists in a hardcoded list of all prime numbers under 100000.
I mean people underestimate how usefull lookup tables are. A lookup table of primes for example is basically always just better except the one case where you are searching for primes which is more maths than computer programming anyways. The modern way is to abstract and reimplement everything when there are much cheaper and easier ways of doing it.
more maths than computer programming anyways
Computer programming is a subset of maths and was invented by a mathematition, originally to solve a maths problem…
Yeah but they slowly develop to be their own fields. You wouldnt argue that physics is math either. Or that chemistry could technically be called a very far branch of philosophy. Computer programing, physics, etc are the applied versions of math. You are no longer studying math, you are studying something else with the help of math. Not that it matters much, just makes distinguising between them easier. You can draw the line anywhere but people do generally have a somewhat shared idea of where that lies.
Chemistry is a branch of alchemy
Ah gotcha. Or a known list yeah
For prime numbers, since they’re quite difficult to calculate and there’s not that many of them, that’s what’s most common.
That’s a legitimate thing to do if you have a slow implementation that’s easy to verify and a fast implementation that isn’t.
The error is ~1/log(x), for anyone interested.
you can increase its accuracy by changing the parameter type to long
LLMs belong to the same category. Seemingly right, but not really right.
l/whoosh
Pssh, mine uses a random number generator for odd numbers to return true 4% of the time to achieve higher accuracy and a bettor LLM metaphor
I’m struggling to follow the code here. I’m guessing it’s C++ (which I’m very unfamiliar with)
bool is_prime(int x) { return false; }Wouldn’t this just always return false regardless of x (which I presume is half the joke)? Why is it that when it’s tested up to 99999, it has a roughly 95% success rate then?
I suppose because about 5% of numbers are actually prime numbers, so false is not the output an algorithm checking for prime numbers should return
Oh I’m with you, the tests are precalculated and expect a true to return on something like 99991, this function as expected returns false, which throws the test into a fail.
Thank you for that explanation
And the natural distribution of primes gets smaller as integer length increases
That’s the joke. Stochastic means probabilistic. And this “algorithm” gives the correct answer for the vast majority of inputs
Because only 5% of those numbers are prime
I have seen that algorithm before. It’s also the implementation of an is_gay(Image i) algorithm with around 90% accuracy.
It has actually 100% accuracy
95% of the time
Can we just call the algorithm sex panther and move on?
I mean, an application could exist where this isn’t even wrong. Maybe as a “subroutine” of another algorithm that only needs a truly composite number most of the time to work.
That this reads as a joke says a lot about what application we’re intuitively expecting.
Edit: Not sure why this is being downvoted.
Edit: Not sure why this is being downvoted.
Perhaps because it would do better, being replaced with
noop.A link time optimiser might actually do so.
That’s kind of what I meant by putting “subroutine” in quotes. You obviously wouldn’t write it like this, you’d just use a random large number with a bit of explanation.
Oh well, live and learn. I’ll try to be clearer next time.
I just took the above comment as continuing the joke, but this explanation actually confuses me more.
Well, I don’t really think you need to be very clear in this case. Jokes are more fun when you “get” them rather than have them explained.I get OP was a joke, but I was trying to make a serious observation.
Say you have some kind of stochastic algorithm that works on the assumption it’s fed a composite number most of the time. Maybe something like Pollard’s Rho algorithm, where whatever number theoretic structure you need accumulates slowly over time as a result. You decide to just pick a large number at random for each iteration.
Implicitly, you’ve solved the problem of finding a composite number by assuming all (large) numbers are composite, like in this post. It is pretty close, like mentioned in this post. If that’s not good enough, you could also use a primality test that fails some small portion of the time, which do exist, and use less power than guaranteed tests.
