niklasb's blog

Tasks involving numerical integration
By niklasb, 11 years ago, In English

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);
  if (fabs(l+r-tot) < eps) return tot;
  return integrate(a,m)+integrate(m,b);
}
  • Vote: I like it
  • -1
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
11 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I know two:

→ Reply
»
11 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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);
}
→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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!

    → Reply
»
11 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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. ;)

→ Reply
»
11 years ago, # |
  Vote: I like it +5 Vote: I do not like it

"Latin America 2012 Problem E" can be useful.

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I am so lucky to find this blog while i am solving SGU217. thank you!

→ Reply
»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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!).

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

→ Reply