849

o(1) statistical prime approximation (thelemmy.club)

submitted 3 days ago* (last edited 3 days ago) by not_IO@lemmy.blahaj.zone to c/programmer_humor@programming.dev

61 comments fedilink hide all child comments

https://cosocial.ca/@mhoye/116111505546606451

top 50 comments

sorted by: hot top new old

[-] Flipper@feddit.org 118 points 3 days ago* (last edited 3 days ago)

Has the same vibes as anthropic creating a C compiler which passes 99% of compiler tests.

That last percent is really important. At least that last percent are some really specific edge cases right?

Description:
When compiling the following code with CCC using -std=c23:
bool is_even(int number) {
   return number % 2 == 0;
}
the compiler fails to compile due to bool, true, and false being unrecognized. The same code compiles correctly with GCC and Clang in C23 mode.

Source

Well fuck.

[-] sus@programming.dev 3 points 2 days ago* (last edited 2 days ago)

The incredible thing is this is actually the result of an explicit design decision.

The compiler accepts most GCC flags. Unrecognized flags (e.g., architecture- specific -m flags, unknown -f flags) are silently ignored so ccc can serve as a drop-in GCC replacement in build systems.

They're so committed to vibing that they'd prefer if the compiler just does random shit to make it easier to shove it haphazardly into a build pipeline.

[-] PlexSheep@infosec.pub 27 points 3 days ago

If this wasn't 100% vibe coded, it would be pretty cool.

A c compiler written in rust, with a lot of basics supported, an automated test suite that compiles well known c projects. Sounds like a fun project or academic work.

[-] into_highest_invite@lemmygrad.ml 7 points 3 days ago

any llm must have several C compilers in its training data, so it would be a reasonably competent almost-clone of gcc/clang/msvc anyway, right?

is what i would have said if you didn't put that last part

[-] Cethin@lemmy.zip 2 points 2 days ago* (last edited 2 days ago)

You're still correct. The thing about LLMs is that they're statistical models that output one of the most likely responses, from the list of most likely responses. It still has some randomness though. You can tune this, but no randomness is shit, and too much randomness sometimes generates stupid garbage. With a large enough output, you're statistically likely, with any randomness, to generate some garbage. A compiler is sufficiently large and complex that it's going to end up creating garbage somewhere, even if it's trained on these compilers specifically.

[-] into_highest_invite@lemmygrad.ml 2 points 2 days ago

that's a great point but wouldn't the output for a solved problem like "make a working C compiler in rust" work better if the temperature/randomness were zero? or am i fundamentally misunderstanding?

[-] Cethin@lemmy.zip 2 points 2 days ago

Probably. At that point you might as well just copy/paste the existing compiler though. The temperature is basically the thing that makes it seem intelligent, because it gives different responses each time, so it seems like it's thinking. But yeah, having it just always give the most likely response would probably be better, but also probably wouldn't play well with copyright laws when you have the exact same code as an existing compiler.

[-] racketlauncher831@lemmy.ml 2 points 2 days ago

This is so fucked up. The AI company has the perfect answer and yet it rolls the die to recreate the same thing by chance. What are they expecting, really?

load more comments (1 replies)

[-] apex32@lemmy.world 65 points 3 days ago

Reminds me of this xkcd:

https://xkcd.com/221/

[-] brian@programming.dev 3 points 1 day ago

also sort of https://xkcd.com/2934/

[-] savedbythezsh@sh.itjust.works 64 points 3 days ago

More like: https://xkcd.com/2236/

[-] ulterno@programming.dev 13 points 3 days ago

info

View the source to see how I embedded the picture without copying it. The hover text had to be copied though.

[-] ulterno@programming.dev 19 points 3 days ago

info

View the source to see how I embedded the picture without copying it. The hover text had to be copied though.

[-] SexualPolytope@lemmy.sdf.org 77 points 3 days ago

The error is ~1/log(x), for anyone interested.

