编写自己的平方根函数 [英] Writing your own square root function

问题描述

你怎么写自己的函数查找整数的最准确的平方根？

How do you write your own function for finding the most accurate square root of an integer?

谷歌搜索后，我发现<一href="//web.archive.org/web/20100330183043/http://nlindblad.org/2007/04/04/write-your-own-square-root-function">this （从原文链接存档），但首先，我没弄不明白完全，第二，它是近似的了。

After googling it, I found this (archived from its original link), but first, I didn't get it completely, and second, it is approximate too.

假设平方根为最接近的整数（实际的根目录）或浮点数。

Assume square root as nearest integer (to the actual root) or a float.

推荐答案

以下计算楼层（开方（N））的N> 0：

The following computes floor(sqrt(N)) for N > 0:

x = 2^ceil(numbits(N)/2)
loop:
    y = floor((x + floor(N/x))/2)
    if y >= x
        return x
    x = y

这是一个版本克兰德尔和放给牛顿的方法; Pomerance，素数：一个算法的角度。你应该使用这个版本的原因是，谁知道他们在做什么的人已经证明，它完全收敛的平方根的地板，它的简单，所以作出执行错误的概率是很小的。这也是快（尽管它可以构建一个更快的算法 - 但在做正确的要复杂得多）。正确实现的二进制搜索可以更快的非常小的N，但你不妨使用一个查找表。

This is a version of Newton's method given in Crandall & Pomerance, "Prime Numbers: A Computational Perspective". The reason you should use this version is that people who know what they're doing have proven that it converges exactly to the floor of the square root, and it's simple so the probability of making an implementation error is small. It's also fast (although it's possible to construct an even faster algorithm -- but doing that correctly is much more complex). A properly implemented binary search can be faster for very small N, but there you may as well use a lookup table.

要舍入到最近的的整数，只计算T =地板使用上面的算法（开方（4N））。若t的至少显著位被设置，则选择X =（T + 1）/ 2;否则选择T / 2。请注意，这轮上领带;你也可以四舍五入（或圆形，甚至）通过查看剩余是否为零（即是否T ^ 2 = = 4N）。

To round to the nearest integer, just compute t = floor(sqrt(4N)) using the algorithm above. If the least significant bit of t is set, then choose x = (t+1)/2; otherwise choose t/2. Note that this rounds up on a tie; you could also round down (or round to even) by looking at whether the remainder is nonzero (i.e. whether t^2 == 4N).

请注意，你并不需要使用浮点运算。事实上，你不应该。该算法应该完全使用整数来实现（尤其是，在地板（）函数仅仅指示定期整数除法应使用）。

Note that you don't need to use floating-point arithmetic. In fact, you shouldn't. This algorithm should be implemented entirely using integers (in particular, the floor() functions just indicate that regular integer division should be used).

这篇关于编写自己的平方根函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！