Cheat Engine

[Polynomial]

The following are a few optimisation challenges to test your skill at analysing algorithms and optimising their performance. There are a few rules, so I'll start out with them:

Rules
1) All entries must be submitted as both a compiled Windows executable and full source code.
2) You must write your program in VS2008-compatible C++.
3) Plagarism will not be tollerated. I am aware of many solutions to these problems and have given each of them a thorough search. Each entry will be checked thoroughly. However this is mainly a learning competition, so you may base your optimisations off of other people's ideas. Work together to produce the best code.
4) Don't start arguments over mistakes, your opinion on the quality of someone's code, or who invented certain ideas. It's all about learning. Test out things that seem to be unlikely to work anyway, just to see how it fares. I've seen some brilliant ideas miraculously fail for no apparant reason, and things that shouldn't work just happen to work. There's no reason to denounce an idea at face value.
5) No inline ASM.

Right, now onto the challenges!

Challenge 1 - Primality test
Produce a function that given a number, returns a boolean representing the primality of that number - i.e. whether or not it is prime.

Here is a very unoptimal sample:

[Flyte]

Why is this limited to C++?

[Polynomial]

I chose a language that most people on here know and that I have a very simple one-button-to-compile IDE for to save me messing about with other people's code when doing benchmarks. If I open it up to ASM, C, C#, VB.NET, Java and every other language out there it becomes less about the process of optimisation and more about the strengths and weaknesses of the chosen language, and makes proper benchmarking difficult.

Did you have a "better" language in mind?

[Flyte]

[Polynomial]

I'm aware that the first two are open topics (semiprime factorisation especially), but the idea of this is to see what only your collective minds can conjure up. Since I don't have an F# compiler to hand and I would assume most people in here don't either, I'm gonna stick with C++ on this.

If you're not going to directly enter, might you provide some sample pseudocode and ideas? Partial participation is better than nothing.

[Deltron Z]

Nice, I'm glad someone else offering such challanges.

Challange 1:
First of all, let's look at the definition for prime numbers:

[Polynomial]

Deltron, your use of the 6k+/-1 rule is somewhat incorrect. All primes are in that form, but that does not mean that you can skip checking if they are divisible. For example, 961 is not prime but your algorithm misses it completely and states that it is prime. It is a semiprime of 31 and 31.

[Deltron Z]

You're wrong!
Try executing before assuming wrong assumptions, or at least read the code or make sure you understand the algorithm.

Look, the idea here is not to check if n is in the form of 6n + 1 or 6n - 1, you've got that right. I used the same concept, except that I check if the number n is divisble by 6i + 1 or 6i - 1, because any other number is divisble by 3, and if you look at the code you will notice there's a condition, n % 3 == 0, outside the loop. this concept is somehow derived by the fact that a prime number is in the form of 6n + 1 or 6n - 1.

My code runs fine, returns 0 (false) for 961.

P.S. working on the 3rd challange... what about if I increase my stack's size to, let's say, a mega byte? or 20? that's enough for sure...
What should be the search pattern? wild-cards allowed? search in extentions too? if not, is the partial name means the first few characters or some unknown part of the file's name? either way, it doesn't matter, strstr or strncmp or whatever... still a very simple algorithm, but is increasing my stack size allowed in my solution?

[Polynomial]

My apologies, it's late and I misread your code and missed the n%(i+2) bit. My tiredness is getting the better of me.

And as regards the stack, you should never use recursion. Ever. It's horrible. I've also heard it's rather inefficient. I'm gonna say no recursion. My suggestion would be a loop with a state.

The code should match the partial file name anywhere in the whole name. If I specify "png", that should match "file.png", "pngfile.png" and "this_is_a_not_a_png_file.exe".

[hcavolsdsadgadsg]

Careful with forceinline. It's usually a good idea to let the compiler decide, forcing it to inline might actually hurt performance in the end.

what do you mean by:

[Deltron Z]

[Slugsnack]

We're allowed to code the whole thing in inline assembly ? Lol

[hcavolsdsadgadsg]

sqrtf() is the crt function, returns a float square root.
sqrt() returns double.
fsqrt is the actual instruction.

in C++, sqrt() is overloaded so it works either way.

you can also try the SSE sqrt to do 4 sqrt's at once.
take a look at sqrtps

[Deltron Z]

Should I return the first file I encounter or all of them?
Here's what I've done so far:

[Polynomial]