niklasb's blog

By niklasb, 7 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);
}


• -1

 » 7 years ago, # |   +5 I know two:
 » 7 years ago, # |   +5 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); } 
•  » » 7 years ago, # ^ |   0 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!
 » 7 years ago, # |   +5 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. ;)
 » 7 years ago, # |   +5 "Latin America 2012 Problem E" can be useful.
 » 7 years ago, # |   0 I am so lucky to find this blog while i am solving SGU217. thank you!
 » 3 years ago, # |   0 What's the — estimated — complexity of the adaptive Simpson's rule ?
 » 3 years ago, # |   +8 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!).
 » 2 years ago, # | ← Rev. 2 →   0 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?