Euclidean Distance and Cosine Similarity in C

Implementing Euclidean Distance in C

In the previous lesson, we defined Euclidean distance with the following formula for two vectors, $A$ and $B$, of dimension $n$:

To implement this, we need to iterate through the vectors, calculate the squared difference of each pair of components, sum them up, and finally take the square root of the total sum.

The following video segment provides a quick, language-agnostic overview of the coding logic, which directly maps to the formula.

A Key Performance Insight: Squared Euclidean Distance

For many applications, including finding the k-nearest neighbors, we don't need the absolute distance. We only need to rank the distances to find the smallest ones. Since the square root function, $f(x)=\sqrt{x}$, is monotonically increasing, comparing $d(A,B)$ is equivalent to comparing $d(A,B{)}^2$. If $d_1^2>d_2^2$, then we know $d_1>d_2$.

This is a critical, low-level optimization. The sqrt operation is computationally far more expensive than multiplication or addition. By comparing the squared distances, we can avoid the sqrt call for every comparison in our search loop, saving a significant amount of CPU time. We only need to calculate the actual square root for the final top 'k' results if the user needs the true distance value.

The following article from Cloudflare's blog discusses this exact optimization in the context of a high-performance system.

Following this logic, let's write our first function. We'll represent our vectors as pointers to floating-point arrays.

#include <math.h>

// Calculates the squared Euclidean distance between two vectors.
// This is preferred for comparisons as it avoids the expensive sqrtf call.
float euclidean_distance_squared(const float *v1, const float *v2, int dim) {
    float sum = 0.0f;
    for (int i = 0; i < dim; ++i) {
        float diff = v1[i] - v2[i];
        sum += diff * diff;
    }
    return sum;
}

For completeness, here is the function that returns the true Euclidean distance. It simply calls our squared distance function and then performs the final square root.

// Calculates the true Euclidean distance.
// Use this only when the actual distance value is needed, not for ranking.
float euclidean_distance(const float *v1, const float *v2, int dim) {
    float squared_dist = euclidean_distance_squared(v1, v2, dim);
    return sqrtf(squared_dist);
}

Notice the use of sqrtf, which is the version of sqrt from <math.h> that operates on float types.

Implementing Cosine Similarity in C

Next, we'll implement Cosine similarity. As a reminder, this metric measures the cosine of the angle between two vectors, ignoring their magnitudes.

The formula is:

This formula can be broken down into three distinct parts:

1. Dot Product of A and B ($A\cdot B$)
2. L2 Norm (magnitude) of A ($\Vert A\Vert$)
3. L2 Norm (magnitude) of B ($\Vert B\Vert$)

This breakdown lends itself to a clean, modular implementation. We'll write helper functions for the dot product and the L2 norm, then combine them.

1. Dot Product

The dot product is the sum of the element-wise products of the two vectors.

// Calculates the dot product of two vectors.
float dot_product(const float *v1, const float *v2, int dim) {
    float sum = 0.0f;
    for (int i = 0; i < dim; ++i) {
        sum += v1[i] * v2[i];
    }
    return sum;
}

2. L2 Norm

The L2 norm is the square root of the sum of the squares of the vector's components. You might notice this is just the Euclidean distance from the vector to the origin.

// Calculates the L2 norm (magnitude or length) of a vector.
float l2_norm(const float *v, int dim) {
    float sum = 0.0f;
    for (int i = 0; i < dim; ++i) {
        sum += v[i] * v[i];
    }
    return sqrtf(sum);
}

3. Combining for Cosine Similarity

Now, we can assemble these building blocks into our final function. We must also handle a potential division by zero if one of the vectors has a magnitude of zero.

// Calculates the Cosine similarity between two vectors.
// Returns a value between -1 (opposite) and 1 (identical).
float cosine_similarity(const float *v1, const float *v2, int dim) {
    float dp = dot_product(v1, v2, dim);
    float norm1 = l2_norm(v1, dim);
    float norm2 = l2_norm(v2, dim);

    // Handle potential division by zero
    if (norm1 == 0.0f || norm2 == 0.0f) {
        return 0.0f; // Or handle as an error, depending on requirements
    }

    return dp / (norm1 * norm2);
}

