Per HammerFeb 27
mhoye

I’ve been thinking about this for days. Incredible stochastic algorithm, gets more reliable the larger your input, incredibly fast, trivial to implement and deterministic on its inputs. It really has so much going for it.

(Via @jonathankoren )

Feb 22 at 12:42amWeb
Show threadGreg PfeilFeb 22
@mhoye @jonathankoren And no false positives!
Show threadmhoyeFeb 22
@sellout @jonathankoren right!?
Show threadRyeNCode 🇨🇦Feb 22
@mhoye @sellout @jonathankoren
It's accuracy asymptotically approaches 100%
That's amazing!
Slight cavities about using it for cryptographic purposes or around smallish numbers.
Show threadDan PortsFeb 22
@mhoye @jonathankoren wow, so much more efficient than the state-of-the-art algorithm: asking a LLM whether x is prime
Show threadJohn William David ThomsonFeb 27
@dan @mhoye @jonathankoren more accurate too!
Show threadphilosophizes whilst swimmingFeb 22
@jonathankoren @mhoye they’re all good algorithms, Brent
Show threadjonathankoren™Feb 22
@adardis @mhoye there are no bad algorithms. There are only bad use cases.
Show threadeiriasFeb 22
@jonathankoren @adardis @mhoye this is like that weather aphorism, isn't it
Show threadmarcusFeb 22
@jonathankoren Is there a use case for Bogosort?
Show threadjonathankoren™Feb 22
@mschomm it’s perfectly fine for small arrays
Show threadOxyte 🥴🥴🥴🥴🥴Feb 22
@mschomm @jonathankoren Benchmarking
Show threadgroxxFeb 22
@mhoye @jonathankoren it's branchless too, and easily parallelized onto a GPU to speed it up
Show threadOllie BoermansFeb 22
@mhoye @jonathankoren @daedalus I hope the crypto crew catch wind of this. Has potential to save a lot of electricity
Show threadMark ReidFeb 22
@mhoye @jonathankoren @rmondello Surprising fact: exactly the same algorithm works even better for many other problems: perfect numbers, powers of two, busy beaver, etc.
Show threadTom BortelsFeb 22

@jonathankoren @mhoye

The problem is its inaccuracy for smaller input sets involving low-digit-count numbers.

Trivially fixed by hardcoding the results for 3-digit and lower input. Ship it!

Show threadjonathankoren™Feb 22
@tbortels @mhoye https://di-mgt.com.au/primes10000.txt
Show threadcubeosFeb 22
@mhoye @jonathankoren It also provides the script for a math party trick: "Tell me any 100 digit number and I will tell you if it's prime!'
Show threadgkrnoursFeb 22
@mhoye @jonathankoren are you sure about the more reliable the larger input? Prime number are weird
Show threadThomas EisenbockFeb 22
@mhoye @i0null @jonathankoren How can I unsee this?
Show threadHacker MemesFeb 22
@et @mhoye @jonathankoren
bool mark_as_unread() {
return true;
}
Show threadSven A. SchmidtFeb 22
@mhoye @jonathankoren It might be sentient
Show threadmhoyeFeb 22
@finestructure @jonathankoren oh shit you’re right
Show threadIchinin   ✅🎯🙄Feb 22
@mhoye Algorithms like this are used as a pre-prime testing before you do the actual prime testing that requires CPU heavy computation.
Show threadArcane RoopsFeb 22
@mhoye @jonathankoren Snort! :-)
Show threadMehrad   Feb 22
@mhoye
@jonathankoren
It is one of the best one-class classifier I've ever seen. Extremely efficient and the computational time doesn't grow the larger the input gets.
Show threadIngonymousFeb 22
@mhoye @Nephele @jonathankoren
That's prime crime
Show threadStylusFeb 22
@mhoye @silicatefondue @jonathankoren this class of algorithm is called the stopped clock algorithm. It joins the previously identified Monte Carlo and las Vegas algorithms.
Show threadmjdxpFeb 22
@mhoye @jonathankoren amazing, we've discovered prime numbers past 2
Show threadmhoyeFeb 22
@mjdxp @jonathankoren This changes everything!
Show threadYesBaitFeb 22
@mhoye @jonathankoren can absolutely relate. Constantly trying convince my quantitative colleagues that discrete maths is different from their stochastic and AI based reasoning.
Show threadTygerKrashFeb 22
@mhoye @jonathankoren thats fantastic.
Show threadDaveFeb 22

@mhoye @jonathankoren

Reminds me of another ...

float sin(float x) { return x; }

is remarkably accurate for a large proportion of the possible input values.

Show threadDerPumu (he/him)Feb 22
@TheLancashireman @mhoye @jonathankoren physicists bread and butter. "x is small, so sin(x) is roughly x"
Show threadExeciNFeb 22
@mhoye @jonathankoren
And it’s O(1) too!
Show threadQybatFeb 22
@mhoye @jonathankoren The best part is that the apparent errors are just an artifact of the test methodology. The stricter you make your test, the more accurate the algorithm measures.
Show threadBlackoverflowFeb 23

@mhoye
@jonathankoren

It has 100% Test Coverage, too!

This means, it has no bugs, right?

Show threadTim MakariosFeb 23
@mhoye @jonathankoren
No false positives!
Show threadPeter SommerladFeb 24

@mhoye @jonathankoren

similarly 7 9s chance of undefined behavior in C++ integer multiplication due to overflow. so probable with random Input that optimizing away imul operations would be done by an AI-based optimizer