问题标签 [sqrt]

（编辑：让我们把它命名为“测量如何出错的教训。”我仍然没有弄清楚究竟是什么导致了这种差异。）

我在这里找到了 Mark Crowne的一个非常快的整数平方根函数。至少在我的机器上使用 GCC，它显然是我测试过的最快的整数平方根函数（包括标准库中的 Hacker's Delight、this page和 floor(sqrt()) 中的函数）。

在稍微清理一下格式、重命名变量并使用固定宽度类型之后，它看起来像这样：

INNER_ISQRT 宏并不太邪恶，因为它是本地的并且在不再需要后立即未定义。尽管如此，原则上我仍然想将其转换为内联函数。我已经在几个地方（包括 GCC 文档）阅读了有关内联函数与宏“一样快”的断言，但是在不影响速度的情况下转换它时遇到了麻烦。

我当前的迭代看起来像这样（注意 always_inline 属性，我把它放在了很好的衡量标准）：

不管我做什么，内联函数总是比宏慢。使用 -O2 构建的 (2^28 - 1) 次迭代，宏版本的时间通常在 2.92 秒左右，而内联版本的时间通常在 3.25 秒左右。编辑：我之前说过 2^32 - 1 次迭代，但我忘记了我已经改变了它。他们需要更长的时间才能获得完整的色域。

编译器可能只是愚蠢并拒绝内联它（再次注意 always_inline 属性！），但如果是这样，那无论如何都会使宏版本通常更可取。（我尝试检查程序集以查看，但它作为程序的一部分太复杂了。当我尝试只编译函数时，优化器省略了所有内容，并且由于对 GCC 不熟悉，我在将其编译为库时遇到了问题.)

简而言之，有没有办法把它写成内联而不影响速度？（我没有分析过，但是 sqrt 是那些应该始终快速完成的基本操作之一，因为我可能在许多其他程序中使用它，而不仅仅是我目前感兴趣的程序。此外，我只是好奇.)

我什至尝试使用模板来“烘焙”常量值，但我觉得其他两个参数更有可能导致命中（宏可以避免这种情况，因为它直接使用局部变量）.. .好吧，无论是那个还是编译器都顽固地拒绝内联。

更新：下面的 user1034749 将这两个函数放在单独的文件中并编译它们时，从这两个函数中获得相同的程序集输出。我尝试了他的确切命令行，并且得到了与他相同的结果。出于所有意图和目的，这个问题得到了解决。

但是，我仍然想知道为什么我的测量结果会有所不同。显然，我的测量代码或原始构建过程导致情况有所不同。我将在下面发布代码。有谁知道这笔交易是什么？也许我的编译器实际上在我的 main() 函数的循环中内联了整个 mcrowne_isqrt() 函数，但它没有内联整个其他版本？

更新 2（在测试代码之前压缩）：请注意，如果我交换测试的顺序并使内联版本排在第一位，则内联版本的输出速度比宏版本快相同的数量。这是一个缓存问题，还是编译器内联一个调用而不是另一个，或者什么？

更新3：我仍然不知道如何可靠地比较不同功能的时间，而不需要根据测试的顺序来确定时间。我将不胜感激任何提示！

但是，如果其他阅读本文的人对快速 sqrt 实现感兴趣，我应该提一下：Mark Crowne 的代码测试速度比我尝试过的任何其他纯 C/C++ 版本都快（尽管测试存在可靠性问题），但以下对于标量 32 位整数 sqrt，SSE 代码似乎可能会更快一些。它不能被推广到成熟的 64 位无符号整数输入而不损失精度（并且第一个有符号转换也必须由处理值 >= 2^63 的固有负载替换）：

我正在尝试计算 Ruby 中一个非常大的数字的平方根。我遇到的问题是 Math.sqrt 函数看起来像这样

sqrt(numeric) → float

如果我给它一个非常大的数字，它会给我 FloatDomainError: Infinity。

sqrt()返回 BigNum的最佳方法是什么？这可能有一个宝石，还是我必须编写自己的函数来计算平方根？

