How to make large calculations program faster

I'm implemen开发者_Python百科ting a compression algorithm. Thing is, it is taking a second for a 20 Kib files, so that's not acceptable. I think it's slow because of the calculations.

I need suggestions on how to make it faster. I have some tips already, like shifting bits instead of multiplying, but I really want to be sure of which changes actually help because of the complexity of the program. I also accept suggestions concerning compiler options, I've heard there is a way to make the program do faster mathematical calculations.

Common operations are:

• pow(...) function of math library
• large number % 2
• large number multiplying

Edit: the program has no floating point numbers

The question of how to make things faster should not be asked here to other people, but rather in your environment to a profiler. Use the profiler to determine where most of the time is spent, and that will hint you into which operations need to be improved, then if you don't know how to do it, ask about specific operations. It is almost impossible to say what you need to change without knowing what your original code is, and the question does not provide enough information: pow(...) function: what are the arguments to the function, is the exponent fixed? how much precision do you need? can you change the function for something that will yield a similar result? large number: how large is large in large number? what is number in this context? integers? floating point?

Your question is very broad, without enough informaiton to give you concrete advise, we have to do with a general roadmap.

What platform, what compiler? What is "large number"? What have you done already, what do you know about optimization?

• Test a release build with optimization (/Ox /LTCG in Visual C++, -O3 IIRC for gcc)
• Measure where time is spent - disk access, or your actual compression routine?
• Is there a better algorithm, and code flow? The fastest operation is the one not executed.
• for 20K files, memory working set should not be an issue (unless your copmpression requries large data structures), so so code optimization are the next step indeed
• a modern compiler implements a lot of optimizations already, e.g replacing a division by a power-of-two constant with a bit shift.
• pow is very slow for native integers
• if your code is well written, you may try to post it, maybe someone's up to the challenge.

Hints :-
1) modulo 2 works only on the last bit.
2) power functions can be implemented in logn time, where n is the power. (Math library should be fast enough though). Also for fast power you may check this out

If nothing works, just check if there exists some fast algorithm.