CODEWITHSUNDEEP
cdistancepointssquare-root
Raphm
Raphm

Reputation: 105

Distance between two points without using the square root

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;
}

Upvotes: 7

Views: 19946

Answers (5)

pmg
pmg

Reputation: 108988

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));
}

Upvotes: 0

BLUEPIXY
BLUEPIXY

Reputation: 40145

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;
}

Upvotes: 5

dvishal
dvishal

Reputation: 166

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

Upvotes: 1

woz
woz

Reputation: 10994

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;
}

Upvotes: 1

This isn&#39;t my real name
This isn&#39;t my real name

Reputation: 5029

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.)

Upvotes: 0

Related Questions