在这种情况下，最简单的方法是什么？泰勒级数？数字的平方根总是整数。

我正在使用 Dobb 博士的文章“ Optimizing Math-Intensive Applications with Fixed-Point Arithmetic ”中描述的 Anthony Williams 的定点库，使用Rhumb Line 方法计算两个地理点之间的距离。

当点之间的距离很长（大于几公里）时，这很有效，但在较小的距离时效果很差。最坏的情况是当两个点相等或接近相等时，结果是 194 米的距离，而我需要在 >= 1 米的距离处至少 1 米的精度。

通过与双精度浮点实现进行比较，我发现了函数的问题，该fixed::sqrt()函数在较小的值下表现不佳：

通过将其视为特殊情况来纠正结果fixed::sqrt(0)是微不足道的，但这并不能解决小的非零距离的问题，其中误差从 194 米开始并随着距离的增加收敛到零。我可能需要至少一个数量级的精度提高到零。

该fixed::sqrt()算法在上面链接的文章的第 4 页上进行了简要说明，但我很难遵循它，更不用说确定是否可以改进它。该函数的代码复制如下：

注意m_nVal是内部定点表示值，它是一个int64_t并且表示使用Q36.28格式（fixed_resolution_shift= 28）。该表示本身具有至少 8 位小数的足够精度，并且作为赤道弧的一小部分适用于大约 0.14 米的距离，因此限制不是定点表示。

使用恒向线法是该应用程序的标准机构建议，因此无法更改，并且在任何情况下，在应用程序的其他地方或将来的应用程序中都可能需要更准确的平方根函数。

问题：是否有可能提高fixed::sqrt()算法对小的非零值的准确性，同时仍保持其有界和确定性收敛？

附加信息 用于生成上表的测试代码：

结论 根据 Justin Peel 的解法和分析，并与《被忽视的定点算术艺术》中的算法进行比较，我将后者改编如下：

虽然这提供了更高的精度，但我需要的改进并没有实现。仅 Q36.28 格式就提供了我需要的精度，但不可能在不损失几位精度的情况下执行 sqrt()。然而，一些横向思维提供了更好的解决方案。我的应用程序根据某个距离限制测试计算出的距离。事后看来，相当明显的解决方案是测试距离的平方与极限的平方！

我的程序的一部分是计算sqrt浮点数。当我写sqrt(1.0f);我成功编译程序，但当我写sqrt(-1.0f); 编译失败undefined reference to 'sqrt'- 我想在这种情况下，nan值将被返回......我使用 gcc 编译程序。当我用 Visual Studio 编译它时，它会以 sqrt 的否定参数成功编译。问题怎么解决 谢谢

我正在尝试为最有可能在 FPGA 上实现的高效平方根算法找到更多信息。已经找到了很多算法，但哪一种是来自英特尔或 AMD 的？高效是指它们要么非常快，要么不需要太多内存。

编辑：我可能应该提到这个问题通常是一个浮点数，因为大多数硬件都实现了 IEEE 754 标准，其中数字表示为：1 个符号位、8 位偏置指数和 23 位尾数。

谢谢！

为什么输出给出 3 ，期望 -3。如何在c中处理这种预处理？

我搜索了与我的问题相似的问题Similar question 。但我的问题是使用 Turbo C 编译器 v3.0 时。我应该为 math.h 文件做一些额外的工作吗？请帮忙。

输出是这样的：

输入 # 表示平方根。

64

a = 0.000000

a = 0.000000，平方根为 0.000000

我的目标是打印***平方根是否为负。但我想不出一种将默认nan文本更改为的方法***

那么，我应该在 if 语句中写些什么才能使它成为可能呢？或者也许还有另一种方法来检查 y 是否为 nan 然后打印*

我在 for 循环中的代码中出现错误for ( j = 3; j <=sqrt(num); j +=2)：

多个重载函数“sqrt”实例与参数列表匹配。

我该如何解决？

我正在运行这段代码来计算平方根，x[i][j] - y[j]但它让我胡说八道！

第一个outFile打印 0 这是原始值，但第二个打印-1.#IND.