编写自己的平方根函数(Writing your own square root function)

2019-09-01 04:33发布

你如何写找到一个整数的最准确的平方根自己的功能?

谷歌搜索之后,我发现这个 (从存档原始链接 ),但首先,我并没有完全得到它,第二,它是近似了。

假设平方根为最接近的整数(实际根)或浮动。

Answer 1:

下面的代码计算地板(SQRT(N))为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,但你不妨使用一个查找表。

舍入到整数,使用上面的算法只是计算T =地板(SQRT(4N))。 如果T的至少显著位被设置,则选择X =(T + 1)/ 2; 否则选择T / 2。 请注意,这围捕上领带; 你也可以四舍五入(或轮偶数)通过查看剩余是否为非零(即T是否^ 2 = = 4N)。

请注意,您不需要使用浮点运算。 事实上,你不应该。 该算法应该完全使用整数来实现(特别是地板()函数只是表明普通整数除法应该使用)。



Answer 2:

根据您的需求,可以使用一个简单的分而治之的策略。 它不会收敛一些其它方法 ,但它可能是一个更容易为新手理解。 另外,由于它是一个为O​​(log n)的算法(减半搜索空间中的每个迭代),对于一个32位浮点最坏的情况下将是32次迭代。

比方说,你想要的62.104平方根。 你选择一个中间值介于0和,并且将其平方。 如果正方形是比你的数字越高,你需要专注于低于中点号。 如果它太低,集中于那些高。

有了真正的数学,你可以保持分裂的搜索空间两个永远(如果没有一个合理的平方根)。 在现实中,计算机将最终耗尽的精度和你有你逼近。 下面的C程序说明了这一点:

#include <stdio.h>
#include <stdlib.h>

int main (int argc, char *argv[]) {
    float val, low, high, mid, oldmid, midsqr;
    int step = 0;

    // Get argument, force to non-negative.

    if (argc < 2) {
        printf ("Usage: sqrt <number>\n");
        return 1;
    }
    val = fabs (atof (argv[1]));

    // Set initial bounds and print heading.

    low = 0;
    high = mid = val;
    oldmid = -1;

    printf ("%4s  %10s  %10s  %10s  %10s  %10s    %s\n",
        "Step", "Number", "Low", "High", "Mid", "Square", "Result");

    // Keep going until accurate enough.

    while (fabs(oldmid - mid) >= 0.00001) {
        oldmid = mid;

        // Get midpoint and see if we need lower or higher.

        mid = (high + low) / 2;
        midsqr = mid * mid;
        printf ("%4d  %10.4f  %10.4f  %10.4f  %10.4f  %10.4f  ",
            ++step, val, low, high, mid, midsqr);
        if (mid * mid > val) {
            high = mid;
            printf ("- too high\n");
        } else {
            low = mid;
            printf ("- too low\n");
        }
    }

    // Desired accuracy reached, print it.

    printf ("sqrt(%.4f) = %.4f\n", val, mid);
    return 0;
}

这里有一对夫妇运行的,所以你希望得到一个想法,它是如何工作的。 对于77:

