I’ve been thinking about this for days.

[mhoye@cosocial.ca]

@sellout @jonathankoren right!?

[dan@discuss.systems]

@mhoye @jonathankoren wow, so much more efficient than the state-of-the-art algorithm: asking a LLM whether x is prime

[ryencode@mstdn.ca]

@mhoye @sellout @jonathankoren
It's accuracy asymptotically approaches 100%
That's amazing!
Slight cavities about using it for cryptographic purposes or around smallish numbers.

[adardis@mstdn.social]

@jonathankoren @mhoye they’re all good algorithms, Brent

[jonathankoren@sfba.social]

@adardis @mhoye there are no bad algorithms. There are only bad use cases.

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