在網上找到的平方根源代碼

我正在尋找一些平方根計算算法，並發現這個源文件。我想嘗試複製它，因爲它看起來很簡單，但我不能將它與一些已知的算法（牛頓，巴比倫...）聯繫起來。你能告訴我這個名字嗎？在網上找到的平方根源代碼

int sqrt(int num) { 
    int op = num; 
    int res = 0; 
    int one = 1 << 30; // The second-to-top bit is set: 1L<<30 for long 

    // "one" starts at the highest power of four <= the argument. 
    while (one > op) 
     one >>= 2; 

    while (one != 0) { 
     if (op >= res + one) { 
      op -= res + one; 
      res += 2 * one; 
     } 
     res >>= 1; 
     one >>= 2; 
    } 
    return res; 
}

來源

2017-07-17 alukard990

它在[維基百科在「數字-toDigit計算」]描述（https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Digit-by-digit_calculation） –

「你能告訴我名字嗎？「我會把它叫做「sqrt」（1073741824）' - > -1而不是預期的32768. – chux

「找到這個源文件」 - >在哪裏？ – chux

作爲@Eugene Sh.參考，這樣做是爲了計算平方根經典的「數字逐位」的方法。在小學教過這樣的事情時，在base 10學習。

OP的代碼也失敗了選擇號碼。 sqrt(1073741824) --> -1而不是預期的32768. 1073741824 == 0x40000000。此外，它失敗了大部分（全部？）值和更大的值。當然OP的sqrt(some_negative)也是一個問題。

候選選項：也here

unsigned isqrt(unsigned num) { 
    unsigned res = 0; 

    // The second-to-top bit is set: 1 << 30 for 32 bits 
    // Needs work to run on unusual platforms where `unsigned` has padding or odd bit width. 
    unsigned bit = 1u << (sizeof(num) * CHAR_BIT - 2); 

    // "bit" starts at the highest power of four <= the argument. 
    while (bit > num) 
    bit >>= 2; 

    while (bit > 0) { 
    if (num >= res + bit) { 
     num -= res + bit; 
     res = (res >> 1) + bit; // Key dif between this and OP's code 
    } else { 
     res >>= 1; 
    } 
    bit >>= 2; 
    } 
    return res; 
}

便攜性更新。 4的最大的力量是需要的。

#include <limits.h> 
// greatest power of 4 <= a power-of-2 minus 1 
#define POW4_LE_POW2M1(n) ( ((n)/2 + 1) >> ((n)%3==0) ) 

unsigned bit = POW4_LE_POW2M1(UINT_MAX);

來源

2017-07-17 16:42:15 chux

在網上找到的平方根源代碼

回答

相關問題