MONT-E-CARLO.
If you want to calculate the integral of f(x) in a..b:
First generate a bounding box such that f(x) lies within it (you can do this analytically or just guess; as long as you are close it will work).
n times, do:
Generate a random x,y in the bounding box. See if y < f(x) (keep track of the number of times this is the case, call it m).
Now m/n times the area of the bounding box is the area under the curve. (Basically, you figure the ratio of hits to non hits is the same as the ratio of the area under the curve to the area of the box.)
There are similar randomized algorithms lots of places in computer science, and it's often surprising how well they work. Some people use something called "Metropolis Monte Carlo" in order to do fancy rendering of light in 3D images. |