1

Simpson's method for finding a the area under a curve, ie. The value of a definite integral for [a, b] is area = ((b-a)/6)*(f(a) + 4*f(m) + f(b)) where m is the midpoint of the interval.

I've already written a function S() that calculates this for a given interval and curve. I'm trying to write a new function AdaptiveSimpsons() which takes into account that some areas of the curve have more variations and thus require more subdivisions to get within a certain range of accuracy.

Pseudocode for this would be:

  1. Subdivide interval [a, b] into two and check if those two parts are within desired uncertainty (there is a function already written for this)

  2. If yes, add the interval to an array

  3. If no, keep dividing until it satisfies, and add each subdivision to array

  4. Run a loop that takes each interval from array and uses S() function to calculate area using Simpson's method.

I'm unsure of how to get the appropriate intervals without using recursion. I'm new to C so any help is appreciated.

Peter O.
  • 32,158
  • 14
  • 82
  • 96
Chinmayee Gidwani
  • 51
  • 7
  • Can you base the interval on the local gradient of the curve? If the gradient between the current point and the proposed next point is steep, use a smaller step. – Weather Vane Jan 19 '17 at 23:31
  • @WeatherVane I could, but the assignment is specific about getting it within a given degree of uncertainty by subdividing – Chinmayee Gidwani Jan 19 '17 at 23:36
  • You do not need recursion to do that. A simple loop will do it, halving the proposed interval until satisfactory, or a predefined minimum step. Then take the area of that slice and move on. – Weather Vane Jan 19 '17 at 23:41
  • but the number of intervals increases everytime it is divided. for example, it is first divided into two, out of which both sections are unsatisfactory. then both sections are divided by two, where say 3/4 sections are unsatisfactory. it must keep subdividing until all sections are satisfactory. if i use a loop, I can't figure out how to get all sections to be considered every time it gets divided – Chinmayee Gidwani Jan 19 '17 at 23:45
  • Just consider one section, that gets halved, forget what else comes. Start again after the slice you calculate. It's a local matter. If the first half needs subdividing, forget the rest until you have done the current slice? Otherwise, you'll end up with every section of the smallest size. – Weather Vane Jan 19 '17 at 23:48
  • Hm I get what you're saying but how do you come back to the other slices? I can consider one slice until one slice only satisfies the conditions. How would I simultaneously also divide the other slices that did not satisfy the condition? – Chinmayee Gidwani Jan 19 '17 at 23:57
  • You don't, you start again with another slice. – Weather Vane Jan 20 '17 at 00:00
  • The standard technique for converting recursion to iteration uses a queue (or stack) to store information for each incomplete recursive call. Iteration stops when the queue is empty. See, amongst others questions on SO, [Can every recursion be changed to iteration?](https://stackoverflow.com/questions/11708903/can-every-recursion-be-changed-to-iteration) Note that not all recursive functions can be changed to tail recursive functions. – Jonathan Leffler Jan 20 '17 at 00:35

0 Answers0