计算两个CGPoints之间距离的最快方法是什么？

Question

两点之间的距离：

sqrt((x1-x2)^2 + (y1-y2)^2)

有没有一种更快的方法在Objective-C中进行这个数学计算？

编辑：我认为我需要澄清一下上面的内容。我写上面的公式只是为了澄清我正在使用的计算距离的公式。^并不表示异或 - 我只是想用数学公式表示，而不使用任何函数如pow等，所以我想使用^来代表“乘方”。我想知道是否有人知道使用位运算符，或以其他方式编写代码的汇编版本是否会得到优化。我在一个iPhone/iPad应用程序中使用这个公式。

- xcoder

---

我只是想知道有没有人知道执行这种计算的最快方法。通常我会直接写出公式并使用 pow 或其他函数，但我不确定是否使用乘法运算符或位运算符能够产生更快的结果。 - xcoder

Answer 1

不行，如果你需要准确的距离，那么你无法打败那个公式。

虽然需要明确的是，^ 不是用于对一个值进行平方运算的操作符，而是执行异或位运算的操作符。

你需要使用类似以下的内容：

double dx = (x2-x1);
double dy = (y2-y1);
double dist = sqrt(dx*dx + dy*dy);

如果你可以只使用正方形（当你只想按距离排序时很有用），那么你可以使用更高效的

double dx = (x2-x1);
double dy = (y2-y1);
double dist = dx*dx + dy*dy;

这些解决方案至少和pow()函数一样好。在最坏的情况下，pow()会使用堆栈并且效率较低，但也有可能你的编译器会将其转换为x*x以提高效率。

- Michael Chinen

---

+1 你可以肯定，pow 函数的执行时间至少比 * 运算符慢一个数量级，而且我认为编译器无法对 pow 进行优化，因为它不能确定 pow 是否已被替换为完全不同的函数。 - Mike Dunlavey

另外，hypot(dx, dy)。 - The Paramagnetic Croissant

Answer 2

我提供一个简单、好看的解决方案。它可能不比之前提供的任何方法更快，只是更短。我个人正在使用 hypot。

double dist = hypot((x1-x2), (y1-y2));

根据文档，这将返回“（x^2+y^2）的平方根”。

- Firo

Answer 3

在Intel Mac上，Clang可以编译：

double distance = ({double d1 = x1 - x2, d2 = y1 - y2; sqrt(d1 * d1 + d2 * d2); });

将数学计算压缩成了仅有6条指令：减、乘、减、乘、加、开方；这是相当难以超越的。（虽然sqrt只占用了一条指令，但需要多个周期完成。）

- CRD

Answer 4

double dist = sqrt ( pow((x1-x2), 2) + pow((y1-y2), 2) );

考虑到x1, x2, y1, y2是float、double或整数。

- Ilanchezhian

---

我认为一个通用的指数函数（pow）计算平方不会比简单的乘法更快。 - Alexey Frunze

Answer 5

这里唯一需要改进的是平方根计算函数。

我尝试了这两个函数（在维基百科上的一个关于平方根计算的文章中找到），用于计算近似平方根值：

float fsqrt(float x)
{
  float xhalf = 0.5f * x;
  union
  {
    float x;
    int i;
  } u;

  u.x = x;
  u.i = 0x5f3759df - (u.i >> 1);
  x *= u.x * (1.5f - xhalf * u.x * u.x);

  return x;
}

float fsqrt2(float z)
{
    union
    {
        int tmp;
        float f;
    } u;

    u.f = z;

    /*
     * To justify the following code, prove that
     *
     * ((((val_int / 2^m) - b) / 2) + b) * 2^m = ((val_int - 2^m) / 2) + ((b + 1) / 2) * 2^m)
     *
     * where
     *
     * val_int = u.tmp
     * b = exponent bias
     * m = number of mantissa bits
     *
     * .
     */

    u.tmp -= 1 << 23; /* Subtract 2^m. */
    u.tmp >>= 1; /* Divide by 2. */
    u.tmp += 1 << 29; /* Add ((b + 1) / 2) * 2^m. */

    return u.f;
}

但是在我的Core 2 Duo Pentium CPU上，它们似乎并不比x87 FPU的FSQRT指令更快。请检查它们是否在您的平台上比标准的sqrtf()/sqrt()函数更快，并且精度是否足够。

- Alexey Frunze