pax> sqrt 77
Step      Number         Low        High         Mid      Square    Result
   1     77.0000      0.0000     77.0000     38.5000   1482.2500  - too high
   2     77.0000      0.0000     38.5000     19.2500    370.5625  - too high
   3     77.0000      0.0000     19.2500      9.6250     92.6406  - too high
   4     77.0000      0.0000      9.6250      4.8125     23.1602  - too low
   5     77.0000      4.8125      9.6250      7.2188     52.1104  - too low
   6     77.0000      7.2188      9.6250      8.4219     70.9280  - too low
   7     77.0000      8.4219      9.6250      9.0234     81.4224  - too high
   8     77.0000      8.4219      9.0234      8.7227     76.0847  - too low
   9     77.0000      8.7227      9.0234      8.8730     78.7310  - too high
  10     77.0000      8.7227      8.8730      8.7979     77.4022  - too high
  11     77.0000      8.7227      8.7979      8.7603     76.7421  - too low
  12     77.0000      8.7603      8.7979      8.7791     77.0718  - too high
  13     77.0000      8.7603      8.7791      8.7697     76.9068  - too low
  14     77.0000      8.7697      8.7791      8.7744     76.9893  - too low
  15     77.0000      8.7744      8.7791      8.7767     77.0305  - too high
  16     77.0000      8.7744      8.7767      8.7755     77.0099  - too high
  17     77.0000      8.7744      8.7755      8.7749     76.9996  - too low
  18     77.0000      8.7749      8.7755      8.7752     77.0047  - too high
  19     77.0000      8.7749      8.7752      8.7751     77.0022  - too high
  20     77.0000      8.7749      8.7751      8.7750     77.0009  - too high
  21     77.0000      8.7749      8.7750      8.7750     77.0002  - too high
  22     77.0000      8.7749      8.7750      8.7750     76.9999  - too low
  23     77.0000      8.7750      8.7750      8.7750     77.0000  - too low
sqrt(77.0000) = 8.7750

对于62.104:

pax> sqrt 62.104
Step      Number         Low        High         Mid      Square    Result
   1     62.1040      0.0000     62.1040     31.0520    964.2267  - too high
   2     62.1040      0.0000     31.0520     15.5260    241.0567  - too high
   3     62.1040      0.0000     15.5260      7.7630     60.2642  - too low
   4     62.1040      7.7630     15.5260     11.6445    135.5944  - too high
   5     62.1040      7.7630     11.6445      9.7037     94.1628  - too high
   6     62.1040      7.7630      9.7037      8.7334     76.2718  - too high
   7     62.1040      7.7630      8.7334      8.2482     68.0326  - too high
   8     62.1040      7.7630      8.2482      8.0056     64.0895  - too high
   9     62.1040      7.7630      8.0056      7.8843     62.1621  - too high
  10     62.1040      7.7630      7.8843      7.8236     61.2095  - too low
  11     62.1040      7.8236      7.8843      7.8540     61.6849  - too low
  12     62.1040      7.8540      7.8843      7.8691     61.9233  - too low
  13     62.1040      7.8691      7.8843      7.8767     62.0426  - too low
  14     62.1040      7.8767      7.8843      7.8805     62.1024  - too low
  15     62.1040      7.8805      7.8843      7.8824     62.1323  - too high
  16     62.1040      7.8805      7.8824      7.8815     62.1173  - too high
  17     62.1040      7.8805      7.8815      7.8810     62.1098  - too high
  18     62.1040      7.8805      7.8810      7.8807     62.1061  - too high
  19     62.1040      7.8805      7.8807      7.8806     62.1042  - too high
  20     62.1040      7.8805      7.8806      7.8806     62.1033  - too low
  21     62.1040      7.8806      7.8806      7.8806     62.1038  - too low
  22     62.1040      7.8806      7.8806      7.8806     62.1040  - too high
  23     62.1040      7.8806      7.8806      7.8806     62.1039  - too high
sqrt(62.1040) = 7.8806

对于49:

pax> sqrt 49
Step      Number         Low        High         Mid      Square    Result
   1     49.0000      0.0000     49.0000     24.5000    600.2500  - too high
   2     49.0000      0.0000     24.5000     12.2500    150.0625  - too high
   3     49.0000      0.0000     12.2500      6.1250     37.5156  - too low
   4     49.0000      6.1250     12.2500      9.1875     84.4102  - too high
   5     49.0000      6.1250      9.1875      7.6562     58.6182  - too high
   6     49.0000      6.1250      7.6562      6.8906     47.4807  - too low
   7     49.0000      6.8906      7.6562      7.2734     52.9029  - too high
   8     49.0000      6.8906      7.2734      7.0820     50.1552  - too high
   9     49.0000      6.8906      7.0820      6.9863     48.8088  - too low
  10     49.0000      6.9863      7.0820      7.0342     49.4797  - too high
  11     49.0000      6.9863      7.0342      7.0103     49.1437  - too high
  12     49.0000      6.9863      7.0103      6.9983     48.9761  - too low
  13     49.0000      6.9983      7.0103      7.0043     49.0598  - too high
  14     49.0000      6.9983      7.0043      7.0013     49.0179  - too high
  15     49.0000      6.9983      7.0013      6.9998     48.9970  - too low
  16     49.0000      6.9998      7.0013      7.0005     49.0075  - too high
  17     49.0000      6.9998      7.0005      7.0002     49.0022  - too high
  18     49.0000      6.9998      7.0002      7.0000     48.9996  - too low
  19     49.0000      7.0000      7.0002      7.0001     49.0009  - too high
  20     49.0000      7.0000      7.0001      7.0000     49.0003  - too high
  21     49.0000      7.0000      7.0000      7.0000     49.0000  - too low
  22     49.0000      7.0000      7.0000      7.0000     49.0001  - too high
  23     49.0000      7.0000      7.0000      7.0000     49.0000  - too high
