3

假设我们有这些不等式：

if (a*a+b*b>0) {
    ...
}

if (a*b+c*d>0) {
    ...
}

显然，它们都需要 2 次乘法来评估。
问题是，我们真的需要计算 2 个全精度乘积来检查这些表达式是否为正吗？
是否有任何数学技巧可以让我编写这些 if 命令而无需评估 2 个产品？
会更快吗？
或者编译器可能会尽可能快地处理它？
我是不是想多了？

编辑：嗯，升级很快。我只想指出，我是在笼统地说。无论如何，我的任何项目都不需要这样的微优化。另外，是的，我本可以省略第一个，因为它太琐碎了。可能第二个更有趣。

4

4 回答 4

2

Your "am I overthinking" question suggests me that you haven't found this to be an actual bottleneck by really profiling your code. So I'd say yes, you're just trying to do premature optimization.

However, if this really is a major performance-critical part of your application, then the only improvement I can think of right now is the following. Since squares of real numbers can never be negative, then "a squared is greater than zero" is equivalent with "a is not zero". So if comparisons are fast (well, that's relative -- faster than multiplication) on your architecture, then

if (a*a+b*b>0) {
    ...
}

can be written as

if (a || b) {
    ...
}

(provided that no corner cases arise. If the variables are signed integers or floating-point numbers representing real numbers, then this should be fine. If, however, there are some unsigned integer overflow or complex numbers involved, then you will have to perform additional checks, and at that point, it's hard to reason about the relative performance without true profiling.)

I don't have such a "clever" "optimization" for the second case in my mind, but perhaps someone else can come up with something similar -- if and only if it is absolutely necessary. Not otherwise -- code readability is preferred over performance when performance is not critical.

于 2013-11-23T23:12:08.127 回答
1

我假设这些表达式都不会溢出，因为类型没有溢出的概念，或者因为值在范围内。当溢出和潜在的回绕进入图片时（例如 ifa和bare unsigned int）应用不同的规则。

第一条语句显然等价于

if (a != 0 || b != 0)

或者

if (a || b)

它用一个额外的分支换取两个乘法和一个加法。

第二个语句更有趣：我认为确定操作数的符号并且仅在符号相反时才进行实际数学运算是合理a*b的c*d。在所有其他情况下，可以在不知道实际值的情况下确定条件。我猜，结果逻辑是否比计算快取决于类型。

于 2013-11-23T23:15:45.000 回答
1

第一个将始终 >= 0。当且仅当a和b为 0 时，它将为 0，因此它相当于：

if (a || b) {
   ...
}

关于第二个：如果 sign ofa等于 sign of b，并且 sign ofc等于 sign of d，那么情况同上：

if (sign(a)==sign(b) && sign(c)==sign(d))
{
  if ((a && b) || (c && d))
  {
    ... > 0
  }
  else
  {
    ... = 0
  }
}
else
{
  if (sign(a)*sign(b)==sign(c)*sign(d))
  {
     ... <= 0
  }
  else
  {
    /* must do the actual product to find out */
  }
}

对于符合 IEEE-754 的浮点数，符号位于每个数字的 MSb 处。

对于模拟 FP 的环境，您可以做一件事来优化比较：如果您只是比较产品的两个结果，则可以避免添加，如下所示：

if (a*b>c*d) {
   ...
}

这有点快，因为要比较两个浮点数，您只需将它们作为有符号整数进行比较，并且没有 FP 的 CPU 肯定有资源来比较两个整数，比它花在 FP 软件上的时间要快添加。

于 2013-11-23T23:17:05.083 回答
0

另一个重写（假设您使用浮点数，它们是32 位宽并且符合 IEEE 754，并且大小与 int 相同；是的，这是 hacky 和平台相关的）。

对于第一种情况，您可以使用单个按位 'or' & 'and'（and 用于忽略符号位和指数，仅保留尾数；如果不能有任何 -0，则可以将其删除） ：

if (*((int *)&a) | (*(int *)&b) & 0x7FFFFF) { // a*a + b*b>0
  ...
}

我真的怀疑第二种情况是否存在类似的无分支魔法。

于 2013-11-23T23:47:07.930 回答