In competitive programming, Adaptive Simpson’s Method is commonly used to compute Definite Integrals. If you don’t know what is an Integral, please read this article.
Introduction to Simpson’s rule
Now we want to compute \int_L^Rf(x)\text dx.
We use a quadratic function to simulate the given function f(x).
So we have
double simpson(double l,double r){return (r-l)/6*(f(l)+4*f((l+r)/2)+f(r));}
Adaptive Simpson’s Method
Simpson’s rule gives us a good method for Numerical Integration. However, if we want higher precision, we should improve it.
Suppose s(L,R) equals to \int_L^Rf(x)\text dx computed directly using Simpson’s rule.That is,
When we compute calc(L^\prime,R^\prime)=\int_{L^\prime}^{R^\prime}f(x)\text dx for higher precision, suppose M=\frac{L+R}{2}. Recall that \int_a^b=\int_a^c+\int_c^b.
If |s(L^\prime,M)+s(M,R^\prime)-s(L^\prime,R^\prime)|<\epsilon, that means we have enough precision, thus calc(L^\prime,R^\prime) should return s(L^\prime,M)+s(M,R^\prime).
If not, then we should compute calc(L^\prime,M) and calc(M,R^\prime) separately, and add them together.
Here’s the code of Adaptive Simpson’s Method.
const double eps=1e-12; // represents how much precision you need
double f(double x){ /* function for integration */}
double simpson(double l,double r){return (r-l)/6*(f(l)+4*f((l+r)/2)+f(r));}
double calc(double l,double r,double ans)
{
double m=(l+r)/2,x=simpson(l,m),y=simpson(m,r);
if(abs(x+y-ans)<eps)return x+y;
return calc(l,m,x)+calc(m,r,y);
}
int main()
{
double L,R;
scanf("%lf%lf",&L,&R);
printf("%.8f\n",calc(L,R,simpson(L,R)));
}
That’s all. Thanks for reading.
Problems
I’ve collected several problems solvable using this method. You can find them here.