How to verify method used to solve integral was actually the fastest?

Question

Is there any way to verify if the method I chose to integrate (by hand) was indeed fastest, or if there exists some better technique? Can a computer tell me or show me what the fastest method was, i.e. Weierstrass substitution, integration by parts, etc.

Update: I changed the question slightly because it seemed I may have asked the wrong question. I don't mean computationally, I mean solving the integral by hand; hence the contest-math tag. Sorry about the mix up!

Answer 1

You could always use that software but I do not know of an algorithm producing the fastest way of solving integrals. Apart from base integrals from which you can give the result on the top of your hand, i think it is mostly experience and preferences which guide you to your fastest way(which does not have to be the fastest way for me).

Answer 2

The efficiency of the algorithm is expressed by $O(...)$ expression, for example $O(n^2)$, $O(\log n)$, and so on. Therefore, I think you'll have to express the efficiency of your algorithm using the O (...) expression and compare this with others.
For a more detailed comparison probably will not be available.

Answer 3

Stefan's proposal is the closest you can get for an analytic result. However, the big-O notation is commonly used only to describe the worst-case time complexity of an algorithm. In practice, something like an $\mathcal{O}(n)$ algorithm (interpolation search) can outperform an $\mathcal{O}(\log n)$ algorithm (binary search).

Hence, what you should do is to think of common use cases for your algorithm, with known analytic or numerical results. Then benchmark your algorithm with a CPU program counter (see: time measurement and optimization for Mathematica or profiling tools for Maple). You should have a large number of test cases, preferably generated by machine through varying a few decision variables (e.g. number of exponentiation operations). You would also iterate the same calculation and take the average, to reduce the sampling error. This is what every developer of a numerical library would do.

As you can already guess, there is no sure-fire way of doing this:

1. There is always a trade-off between stability (crudely speaking, precision) and speed. You cannot strictly say that one algorithm is faster - because this law already guarantees that you can always sacrifice precision for speed. You can only say that one algorithm is faster than another for your desired precision. For instance, I could write an algorithm that calculates the square root of a positive real really fast: I just assign the output as 1 for every positive real input. The errors grow with size of the input, but this is technically the fastest algorithm you can get - it's $\mathcal{O}(1)$.
2. Since we are talking about software implementations, there are various software and hardware reasons why one algorithm is faster than another, so you can never pin it purely to a mathematical problem of which algorithm is faster. Other issues come into play - you could trade off memory space for speed, you could also exploit low-level CPU architecture in a variety of ways that advantage one architecture over another. There is rarely a software implementation that is faster for all use cases. Take a look at Eigen vs MKL vs ACML vs GOTO vs ATLAS for instance.

Not all is lost however... there are obvious cases such as the classic linear regression problem whereby you'd always rather compute the coefficients by solving the system of linear equations rather than inverting the matrix directly.

Answer 4

I noticed that you updated your question. No, there is no preferred method to solve an integral analytically, provided an elementary solution exists. What you're most comfortable with is the fastest.

I could, however, advise you on certain tricks that are useful. Since lookup is always theoretically fastest, i.e. $\mathcal{O}(1)$, you should:

1. Memorize as many identities in Gradshteyn et al as possible.
2. Try to reduce the problem to a known one, e.g. using differentiation under the integral sign, complexifying the integral, series expansion etc.
3. Practice. I don't know of a good problem book purely on integration practice, but you could look at some problem sets in quantum mechanics; since the probability of finding a particle in space is $\int_{V_0}\left|\psi\left({x,y,z}\right)\right|^{2}\ dV$, there are plenty of examples that test your ability. This is a great way to force yourself to memorize some identities since the problems are often framed such that you have an integral that is difficult to solve by hand unless you exploit an identity. e.g. Find the normalization constant $A\in\mathbb{R}$ given the wavefunction $\psi(x)=A\sin^{7}\left(\dfrac{\pi x}{a}\right)$ in the real interval $[0,a]$ without 'actually' integrating. i.e. Solve $A^{2}\int_{0}^{a}\sin^{14}\left(\dfrac{\pi x}{a}\right)=1$. (Hint: Exploit symmetry about $\pi/2$ and use Euler's function $\Gamma$.)