计算两个 CGPoint 之间距离的最快方法？

Question

两点之间的距离：

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

有没有办法在 Objective-C 中更快地进行数学计算？

编辑：我想我需要澄清上面。我写上面的公式只是为了澄清我使用什么公式来计算距离。 ^ 并不意味着表示 xor - 我只是想表示数学公式，而不使用任何函数，如 pow 或任何东西，所以我打算使用 ^ 来“提高电源关闭”。我想知道是否有人知道使用按位运算符或以其他方式在汇编中编写代码是否会给出优化版本。我正在 iPhone / iPad 应用程序中使用该公式。

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() 将使用堆栈并且效率较低，但在这种情况下，您的编译器可能会将其转换为 x*x 。

Answer 2

只是将其作为一个简单、美观的解决方案提供。它很可能并不比之前给出的任何更快，只是更短。我个人正在使用hypot。

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

根据docs，这将返回“(x^2+y^2) 的平方根。 ”

Answer 3

在 Intel Mac 上，Clang 将编译：

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

总计 6 条数学指令：sub、mul、sub、mul、add、sqrt；很难击败它。 （sqrt 是一条指令，尽管它需要多个周期）。

Answer 4

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

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

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() 更快，以及准确性是否足够。