#include <cmath>
#include <cassert>
#include <cfloat>
// Compute a numerical approximation to an integral via adaptive Simpson's Rule
// This routine ignores underflow.
const int nest=DBL_MANT_DIG;
typedef struct {
bool left; // left interval?
double psum, f1t, f2t, f3t, dat, estr;
} TABLE;
bool // Returns true iff successful.
simpson(double& integral, // Approximate value of the integral.
double (*f)(double), // Pointer to function to be integrated.
double a, double b, // Lower, upper limits of integration.
double acc, // Desired relative accuracy of integral.
// Try to make |error| <= acc*abs(integral).
double dxmax) // Maximum limit on the width of a subinterval
// For periodic functions, dxmax should be
// set to the period or smaller to prevent
// premature convergence of Simpson's rule.
{
double diff,area,estl,estr,alpha,da,dx,wt,est,fv[5];
TABLE table[nest],*p,*pstop;
static const double sixth=1.0/6.0;
bool success=true;
p=table;
pstop=table+nest-1;
p->left=true;
p->psum=0.0;
alpha=a;
da=b-a;
fv[0]=(*f)(alpha);
fv[2]=(*f)(alpha+0.5*da);
fv[4]=(*f)(alpha+da);
wt=sixth*da;
est=wt*(fv[0]+4.0*fv[2]+fv[4]);
area=est;
// Have estimate est of integral on (alpha, alpha+da).
// Bisect and compute estimates on left and right half intervals.
// integral is the best value for the integral.
for(;;) {
dx=0.5*da;
double arg=alpha+0.5*dx;
fv[1]=(*f)(arg);
fv[3]=(*f)(arg+dx);
wt=sixth*dx;
estl=wt*(fv[0]+4.0*fv[1]+fv[2]);
estr=wt*(fv[2]+4.0*fv[3]+fv[4]);
integral=estl+estr;
diff=est-integral;
area -= diff;
if(p >= pstop) success=false;
if(!success || (fabs(diff) <= acc*fabs(area) && da <= dxmax)) {
// Accept approximate integral.
// If it was a right interval, add results to finish at this level.
// If it was a left interval, process right interval.
for(;;) {
if(p->left == false) { // process right-half interval
alpha += da;
p->left=true;
p->psum=integral;
fv[0]=p->f1t;
fv[2]=p->f2t;
fv[4]=p->f3t;
da=p->dat;
est=p->estr;
break;
}
integral += p->psum;
if(--p <= table) return success;
}
} else {
// Raise level and store information for processing right-half interval.
++p;
da=dx;
est=estl;
p->left=false;
p->f1t=fv[2];
p->f2t=fv[3];
p->f3t=fv[4];
p->dat=dx;
p->estr=estr;
fv[4]=fv[2];
fv[2]=fv[1];
}
}
}
// Use adaptive Simpson integration to determine the upper limit of
// integration required to make the definite integral of a continuous
// non-negative function close to a user specified sum.
// This routine ignores underflow.
bool // Returns true iff successful.
unsimpson(double integral, // Given value for the integral.
double (*f)(double), // Pointer to function to be integrated.
double a, double& b, // Lower, upper limits of integration (a <= b).
// The value of b provided on entry is used
// as an initial guess; somewhat faster if the
// given value is an underestimation.
double acc, // Desired relative accuracy of b.
// Try to make |integral-area| <= acc*integral.
double& area, // Computed integral of f(x) on [a,b].
double dxmax, // Maximum limit on the width of a subinterval
// For periodic functions, dxmax should be
// set to the period or smaller to prevent
// premature convergence of Simpson's rule.
double dxmin=0) // Lower limit on sampling width.
{
double diff,estl,estr,alpha,da,dx,wt,est,fv[5];
double sum,parea,pdiff,b2;
TABLE table[nest],*p,*pstop;
static const double sixth=1.0/6.0;
p=table;
pstop=table+nest-1;
p->psum=0.0;
alpha=a;
parea=0.0;
pdiff=0.0;
for(;;) {
p->left=true;
da=b-alpha;
fv[0]=(*f)(alpha);
fv[2]=(*f)(alpha+0.5*da);
fv[4]=(*f)(alpha+da);
wt=sixth*da;
est=wt*(fv[0]+4.0*fv[2]+fv[4]);
area=est;
// Have estimate est of integral on (alpha, alpha+da).
// Bisect and compute estimates on left and right half intervals.
// Sum is better value for integral.
bool cont=true;
while(cont) {
dx=0.5*da;
double arg=alpha+0.5*dx;
fv[1]=(*f)(arg);
fv[3]=(*f)(arg+dx);
wt=sixth*dx;
estl=wt*(fv[0]+4.0*fv[1]+fv[2]);
estr=wt*(fv[2]+4.0*fv[3]+fv[4]);
sum=estl+estr;
diff=est-sum;
assert(sum >= 0.0);
area=parea+sum;
b2=alpha+da;
if(fabs(fabs(integral-area)-fabs(pdiff))+fabs(diff) <= fv[4]*acc*(b2-a)){
b=b2;
return true;
}
if(fabs(integral-area) > fabs(pdiff+diff)) {
if(integral <= area) {
p=table;
p->left=true;
p->psum=parea;
} else {
if((fabs(diff) <= fv[4]*acc*da || dx <= dxmin) && da <= dxmax) {
// Accept approximate integral sum.
// If it was a right interval, add results to finish at this level.
// If it was a left interval, process right interval.
pdiff += diff;
for(;;) {
if(p->left == false) { // process right-half interval
parea += sum;
alpha += da;
p->left=true;
p->psum=sum;
fv[0]=p->f1t;
fv[2]=p->f2t;
fv[4]=p->f3t;
da=p->dat;
est=p->estr;
break;
}
sum += p->psum;
parea -= p->psum;
if(--p <= table) {
p=table;
p->psum=parea=sum;
alpha += da;
b += b-a;
cont=false;
break;
}
}
continue;
}
}
}
if(p >= pstop) return false;
// Raise level and store information for processing right-half interval.
++p;
da=dx;
est=estl;
p->psum=0.0;
p->left=false;
p->f1t=fv[2];
p->f2t=fv[3];
p->f3t=fv[4];
p->dat=dx;
p->estr=estr;
fv[4]=fv[2];
fv[2]=fv[1];
}
}
}