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.