Distance between two points without using the square root

6
votes

Is it possible to calculate the distance between two points without having to use the math.h library? I know that, using the math.h library, it would have to be something among these lines (Euclidean distance formula):

int Distance(int x1, int y1, int x2, int y2)

    {
    int dx = x2 - x1;
    int dy = y2 - y1;
    return sqrt(dx*dx + dy*dy);
    }

However, is there a way of doing this exact same thing but without using the square root (which needs the math.h library)?

EDIT: Whenever I try the following code, it gives me Floating Point Exception (Core Dumped):

float sqrt(int x) {
        int i;
        float s;
        s=((x/2)+x/(x/2)) / 2; /*first guess*/
        for(i=1;i<=4;i++) { /*average of guesses*/
            s=(s+x/s)/2;
        }
        return s;
    }

float Distance(float x1, float y1, float x2, float y2) {
    float dx = x2 - x1;
    float dy = y2 - y1;
    return sqrt(dx*dx + dy*dy);
}

int main() {
  printf("%f", Distance(1, 2, 2, 1));
  return 0;
}
5
cdistancepointssquare-root
Sure there is, but you would basically be duplicating code from the math library. - woz
Note that math.h is a header, not a library, and that the math functions are part of the standard C library. (Many many years ago, when systems were much smaller and memory was a real thing that you could really use up, the math functions were broken out into a separate library that could be left unlinked if you didn't need it.) - This isn't my real name

5 Answers

5
votes
int int_sqrt(int x){
    int s, t;

    s = 1;  t = x;
    while (s < t) {
        s <<= 1;
        t >>= 1;
    }//decide the value of the first tentative

    do {
        t = s;
        s = (x / s + s) >> 1;//x1=(N / x0 + x0)/2 : recurrence formula
    } while (s < t);

    return t;
}
1
votes

This should work. Try it out.

float sqrt(int x) {
    int i;
    float s;
    s=((x/2)+x/(x/2)) / 2; /*first guess*/
    for(i=1;i<=4;i++) { /*average of guesses*/
        s=(s+x/s)/2;
    }
    return s;
}
1
votes

You can use Babylonian methods to calculate square root. This method uses successive approximations to calculate square root.

Here is how it works

Let's say you want to calculate sqrt of 1234.

Let S = 1234,

D is number of digits in S which is = 4.

If D is even we will represent it as D = 2n+2 else if D is odd D = 2n + 1;

Here D is even so 4 = 2*1+2, so n=1.

Approx squere root of Sapprox = D * 10^n = 4 * 10^1 = 40

Let's call this X0 = Sapprox = 40.

X0 is 0th approximation.

Since S has 4 digits you will have to calculate 3 more approximations and X3 will be correct square root of S.

so X1 = 0.5(X0 + S/X0);
X1 = 0.5(40 + 1234/40) = 35.425

X2 = 0.5(X1 + S/X1); X2 = 0.5(35.42 + 1234/35.42) = 35.129

X3 = 0.5(X2 + S/X2); X3 = 0.5(35.129 + 1234/35.129) = 35.128

sqrt(1234) = 35.128

0
votes

distance calculations on a grid generally use a formula that involves the calculation of square roots. Effectively, the only way to calculate square roots without calling the sqrt() function that is part of the standard C library, is to reimplement it, poorly.

Why do you want to do that? (Or are you asking, "how can I do this without calculating square roots"? That's not a programming problem anymore.)

0
votes

Look Ma! No <math.h> (but still needs to link with libm)

#include <complex.h>
#include <stdio.h>

double distance(double x0, double y0, double x1, double y1) {
    return cabs((x0 + I*y0) - (x1 + I*y1));
}

int main(void) {
    printf("==> %7.2f\n", distance(1, 2, 2, 1));
    printf("==> %7.2f\n", distance(1, 0, 4, 0));
    printf("==> %7.2f\n", distance(1, 1, 4, 4));
}