sqrt(49.0000) = 7.0000


Answer 3:

一个简单的(但不是非常快)的方法来计算X的平方根:

squareroot(x)
    if x<0 then Error
    a = 1
    b = x
    while (abs(a-b)>ErrorMargin) 
        a = (a+b)/2
        b = x/a
    endwhile
    return a;

例如:平方根(70000)

    a       b
    1   70000
35001       2
17502       4
 8753       8
 4381      16
 2199      32
 1116      63
  590     119
  355     197
  276     254
  265     264

正如你可以看到它限定上部和下部边界的平方根和,直到它的大小是可以接受的变窄的边界。

还有更有效的方法,但这个说明了这个过程,很容易理解。

只是要注意,如果使用其他的整数你有一个无限循环的Errormargin设置为1。



Answer 4:

我要指出计算平方根的倒数1 / SQRT(X)的一个非常有趣的方法,它是在游戏设计界的传奇人物,因为它是令人boggingly快。 或等待,请阅读以下职位:

http://betterexplained.com/articles/understanding-quakes-fast-inverse-square-root/

PS:我知道你只是想平方根,但地震的优雅克服了我的一部分:)一切阻力

顺便说一句,上述文章还谈到了枯燥的牛顿迭代近似的地方。



Answer 5:

当然,这是近似的; 这是与浮点数是如何工作的数学。

总之,标准的方法是用牛顿法 。 这是关于与使用泰勒级数,自带立即想到的其他方式。



Answer 6:

计算平方根使用Python任意精度

#!/usr/bin/env python
import decimal

def sqrt(n):
    assert n > 0
    with decimal.localcontext() as ctx:
        ctx.prec += 2 # increase precision to minimize round off error
        x, prior = decimal.Decimal(n), None
        while x != prior: 
            prior = x
            x = (x + n/x) / 2 # quadratic convergence 
    return +x # round in a global context


decimal.getcontext().prec = 80 # desirable precision
r = sqrt(12345)
print r
print r == decimal.Decimal(12345).sqrt()

输出:

111.10805551354051124500443874307524148991137745969772997648567316178259031751676
True


Answer 7:

这是一个常见的面试问题被Facebook等要求,我不认为这是用牛顿法在接受记者采访是一个好主意。 如果面试官问你的牛顿方法的机理,当你真的不明白吗?

我公司提供的Java中的二进制搜索基础的解决方案,我相信大家都能明白。

public int sqrt(int x) {

    if(x < 0) return -1;
    if(x == 0 || x == 1) return x;

    int lowerbound = 1;
    int upperbound = x;
    int root = lowerbound + (upperbound - lowerbound)/2;

    while(root > x/root || root+1 <= x/(root+1)){
        if(root > x/root){
            upperbound = root;
        } else {
            lowerbound = root;
        }
        root = lowerbound + (upperbound - lowerbound)/2;
    }
    return root;
}

你可以在这里测试我的代码: 本文给出了:SQRT(X)



Answer 8:

发现了大约一个伟大的文章整数平方根 。

这是因为它提出一个有小幅改进版:

