不使用平方根求两点之间的距离

Question

不使用math.h库，是否有可能计算两点之间的距离？我知道使用math.h库，这将是以下公式之一（欧几里得距离公式）：

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

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

然而，有没有一种方法可以做到同样的事情，但不使用平方根（这需要math.h库）？

编辑：每当我尝试以下代码时，它会给我一个浮点异常（核心已转储）：

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

- Raphm

---

当然有，但你基本上会复制数学库中的代码。 - woz

请注意，math.h是一个头文件而不是库文件，数学函数是标准C库的一部分。（很多年前，当系统更小，内存真正可以被用尽时，数学函数被分离到单独的库中，如果您不需要它，可以将其留未连接。） - This isn't my real name

Answer 1

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

- BLUEPIXY

---

N、x1和x0来自哪里？ - Mouradif

Answer 2

这应该可以。试一下。

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

- woz

---

感谢您提供准确的答案！但是，每当我尝试以下代码时，它会给我一个浮点异常（核心已转储）：（发布编辑） - Raphm

嗯，我不确定。你的调试器有提供任何提示吗？ - woz

使用 x=0 或 x=1 调用该函数将导致在 s=((x/2)+x/(x/2)) 中除以 0。 - Flopp

Answer 3

您可以使用巴比伦方法来计算平方根。这种方法使用连续逼近来计算平方根。

以下是它的工作原理

假设您想要计算1234的平方根。

让S = 1234，

D是S中的数字数量，即4。

如果D是偶数，我们将其表示为D = 2n + 2 如果D是奇数，则 D = 2n + 1;

在这里，D是偶数，因此4 = 2 * 1 + 2，所以n = 1。

Sapprox的近似平方根= D * 10^n = 4 * 10^1 = 40

让我们把它称为X0 = Sapprox = 40。

X0是第0次逼近。

由于S有4位数，您将需要计算3个更多的逼近值，而X3将是S的正确平方根。

所以 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

- dvishal

Answer 4

看啊，妈妈！没有<math.h>（但仍需要链接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));
}

- pmg

---

当然，cabs() 将使用 sqrt() 的某种变体来实现... - Andrew Henle

Answer 5

在网格上进行距离计算通常使用涉及平方根计算的公式。实际上，如果不调用标准C库中的sqrt()函数，唯一的计算平方根的方法就是重新实现它，效果不佳。

为什么你想要这样做？（或者你是在问，“我怎样才能在不计算平方根的情况下完成这个任务？”那就不再是一个编程问题了。）

- This isn't my real name