Translate

Thursday, February 05, 2015

Considering a naive coding area

One problem I don't think gets addressed enough is how badly some people are educated, especially when it comes to code. And if it is public on the web then yeah, it can reflect on you, so I thought I would help out with a common area which has turned into a pet peeve of mine, and that is when I see implementations of bad prime counting approaches publicly online.

The reason I search on the subject is I figured out over a decade ago a really simple approach to counting prime numbers that tweaked techniques previous known, resulting in a simple iterative summation, which is so simple I can give it in a single line:

With ints or longs--where pj is the jth prime:

P(x,n) = x - 1 - sum for j=1 to n of {P(x/pj,j-1) - (j-1)}

It counts primes when n equals the count of primes up to sqrt(x), so if n is greater than the count of primes up to and including sqrt(x) then n is reset to that count.

For example P(100,4) = 25. You can just code up from the instructions given and verify easily enough. Notice you'd need 4 primes--2, 3, 5 and 7.

And I've posted that before. Actually I post about it a LOT, but am mentioning it now to highlight just how bad it can really be out there. And how often people learn crappy things in coding.

It is the fastest, short prime counting algorithm available on the planet.

The only other things as short are not as fast. The algorithms that are faster are not as short.

I like to call finds of mine that are better than anything else in the world, my toys. I use them to critique what other people do.

Notice it involves extremely basic math, so claiming you're not good at math is not a valid excuse. If you know how to divide and how to throw away remainders then you can comprehend it. Using ints or longs is so the computer will do that throwing the remainder away for you.

And it can be optimized which bored me decades ago as I realized it then just approached the currently known fast prime counting algorithms. I get bored with known. I prefer the unknown.

So if you dare post ANYTHING about counting primes, and I find it, and it is naive, especially the most horrendous which is to just divide a long list of numbers by every prime, then unfortunately I will think less of you, and wherever you got your education.

And I think that worth mentioning to help people who may not realize that yeah, such things might get noticed. I know I notice them. And it is such a preventable thing. Don't post naive coding practices. Just don't.

Oh yeah, if you want to know how fast your code should be if you dare to post prime counting code, I put up a post with a benchmark. That is with somewhat optimized code.

Sorry, just a little bit irritated. And yes, I dutifully worked to get my algorithm widely known, like with what I'm doing here. Keep talking about it, but these things can take a while. But some people labor under the misconception that they actually are learning good things, when they aren't even learning quasi-decent in an advanced world where a lot more is known than you are necessarily being taught.

So yeah, a LOT of the point of this post is to highlight the algorithm. It IS the best in the world as described but I'm having problems getting it properly acknowledged and that's sad. It's a lot more fun to code than anything else for counting prime numbers, especially at the basic level, while being faster than anything else available for its size.

I'm using this example as it's very demonstrative I think.

Is it really an issue if you have some pathetic prime counting code I come across? I don't know. Probably not. But I am being honest, I do see it at times, and just wonder what people are thinking. Or better yet, wish they were being taught better, since better is available.


James Harris
Post a Comment