unsigned long sqrt(unsigned long a){
    int i;
    unsigned long rem = 0;
    unsigned long root = 0;
    for (i = 0; i < 16; i++){
        root <<= 1;
        rem = (rem << 2) | (a >> 30);
        a <<= 2;
        if(root < rem){
            root++;
            rem -= root;
            root++;
        }
    }
    return root >> 1;
}


Answer 9:

下面是获得使用三角平方根的方式。 这不是最快的算法通过跳槽,但它是精确的。 代码是在javascript:

var n = 5; //number to get the square root of
var icr = ((n+1)/2); //intersecting circle radius
var sqrt = Math.cos(Math.asin((icr-1)/icr))*icr; //square root of n
alert(sqrt);


Answer 10:

还有的是,我在学校里,你可以用它来计算确切的平方根(或任意大型精密如果根是无理数)研究的算法。 这绝对比牛顿的算法慢,但它是精确的。 比方说,你要计算的531.3025平方根

的第一件事是你把你的电话号码从小数点到2个位数的组开始:
{5} {31}。{30} {25}
然后:
1)求其是小于或等于第一组的实际平方根第一组最接近的平方根:SQRT({5})> = 2。这平方根是您的最终答案的第一个数字。 让我们表示这样的时刻B = 2,我们已经找到了我们最后的平方根为B的数字。
2)接着计算之间的差{5}和B ^ 2:5 - 4 = 1。
3)对于所有后续2个组执行以下操作:
乘以100残余物,然后将其添加到第二组:100 + 31 = 131。
发现X - 你的根的下一个数字,使得131> =((B * 20)+ X)* X。 X = 3。43 * 3 = 129 <131现在B = 23。另外,因为你没有更多的2位数字组,小数点的左边,你已经找到你的最后根的所有整数数字。
4)重复进行30 {}和{25}相同。 所以你有了:
{30}:131 - 129 = 2 2 * 100 + 30 = 230> =(23 * 2 * 10 + X)* X - > X = 0 - > B = 23.0
{25}:230 - 0 = 230 230 * 100 + 25 = 23025. 23025> =(230 * 2 * 10 + X)* X - > X = 5 - > B = 23.05
最终结果= 23.05。
该算法看起来很复杂这种方式,但它是更简单,如果你使用你使用“长除法”你学习在学校,除非你不做分割,而是计算平方根相同的符号写在纸上。



Answer 11:

的第一件事,我想到的是:这是使用二进制搜索的好地方(通过这个伟大的启发教程 。)

要查找的平方根vaule ,我们正在寻找的number(1..value)其中预测是首次如此。 我们在选择的预测是number * number - value > 0.00001

double square_root_of(double value)
{
     assert(value >= 1);
     double lo = 1.0;
     double hi = value;

     while( hi - lo > 0.00001)
     {
          double mid = lo + (hi - lo) / 2 ;
          std::cout << lo << "," << hi << "," << mid << std::endl;
          if( mid * mid - value > 0.00001)    //this is the predictors we are using 
          {
              hi = mid;
          } else {
              lo = mid;
          }

     }

    return lo;
 }


Answer 12:

// Fastest way I found, an (extreme) C# unrolled version of:
// http://www.hackersdelight.org/hdcodetxt/isqrt.c.txt         (isqrt4)

// It's quite a lot of code, basically a binary search (the "if" statements)
// followed by an unrolled loop (the labels).
// Most important: it's fast, twice as fast as "Math.Sqrt".
// On my pc: Math.Sqrt ~35 ns, sqrt <16 ns (mean <14 ns)