This short video walks through a manual calculation, reinforcing how the dot product (numerator) and norms (denominator) come together.

Finally, as we discussed in the last lesson, we often convert similarity to distance. The Cosine Distance is simply $1-\text{similarity}$.

// Calculates Cosine distance from Cosine similarity.
// Maps the [-1, 1] similarity range to a [0, 2] distance range.
float cosine_distance(const float *v1, const float *v2, int dim) {
    return 1.0f - cosine_similarity(v1, v2, dim);
}

A Complete Example

To solidify your understanding, here is a complete main.c file. You can compile and run this yourself to see the functions in action.

// main.c



#include <stdio.h>
#include <math.h>

// --- Function implementations from above ---

float dot_product(const float *v1, const float *v2, int dim) {
    float sum = 0.0f;
    for (int i = 0; i < dim; ++i) {
        sum += v1[i] * v2[i];
    }
    return sum;
}

float l2_norm(const float *v, int dim) {
    float sum = 0.0f;
    for (int i = 0; i < dim; ++i) {
        sum += v[i] * v[i];
    }
    return sqrtf(sum);
}

float cosine_similarity(const float *v1, const float *v2, int dim) {
    float dp = dot_product(v1, v2, dim);
    float norm1 = l2_norm(v1, dim);
    float norm2 = l2_norm(v2, dim);
    if (norm1 == 0.0f || norm2 == 0.0f) {
        return 0.0f;
    }
    return dp / (norm1 * norm2);
}

float euclidean_distance_squared(const float *v1, const float *v2, int dim) {
    float sum = 0.0f;
    for (int i = 0; i < dim; ++i) {
        float diff = v1[i] - v2[i];
        sum += diff * diff;
    }
    return sum;
}

float euclidean_distance(const float *v1, const float *v2, int dim) {
    return sqrtf(euclidean_distance_squared(v1, v2, dim));
}

// --- Main function for testing ---

int main() {
    const int DIM = 4;
    float vec1[] = {1.0f, 2.0f, 3.0f, 4.0f};
    float vec2[] = {5.0f, 6.0f, 7.0f, 8.0f};
    float vec3[] = {2.0f, 4.0f, 6.0f, 8.0f}; // Proportional to vec1

    printf("Vector 1: [1, 2, 3, 4]\n");
    printf("Vector 2: [5, 6, 7, 8]\n");
    printf("Vector 3: [2, 4, 6, 8]\n\n");

    // Test Euclidean distance
    float ed_12 = euclidean_distance(vec1, vec2, DIM);
    float ed_sq_12 = euclidean_distance_squared(vec1, vec2, DIM);
    printf("Euclidean Distance (v1, v2): %f\n", ed_12);
    printf("Squared Euclidean Distance (v1, v2): %f (should be %f^2 = %f)\n\n", ed_sq_12, ed_12, ed_12*ed_12);

    // Test Cosine similarity
    float cs_12 = cosine_similarity(vec1, vec2, DIM);
    float cs_13 = cosine_similarity(vec1, vec3, DIM);
    printf("Cosine Similarity (v1, v2): %f\n", cs_12);
    printf("Cosine Similarity (v1, v3): %f (should be 1.0)\n\n", cs_13);

    return 0;
}

To compile and run this code, save it as main.c and use gcc:
gcc main.c -o distance_test -lm
./distance_test

The -lm flag is important; it links the math library required for sqrtf.

Conclusion

In this lesson, you have successfully translated abstract mathematical formulas into functional C code. You now have baseline implementations for the core arithmetic of our vector search engine.

Key Takeaways:

• You have implemented naive C functions for Euclidean distance and Cosine similarity.
• You understand the practical performance benefit of using Squared Euclidean distance for comparisons to avoid expensive sqrtf calls.
• You have structured the Cosine similarity calculation logically by creating helper functions for dot product and L2 norm, which will be invaluable for our later optimization efforts.
• These functions represent our performance baseline, the mark that we will strive to beat.

We are now ready to enter the world of high-performance computing. In the next lesson, we will introduce the concepts of instruction-level parallelism and SIMD (Single Instruction, Multiple Data), the architectural features of modern CPUs that will allow us to smash our current performance baseline.