[-] BradleyUffner@lemmy.world 35 points 3 days ago* (last edited 3 days ago)

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.

[-] frank@sopuli.xyz 25 points 3 days ago

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

[-] BradleyUffner@lemmy.world 36 points 3 days ago

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.

[-] GalacticSushi@lemmy.blahaj.zone 42 points 3 days ago

Plot twist: the test just checks to see if the input exists in a hardcoded list of all prime numbers under 100000.

[-] AI_toothbrush@lemmy.zip 20 points 3 days ago

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.

[-] ozymandias@sh.itjust.works 4 points 3 days ago

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

[-] AI_toothbrush@lemmy.zip 3 points 3 days ago

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.

[-] GalacticSushi@lemmy.blahaj.zone 10 points 3 days ago

load more comments (3 replies)

load more comments (1 replies)

load more comments (2 replies)

[-] anton@lemmy.blahaj.zone 9 points 3 days ago

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.

[-] fckreddit@lemmy.ml 41 points 3 days ago* (last edited 3 days ago)

LLMs belong to the same category. Seemingly right, but not really right.

[-] Viceversa@lemmy.world 6 points 3 days ago* (last edited 3 days ago)

l/whoosh

[-] Semi_Hemi_Demigod@lemmy.world 14 points 3 days ago* (last edited 3 days ago)

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.

[-] LodeMike@lemmy.today 4 points 2 days ago

That would make it less accurate. It's much more likely to return true on not a prime than a prime

[-] themusicman@lemmy.world 2 points 2 days ago

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.

[-] LodeMike@lemmy.today 1 points 2 days ago

More random means more towards 50% correctness.

[-] ptu@sopuli.xyz 3 points 2 days ago

And 2,3,5,7 are primes of the first numbers, making always false 60% correct and random chance 50%

[-] Semi_Hemi_Demigod@lemmy.world 2 points 2 days ago

Code proof or it didn't happen.

Extra credit for doing it in Ruby

[-] Jayjader@jlai.lu 4 points 3 days ago

Now you're thinking with ~~portals~~ primes!

load more comments (1 replies)

[-] renzhexiangjiao@piefed.blahaj.zone 24 points 3 days ago* (last edited 3 days ago)

you can increase its accuracy by changing the parameter type to long

[-] Prime@lemmy.sdf.org 7 points 2 days ago

100% of the time, baby =)

[-] lemmydividebyzero@reddthat.com 17 points 3 days ago

I have seen that algorithm before. It's also the implementation of an is_gay(Image i) algorithm with around 90% accuracy.

[-] JustARegularNerd@lemmy.dbzer0.com 15 points 3 days ago

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?

[-] kraftpudding@lemmy.world 35 points 3 days ago

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

[-] JustARegularNerd@lemmy.dbzer0.com 11 points 3 days ago

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

[-] Agent641@lemmy.world 3 points 3 days ago

And the natural distribution of primes gets smaller as integer length increases

[-] flamingo_pinyata@sopuli.xyz 31 points 3 days ago

That's the joke. Stochastic means probabilistic. And this "algorithm" gives the correct answer for the vast majority of inputs

[-] Hexarei@beehaw.org 5 points 3 days ago

Because only 5% of those numbers are prime

[-] zbyte64@awful.systems 6 points 3 days ago

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

[-] red_tomato@lemmy.world 10 points 3 days ago

It has actually 100% accuracy

[-] JustJack23@slrpnk.net 12 points 3 days ago

95% of the time

[-] clav64@lemmy.world 5 points 3 days ago

Can we just call the algorithm sex panther and move on?

[-] Kekzkrieger@feddit.org 9 points 3 days ago

If you think this is bad and not nearly enough accuracy to be called correct, AI is much worse than this.

It's not just wrong a lot of times or hallucinates but you can't pinpoint why or how it produces the result and if you keep putting the same data in, the output may still vary.

load more comments