private static uint sqrt(uint x)
{
    uint y, z;
    if (x < 1u << 16)
    {
        if (x < 1u << 08)
        {
            if (x < 1u << 04) return x < 1u << 02 ? x + 3u >> 2 : x + 15u >> 3;
            else
            {
                if (x < 1u << 06)
                { y = 1u << 03; x -= 1u << 04; if (x >= 5u << 02) { x -= 5u << 02; y |= 1u << 02; } goto L0; }
                else
                { y = 1u << 05; x -= 1u << 06; if (x >= 5u << 04) { x -= 5u << 04; y |= 1u << 04; } goto L1; }
            }
        }
        else                                             // slower (on my pc): .... y = 3u << 04; } goto L1; }
        {
            if (x < 1u << 12)
            {
                if (x < 1u << 10)
                { y = 1u << 07; x -= 1u << 08; if (x >= 5u << 06) { x -= 5u << 06; y |= 1u << 06; } goto L2; }
                else
                { y = 1u << 09; x -= 1u << 10; if (x >= 5u << 08) { x -= 5u << 08; y |= 1u << 08; } goto L3; }
            }
            else
            {
                if (x < 1u << 14)
                { y = 1u << 11; x -= 1u << 12; if (x >= 5u << 10) { x -= 5u << 10; y |= 1u << 10; } goto L4; }
                else
                { y = 1u << 13; x -= 1u << 14; if (x >= 5u << 12) { x -= 5u << 12; y |= 1u << 12; } goto L5; }
            }
        }
    }
    else
    {
        if (x < 1u << 24)
        {
            if (x < 1u << 20)
            {
                if (x < 1u << 18)
                { y = 1u << 15; x -= 1u << 16; if (x >= 5u << 14) { x -= 5u << 14; y |= 1u << 14; } goto L6; }
                else
                { y = 1u << 17; x -= 1u << 18; if (x >= 5u << 16) { x -= 5u << 16; y |= 1u << 16; } goto L7; }
            }
            else
            {
                if (x < 1u << 22)
                { y = 1u << 19; x -= 1u << 20; if (x >= 5u << 18) { x -= 5u << 18; y |= 1u << 18; } goto L8; }
                else
                { y = 1u << 21; x -= 1u << 22; if (x >= 5u << 20) { x -= 5u << 20; y |= 1u << 20; } goto L9; }
            }
        }
        else
        {
            if (x < 1u << 28)
            {
                if (x < 1u << 26)
                { y = 1u << 23; x -= 1u << 24; if (x >= 5u << 22) { x -= 5u << 22; y |= 1u << 22; } goto La; }
                else
                { y = 1u << 25; x -= 1u << 26; if (x >= 5u << 24) { x -= 5u << 24; y |= 1u << 24; } goto Lb; }
            }
            else
            {
                if (x < 1u << 30)
                { y = 1u << 27; x -= 1u << 28; if (x >= 5u << 26) { x -= 5u << 26; y |= 1u << 26; } goto Lc; }
                else
                { y = 1u << 29; x -= 1u << 30; if (x >= 5u << 28) { x -= 5u << 28; y |= 1u << 28; } }
            }
        }
    }
    z = y | 1u << 26; y /= 2; if (x >= z) { x -= z; y |= 1u << 26; }
Lc: z = y | 1u << 24; y /= 2; if (x >= z) { x -= z; y |= 1u << 24; }
Lb: z = y | 1u << 22; y /= 2; if (x >= z) { x -= z; y |= 1u << 22; }
La: z = y | 1u << 20; y /= 2; if (x >= z) { x -= z; y |= 1u << 20; }
L9: z = y | 1u << 18; y /= 2; if (x >= z) { x -= z; y |= 1u << 18; }
L8: z = y | 1u << 16; y /= 2; if (x >= z) { x -= z; y |= 1u << 16; }
L7: z = y | 1u << 14; y /= 2; if (x >= z) { x -= z; y |= 1u << 14; }
L6: z = y | 1u << 12; y /= 2; if (x >= z) { x -= z; y |= 1u << 12; }
L5: z = y | 1u << 10; y /= 2; if (x >= z) { x -= z; y |= 1u << 10; }
L4: z = y | 1u << 08; y /= 2; if (x >= z) { x -= z; y |= 1u << 08; }
L3: z = y | 1u << 06; y /= 2; if (x >= z) { x -= z; y |= 1u << 06; }
L2: z = y | 1u << 04; y /= 2; if (x >= z) { x -= z; y |= 1u << 04; }
L1: z = y | 1u << 02; y /= 2; if (x >= z) { x -= z; y |= 1u << 02; }
L0: return x > y ? y / 2 | 1u : y / 2;
}


