转换为long long，利弊C

我想用long long而不是double数据类型加速我的算法。我的算法是在定向acyclic graph (DAG)中找到最短路径。简单地说，它增加了边缘的权重"E: a->b" to b，并且如果b的新权重低于前一权重，则将其与其父母设置为a一起更新。转换为long long，利弊C

我的意思是，我的算法只是一些添加和比较操作。边缘的重量原来是"double"，我可以将它们乘以大数并将它们投射到"long long"。如果这个调整使我的程序更快，值得考虑。由于四舍五入big double到long long，我如何处理不稳定性问题。

感谢

来源

2013-02-05 remo

尝试两种方法，并比较你想测量的任何标准的结果。 –

在i5 64 甚至 IMUL似乎约40％的速度[一倍以上乘法。整数加法也应该以更少的周期/更好的吞吐量发生。关于“不精确”的问题，你应该意识到双打可能比整数更不精确。

Calculate which numbers cause problems when converting decimal to floating point?

如果您有访问原始数据（例如权重的十进制表示，具有功率大十应该产生准确整数，没有任何四舍五入文物乘以他们。随着长期多头唯一的问题将是

如何解决可能的舍入不稳定性取决于您的权重的动态范围和最大迭代次数，例如，如果您的权重均小于1.0且大于2^-52，则乘以用2^52给出的确切整数没有舍入误差，那么“不稳定性”是由溢出的可能性决定的（2^12 * 2^52）> = 2^64。

来源

2013-02-05 06:47:43

我有双打，但我想要长或长得到更快的代码。它很可能非常依赖算法本身。 – remo

只要继续 - 并按照J.P.的评论做一次性能比较。（我应该提到，在未公开的测试环境中_even_ imul比双倍乘法要快 - 你可能会使用大部分的加法运算。关键字“weight”是比较乘法运算的可能原因。） –

任何想法在GPU上实现DAG的最短路径问题？ – remo

转换为long long，利弊C

回答

相关问题