# Parametrization of a curve

For a set of 2D or 3D points $\{\mathbf P_0, \mathbf P_1,\cdots,\mathbf P_n\}$, their parameters $\mathbf T = \{t_0,t_1,\cdots,t_n \}$ could be computed as follow:

\begin{align} t_0&=0\\ t_i&=\frac{\sum_{j=1}^{i}||\mathbf P_j- \mathbf P_{j-1}||}{\sum_{j=1}^{n}||\mathbf P_j-\mathbf P_{j-1}||} \qquad i=1,2,\cdots,n \end{align}

Here is my C implementation:

/********************************************************************
v1 = {v1(0),v1(1),...,v1(c-1)}
v2 = {v2(0),v2(1),...,v2(c-1)}
compute the 2-norm of the difference of two vector v1 and v2
*********************************************************************/
double vector_norm(double *v1, double *v2, int c) {
int i;
double res = 0.0;
for (i = 0; i < c; i++) {
res += pow(v1[i] - v2[i], 2);
}
return sqrt(res);
}

/********************************************************
In general, P is a matrix of dimensions {n + 1, c}
here, it was saved as a vector
********************************************************/
void calc_paras(double *P, int n, int c, double *paras) {
int i;
double len = 0.0;
double chord;
//compute the length and total length
paras[0] = 0.0;
for (i = 0; i < n; i++) {
chord = vector_norm(P + (i + 1) * c, P + i * c, c);
len += chord;
paras[i+1] = len;
}
//normalize the paras to [0,1]
for (i = 0; i <= n; i++) {
paras[i] /= len;
}
}


Is a more efficient C implemetation of calc_paras() possible?

Is a more efficient C implementation of calc_paras() possible?

Some small ideas:

1. Use const. A compiler may employ certain optimizations knowing the pointers are to const data.

// double vector_norm(double *v1, double *v2, int c) {
double vector_norm(const double *v1, const double *v2, int c) {

2. If the pointers never overlap, let the compiler know that and allow it additional optimizations using restrict.

// double vector_norm(double *v1, double *v2, int c) {
double vector_norm(const double * restrict v1, const double * restrict v2, int c) {

3. pow(x,2) is questionable. Profile against res += (v1[i] - v2[i])*(v1[i] - v2[i]);

4. Unclear why code is using int vs. size_t to denote the size of a vector. size_t is more C-like.

5. Minor. Might as well avoid the +1

paras[0] = 0.0;
for (i = 1; i <= n; i++) {
chord = vector_norm(P + i*c, P + (i-1)* c, c);
len += chord;
paras[i] = len;
}

6. If vector_norm() is only meant as a helper function for calc_paras(), make vector_norm() static to un-clutter the name space.

• Thanks a lot:) For a C newcomer, I would like to know why pow(x, 2) is questionable. Because pow() is a built-in of math.h library.
– xyz
Aug 31, 2016 at 3:25
• pow() is one of the most complex math functions. Rarely is pow(x,2) more efficient/more precise than simply x*x. I have doubts as to its relative value and speed. Like much minor optimizations, profile it on your target platforms. When in doubt, code to what provides the most clarity to a reviewer. Aug 31, 2016 at 3:28
• In addtion, I discovered that the compiler gives the error when using keywords restrict. Here is snapshots
– xyz
Aug 31, 2016 at 3:36
• @Shutao Tang Use an up-to-date C11 compiler if you are interested in modern optimizations, else your code lives in the past. If obiged to use an old complier why look for a "more efficient C implementation"? Aug 31, 2016 at 3:38
• As a side note for 5. Both temporaries are unecessary. If you zero-initialize paras[0], then the body of the for loop can be written as paras[i] = paras[i-1] +vector_norm(P + i * c, P + (i-1) * c, c); However, i assume the compiler would be able to optimize that away. Also the loop should stop at <n at leaast from the vector definition in the first code snipplet Aug 31, 2016 at 4:55

That is basically the same technique that I would use.

My only suggestion is to consistently use

for (i = 1; i <= n; i++)


for both loops, to match the stated definition.

• Thanks for your suggestion, I know for (int i = 1; i <= n; i++) is C99 style, but when I compile it via the CreateLibrary[]of Wolfram Mathematica, I discovered that it didn't support that style.
– xyz
Aug 30, 2016 at 14:50
• It's really sad that C99 still isn't supported in 2016! Aug 30, 2016 at 14:52
• Maybe I don't know what option I should add in CreateLibrary[] to let the code be compiled with C99 style. :)
– xyz
Aug 30, 2016 at 14:56