I’ve been thinking about this for days.

[groxx@hachyderm.io]

@mhoye @jonathankoren it's branchless too, and easily parallelized onto a GPU to speed it up

[ollicle@mastodon.social]

@mhoye @jonathankoren @daedalus I hope the crypto crew catch wind of this. Has potential to save a lot of electricity

[eirias@mefi.social]

@jonathankoren @adardis @mhoye this is like that weather aphorism, isn't it

[mdreid@mastodon.social]

@mhoye @jonathankoren @rmondello Surprising fact: exactly the same algorithm works even better for many other problems: perfect numbers, powers of two, busy beaver, etc.

[tbortels@infosec.exchange]

@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!

[drwho@masto.hackers.town]

@jonathankoren @adardis @mhoye Can I quote you on that?

[mhoye@cosocial.ca]

@drwho @jonathankoren @adardis It's such a good line.

[cubeos@hachyderm.io]

@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!'

[jonathankoren@sfba.social]

@drwho @adardis @mhoye why would I care?

[gkrnours@mastodon.gamedev.place]

@mhoye @jonathankoren are you sure about the more reliable the larger input? Prime number are weird

[et@mastodon.bayern]

@mhoye @i0null @jonathankoren How can I unsee this?

[finestructure@mastodon.social]

@mhoye @jonathankoren It might be sentient

[i0null@infosec.exchange]

@et @mhoye @jonathankoren
bool mark_as_unread() {
return true;
}

[jonathankoren@sfba.social]

@tbortels @mhoye https://di-mgt.com.au/primes10000.txt

[ichinin@infosec.exchange]

@mhoye Algorithms like this are used as a pre-prime testing before you do the actual prime testing that requires CPU heavy computation.

[arcaneoverflow@techhub.social]

@mhoye @jonathankoren Snort!

[mehrad@fosstodon.org]

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

[ingonymous@mastodon.social]

@mhoye @Nephele @jonathankoren
That's prime crime

[stylus@social.afront.org]

@mhoye @silicatefondue @jonathankoren this class of algorithm is called the stopped clock algorithm. It joins the previously identified Monte Carlo and las Vegas algorithms.

[http@infosec.exchange]

@mhoye @jonathankoren If you change that to:
return !(x&1);
You have improved the probability quite a lot and still fast and won't get optimized away.