finding curve length

[nmukh1]

Hey guys,
I'm trying to optimize a program that measures the length of a curve.
Suppose I define a function f and I have two bounds [a,b] and am trying
to find the arc length. The familiar calculus equation
/
| sqrt(1+f'(x)) dx provides us the arc length.
/

I'm trying to use C to numerically find the arc length.

float metric(float x2, float x1){
return sqrt(pow(f((x2-x1),2))+pow(f(x2)-f(x1),2));}

float lengthofcurve(float a, float b){
float delta=.000001;
float sum=0;
for(a;a<b;a+=delta){
sum+=metric(a,a+delta);
}
return sum;}

Metric computes the length of two points and returnes their distance.
My results so far have been with a high degree of error. Any
suggestions on making the algorithm more efficient?

Thanks

 

[Michael Mair]

Hey guys,
I'm trying to optimize a program that measures the length of a curve.
Suppose I define a function f and I have two bounds [a,b] and am trying
to find the arc length. The familiar calculus equation
/
| sqrt(1+f'(x)) dx provides us the arc length.
/

I'm trying to use C to numerically find the arc length.

float metric(float x2, float x1){
return sqrt(pow(f((x2-x1),2))+pow(f(x2)-f(x1),2));}

float lengthofcurve(float a, float b){
float delta=.000001;
float sum=0;
for(a;a<b;a+=delta){
sum+=metric(a,a+delta);
}
return sum;}

Metric computes the length of two points and returnes their distance.
My results so far have been with a high degree of error. Any
suggestions on making the algorithm more efficient?

For one thing, you do not take parametrization into account,
i.e. whether f "goes throught the curve" at "constant speed"
or not.
In addition, you seem not to know enough about floating point
numbers, otherwise you would know that your summation loop
based on floating point numbers is a bad idea at best and
that "float" is probably not precise enough for your purposes.

Get a good book about numerical mathematics and start from the
beginning and go on until you have covered "quadrature"/numerical
integration.

Then test independently:
- The quality of your approximation of f' to a function f
for a parametrization from 0 to 1 via x, x*x, sqrt(x)
- The quality of lengthofcurve for exact derivative known
with given quadrature formula
Your implementation lacks in both areas.

Note that only the issues about float vs. double and your
for-loop are vaguely C-specific. The rest is off-topic round
here.
You may get better answers in newsgroups about programming
in general and scientific newsgroups dealing with numerical
mathematics.


Cheers
Michael

 

[osmium]

I'm trying to optimize a program that measures the length of a curve.
Suppose I define a function f and I have two bounds [a,b] and am trying
to find the arc length. The familiar calculus equation
/
| sqrt(1+f'(x)) dx provides us the arc length.
/

Why are you telling us this? Is it just interesting background or does it
have something to do with your code, per se?

I'm trying to use C to numerically find the arc length.

float metric(float x2, float x1){
return sqrt(pow(f((x2-x1),2))+pow(f(x2)-f(x1),2));}

I may be totally missing the point. But, ignoring your calculus comment,
ISTM that this should be:

return sqrt( pow( (x2-x1), 2.0.) + pow ( (f(x2) - f(x1) ),
..0) );

But you indicate what you have is working - albeit with error. To me, it
just looks like noise. You mention error, how much? 1%, 10%, 50%?

As has already been pointed out, you should be using double instead of
float. Float is rarely used in C, except for long term (disk) storage - if
at all.

float lengthofcurve(float a, float b){
float delta=.000001;
float sum=0;
for(a;a<b;a+=delta){
sum+=metric(a,a+delta);
}
return sum;}

Metric computes the length of two points and returnes their distance.
My results so far have been with a high degree of error. Any
suggestions on making the algorithm more efficient?

So you want to compute the wrong answer faster? Or what?

 

[nmukh1]

Michael,
Without getting bogged down with mathematical details, this is a simple
elementary calculus application of curve length restricted to cartesian
coordinates. No need to take into account parametrization. My
problems were unfamiliarity with how C allocates memory for different
variable types.

I took your recommendations and did the following:

1. Changed variable type from float to double.
2. Decreased the value for delta, and got more accurate curve lengths
but this resulted in much longer computation time.

My question is whether there is a way to optimize speed and accuracy of
the answer? Or is this question relying too heavily on numerical
analysis and I should stay away from the C forums for this?

 

[Michael Mair]

Please quote enough context -- not everyone may yet have received
my answer or even your original request.
Without context, you take from yourself the chance for another
person answering.

Michael,
Without getting bogged down with mathematical details, this is a simple
elementary calculus application of curve length restricted to cartesian
coordinates. No need to take into account parametrization. My
problems were unfamiliarity with how C allocates memory for different
variable types.

I took your recommendations and did the following:

1. Changed variable type from float to double.
2. Decreased the value for delta, and got more accurate curve lengths
but this resulted in much longer computation time.

Yep. Thus the hint to have a look at quadrature methods: There
are methods with step length adaption which cover regions where
f/f' changes quickly with small steps and other regions with large
steps.

The main thing, though, is going away from a naive floating point
loop iteration.
Rather use
long i;
for (i=0; i<NUM_STEPS; i++) {
h = (double)i/NUM_STEPS;
....
}
for simple iterations or iterate until the forward interval
boundary (i.e. a + h) exceeds your upper integration limit
and do the last part of the summation by hand.
Reason:
for (f=0.0F; f < 1.0F; f += 0.1F) {
....
}
does not necessarily give you ten loop iterations and almost
certainly leave the loop with f != 1.0F because 0.1 cannot
be represented exactly in float (the same applies to double
and long double, of course).

Then think about improving your approximation of f'.

My question is whether there is a way to optimize speed and accuracy of
the answer? Or is this question relying too heavily on numerical
analysis and I should stay away from the C forums for this?

IMO, the latter. If you have finally a C program and have
problems with the _C_ aspects, then you will receive excellent
help here.
However, it makes much more sense to ask where the experts are.
Even though I studied maths, I may have forgotten enough to
lead you into the completely wrong direction.


Cheers
Michael