Answer 13:

使用二进制搜索

public class FindSqrt {

    public static void main(String[] strings) {

        int num = 10000;
        System.out.println(sqrt(num, 0, num));
    }

    private static int sqrt(int num, int min, int max) {
        int middle = (min + max) / 2;
        int x = middle * middle;
        if (x == num) {
            return middle;
        } else if (x < num) {
            return sqrt(num, middle, max);
        } else {
            return sqrt(num, min, middle);
        }
    }
}


Answer 14:

在一个整数的一般的平方根(如2,例如) 只能近似(不是因为与浮点运算的问题,但因为它们是不能被精确计算无理数)。

当然,有些近似是比别人做得更好。 我的意思是,当然,该值是1.732更好的近似为3的平方根,大于1.7

通过该链接您以第一近似,并使用它来计算一个更好的近似给作品的代码中使用的方法。

这就是所谓的牛顿法,并且可以重复计算每一个新的逼近,直到这对你不够准确。

实际上必须有一些方法来决定何时停止重复,否则将永远运行下去。

通常,当近似值之间的差值小于你决定一个值,你会停下来。

编辑:我不认为有可能是一个简单的实现比两个你已经找到。



Answer 15:

逆,因为它的名字说,但有时“足够接近”是“足够接近”; 一个有趣的阅读反正。

Quake3的的快速InvSqrt原产地()



Answer 16:

一个简单的解决方案,可以处理浮子平方根和任意精度使用二进制搜索

编码的红宝石

include Math

def sqroot_precision num, precision
  upper   = num
  lower   = 0
  middle  = (upper + lower)/2.0

  while true do
    diff = middle**2 - num

    return middle if diff.abs <= precision

    if diff > 0
      upper = middle
    else diff < 0
      lower = middle
    end

    middle = (upper + lower)/2.0
  end 
end

puts sqroot_precision 232.3, 0.0000000001


Answer 17:

比方说,我们正在努力寻找的2的平方根,你有1.5的估计。 我们会说一个= 2,X = 1.5。 为了计算更准确的估计,我们将用x分割。 这给出了一个新的值y = 1.333333。 但是,我们不能仅仅以此为我们的下一个估计(为什么不呢?)。 我们需要与以前的估计平均吧。 所以,我们的下一个估计,XX会(X + Y)/ 2,或1.416666。

Double squareRoot(Double a, Double epsilon) {
    Double x = 0d;
    Double y = a;
    Double xx = 0d;

    // Make sure both x and y != 0.
    while ((x != 0d || y != 0d) && y - x > epsilon) {
        xx = (x + y) / 2;

        if (xx * xx >= a) {
            y = xx;
        } else {
            x = xx;
        }
    }

    return xx;
}

Epsilon可确定逼近,如何准确必须这样做。 X它获得的函数应该返回第一近似值,其满足ABS(X * X - A)<ε,其中abs(x)是x的绝对值。

square_root(2, 1e-6)
Output: 1.4142141342163086


Answer 18:

有很好了不少答案,但在这里不用我的这是代码(对我来说)最简单的部分,这里是算法吧。

而在Python 2.7的代码:

from __future__ import division 
val = 81
x = 10
def sqr(data,x):
    temp = x - ( (x**2 - data)/(2*x))
    if temp == x:
        print temp
        return
    else:
        x = temp
        return sqr(data,x)
    #x =temp 
    #sqr(data,x)
sqr(val,x)


Answer 19:

通过内置功能的帮助,计算一个数的平方根

# include"iostream.h"
# include"conio.h"
# include"math.h"
void main()
{
clrscr();
float x;
cout<<"Enter the Number";
cin>>x;

 float squreroot(float);  
 float z=squareroot(x);
 cout<<z;


float squareroot(int x)
    {


 float s;
 s = pow(x,.5)  
 return(s);
 }    


文章来源: Writing your own square root function