### niklasb's blog

By niklasb, 6 years ago, , Good morning ;)

I'm currently improving my geometry code collection and searching for programming tasks involving numerical integration to test my code.

So far, I found the following:

I have to add that most of these can be solved explicitly as well :)

Do you know any similar tasks?

I'm using the following code (which I have not written myself!) which is a simple implementation of the adaptive Simpson's rule and which has served me quite well so far:

double simps(double a, double b) {
return (f(a) + 4*f((a+b)/2) + f(b))*(b-a)/6;
}

double integrate(double a, double b){
double m = (a+b)/2;
double l = simps(a,m), r = simps(m,b), tot=simps(a,b);
return integrate(a,m)+integrate(m,b);
}  Comments (9)
 » I know two:
 » Also try this: http://www.spoj.com/problems/CIRU/This problem may need this trick to reduce the call to f(). inline double simpson(double fl,double fr,double fmid,double l,double r) { return (fl+fr+4.0*fmid)*(r-l)/6.0; } double rsimpson(double slr,double fl,double fr,double fmid,double l,double r) { double mid = (l+r)*0.5; double fml = f((l+mid)*0.5); double fmr = f((mid+r)*0.5); double slm = simpson(fl,fmid,fml,l,mid); double smr = simpson(fmid,fr,fmr,mid,r); if(fabs(slr-slm-smr) < eps) return slm+smr; return rsimpson(slm,fl,fmid,fml,l,mid)+rsimpson(smr,fmid,fr,fmr,mid,r); } double integrate(double l,double r) { double mid = (l+r)*.5; double fl = f(l); double fr = f(r); double fmid = f(mid); return rsimpson(simpson(fl,fr,fmid,l,r),fl,fr,fmid,l,r); } 
•  » » Thanks :) Yeah, the redundant calls to f() waste a lot of run time, but since typical tasks don't require a lot of optimization here, this is okay most of the times :) Nice to see that the optimized version is quite simple as well!
 » http://acm.timus.ru/problem.aspx?space=1&num=1562 But this problem is quite simpler than the ones you've shown and won't require Simpson's formula. ;)
 » "Latin America 2012 Problem E" can be useful.
 » I am so lucky to find this blog while i am solving SGU217. thank you!
 » What's the — estimated — complexity of the adaptive Simpson's rule ?
 » Don't know if you're still looking for problems, but for future reference, CERC '07 Water is a good problem involving numeric integration (of general rational functions, too!).
 » 15 months ago, # | ← Rev. 2 →   Judging by the run times of currently accepted solutions, I don't think Little Mammoth is solved with numerical integration, instead I think it should be solved using Green's Theorem. Am I right?