代码之家 › 专栏 › 技术社区 › SmacL

找到双倍数的快速方法

floating-point optimization c

SmacL · 技术社区 · 15 年前

如果具有以下C函数,用于确定一个数字是否是另一个数字的倍数,以达到任意公差

#include <math.h>

#define TOLERANCE 0.0001

int IsMultipleOf(double x,double mod)
{
    return(fabs(fmod(x, mod)) < TOLERANCE);
}

它工作得很好,但是分析显示它非常慢,以至于它已经成为优化的候选对象。大约75%的时间花在 modulo 剩下的在 fabs . 我正试图找到一种加快速度的方法,使用类似查找表的方法。参数 x 定期变化,而 mod 变化很少。x的可能值的数目足够小,查找空间不会成为问题,通常是几百个可能值中的一个。我可以摆脱 法布斯 很容易,但无法找到一个合理的模的替代方案。关于如何优化上述内容有什么想法吗?

编辑该代码将在Windows桌面和移动设备上运行,因此处理器可能包括Intel、桌面上的AMD以及移动设备上的ARM或SH4。VisualStudio 2008是编译器。

8 回复 | 直到 15 年前

Martin Wickman 15 年前

你真的要用吗 modulo 为了这个?

难道不可能 result = x / mod 然后检查 result 接近0。例如:

11 / 5.4999 = 2.000003  ==> 0.000003 < TOLERANCE

或者类似的。

Jens Gustedt 15 年前

除法(浮点与否, fmod 在您的情况下)通常是一个执行时间因CPU和编译器而异的操作:

GCC内置了
如果你给它正确的编译标志或如果使用 __builtin_fmod 明确地。这可能会映射少量操作汇编程序指令。
可能会有特殊单位,如SSE 在英特尔处理器上, 操作执行更多高效

通过这些技巧,取决于您的环境(您不知道是哪个),时间可能会从一些时钟周期变化到几百个。我认为最好的方法是查看编译器和CPU的文档,以便执行特定的操作。

Sparky 15 年前

以下可能是过度杀伤力和次优。但这里值得一提的是如何做到这一点。

我们知道双引号的格式…

符号1位
11位表示有偏指数
52位小数

让…

值=x/mod;
exp=值的指数位-偏差;
lsb=值的小数位的最小sig位;

一旦你有了它…

/*
 * If applying the exponent would eliminate the fraction bits
 * then for double precision resolution it is a multiple.
 * Note: lsb may require some massaging.
 */
if (exp > lsb)
    return (true);

if (exp < 0)
    return (false);

唯一剩下的情况是公差情况。建立你的双精度,这样你就可以去掉小数左边的所有数字。

符号位为零(正)
指数是偏差(1023我认为…查清楚)
适当地移动分数位

现在把它和你的宽容相比较。

Roddy 15 年前

我想你需要检查一下你的心脏瓣膜 fmod() 函数:x86 fpu's have' FPREM/FPREM1 '通过重复减法计算余数的指令。

虽然浮点除法是一条指令,但似乎您可能需要反复调用fprem来获得模数的正确答案,因此RTL可能不会使用它。

nategoose 15 年前

我根本没有测试过这个,但是从我理解fmod的方式来看,它应该是等效的内联的,这可能会让编译器更好地优化它,尽管我会认为编译器的数学库(或内置的)也可以工作。(而且,我甚至不知道这是否正确)。

#include <math.h>

int IsMultipleOf(double x, double mod) {
    long n = x / mod;  // You should probably test for /0 or NAN result here
    double new_x = mod * n;
    double delta = x - new_x;
    return fabs(delta) < TOLERANCE;  // and for NAN result from fabs
}

Tometzky 15 年前

如果你有可比的数据量表,也许你可以选择长距离而不是双精度。例如 long long 就够了 60 astronomical units in micrometer resolution .

Paul R 15 年前

是吗? 需要双精度?根据您的数学库有多好,这应该更快:

#include <math.h>

#define TOLERANCE 0.0001f

bool IsMultipleOf(float x, float mod)
{
    return(fabsf(fmodf(x, mod)) < TOLERANCE);
}

thomasfedb 15 年前

我想模在内部看起来有点像这样:

mod(x,m) {
  while (x > m) {
    x = x - m
  }
  return x
}

我认为通过某种搜索,我可以得到优化:例如:

fastmod(x,m) {
  q = 1

  while (m * q < x) {
    q = q * 2
  }

  return mod((x - (q / 2) * m), m)
}

您甚至可以选择用对fastmod的annother调用替换对mod的finall调用,并添加条件,如果x<m然后返回x。