niklasb's blog

By niklasb, 6 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

»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it
»
6 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);
}
  • »
    »
    6 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!

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

»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it
»
6 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!

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the — estimated — complexity of the adaptive Simpson's rule ?

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

»
15 months 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?