Skip to content

Instantly share code, notes, and snippets.

@vrbadev
Created April 9, 2021 16:40
Show Gist options
  • Save vrbadev/8c31cb24f61f78834914997038ea4b84 to your computer and use it in GitHub Desktop.
Save vrbadev/8c31cb24f61f78834914997038ea4b84 to your computer and use it in GitHub Desktop.
Fast 2D linear regression in pure C without math libraries
#include <stdio.h>
#include <stdint.h>
float pwr2(float x)
{
return x * x;
}
float inv_sqrt(float number)
{
const float x2 = number * 0.5f;
const float threehalfs = 1.5f;
union {
float f;
uint32_t i;
} conv = { .f = number };
conv.i = 0x5f3759df - (conv.i >> 1);
conv.f *= threehalfs - (x2 * conv.f * conv.f);
return conv.f;
}
uint8_t lin_reg(int n, const float x[], const float y[], float* m, float* b, float* r2)
{
float sumx = 0.0f;
float sumx2 = 0.0f;
float sumxy = 0.0f;
float sumy = 0.0f;
float sumy2 = 0.0f;
for (int i=0; i < n; i++){
sumx += x[i];
sumx2 += pwr2(x[i]);
sumxy += x[i] * y[i];
sumy += y[i];
sumy2 += pwr2(y[i]);
}
float denom = (n * sumx2 - pwr2(sumx));
if (denom == 0) {
*m = 0.0f;
*b = 0.0f;
if (r2) {
*r2 = 0.0f;
}
return 1;
}
*m = (n * sumxy - sumx * sumy) / denom;
*b = (sumy * sumx2 - sumx * sumxy) / denom;
if (r2) {
*r2 = pwr2((sumxy - sumx * sumy / n) * inv_sqrt((sumx2 - pwr2(sumx)/n) * (sumy2 - pwr2(sumy)/n)));
}
return 0;
}
int main()
{
unsigned int num;
printf("Enter number of points: ");
while(scanf("%u", &num) != 1) {
printf("\r\nError when reading number of points! Try again: ");
}
printf("Please enter %u points in format 'x,y', one per line.\r\n", num);
float x[num], y[num];
for (uint16_t i = 0; i < num; i++) {
printf("Point #%u: ", i);
while(scanf("%f,%f", &x[i], &y[i]) != 2) {
printf("\r\nError when reading number of points! Try again: ");
}
}
printf("Performing linear regression...\r\n");
float m, b, r2;
if (lin_reg(num, x, y, &m, &b, &r2)) {
printf("Singular matrix, unable to compute!\r\n");
} else {
printf("Fitted line: y = %.2fx + %.2f with score R2 = %.2f\r\n", m, b, r2);
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment