按位整數立方根算法

下面是一個簡單的方法來計算的整數平方根：按位整數立方根算法

int isqrt(int num) 
{ 
    int root=0; 
    int b = 0x8000; 
    int a=0, c=0; 

    while (b) { 
     c = a|b; 

     if (c*c <= num) 
      a |= b; 

     b >>= 1; 
    }  
}

巧（感謝Wikipedia），這可以優化這樣的：

int sqrt(short num) 
{ 
    int op = num; 
    int res = 0; 
    int one = 1 << 30; 

    while (one > op) 
     one >>= 2; 

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

我的問題：可以爲整數立方根編寫一個類似優化的算法嗎？（這是在一個小型微控制器上運行，它不喜歡乘法運算）

來源

2011-07-10 Rocketmagnet

不是我所知道的，但可以通過添加7,19,37,61等來產生連續整數的第三冪，並且可以通過添加12,18,24,30,36等來獲得這些數字。它並不是特別聰明或者快速，但是考慮到2^32的整數立方根仍然只有1625，所以它不應該進行很多次迭代（所有這些迭代都由一對加法和一個比較組成，沒有細節）。編輯：所以原來有一種方法。很高興知道！ – harold

根據this SO問題和答案標記，從黑客的喜悅本書中，你可以找到這個實現：

int icbrt2(unsigned x) { 
    int s; 
    unsigned y, b, y2; 

    y2 = 0; 
    y = 0; 
    for (s = 30; s >= 0; s = s - 3) { 
     y2 = 4*y2; 
     y = 2*y; 
     b = (3*(y2 + y) + 1) << s; 
     if (x >= b) { 
     x = x - b; 
     y2 = y2 + 2*y + 1; 
     y = y + 1; 
     } 
    } 
    return y; 
}

來源

2011-07-10 13:29:31 Jack

是的，算法可以擴展到立方根，即使沒有乘法。

看到這個代碼：http://www.hackersdelight.org/HDcode/icbrt.c.txt

並考慮買的書黑客的喜悅，他的代碼來自。如果你一年要解決一次這樣的問題，你一定要閱讀！

來源

2011-07-10 13:28:58

這是一種（極端）C＃優化了黑客的喜悅代碼的版本，如提及由他人。

僅供參考（在我的電腦上）：Math.Sqrt大約需要35 ns，cbrt < 15 ns。

使用小數字的乘法，但很容易用換檔替換它們，並且增加了。例如最大multipication（最後一行）：「12 * Z」 ==> 「（Z < < 3）+（Z < < 2）」

這是難以判斷代碼的大小是否是可接受爲一個小型微控制器。

第一步：二進制搜索，則「if」語句，大的值（> = 1U < < 24）相對更快發現，小的值（< 64）在搜索期間進行處理。

第二步：跳到展開循環中的「標籤」。

private static uint cbrt(uint x) 
{ 
    uint y = 2, z = 4, b = 0; 
    if (x < 1u << 24) 
     if (x < 1u << 12) 
      if (x < 1u << 06) 
       if (x < 1u << 03) 
        return x == 0u ? 0u : 1u; 
       else 
        return x < 27u ? 2u : 3u; 
      else 
       if (x < 1u << 09) goto L8; else goto L7; 
     else 
      if (x < 1u << 18) 
       if (x < 1u << 15) goto L6; else goto L5; 
      else 
       if (x < 1u << 21) goto L4; else goto L3; 
    else 
     if (x >= 1u << 30) goto L0; 
     else 
      if (x < 1u << 27) goto L2; else goto L1; 

L0: x -= 1u << 30; if (x >= 19u << 27) 
    { x -= 19u << 27; z = 9; y = 3; } goto M0; 
L1: x -= 1u << 27; if (x >= 19u << 24) 
    { x -= 19u << 24; z = 9; y = 3; } goto M1; 
L2: x -= 1u << 24; if (x >= 19u << 21) 
    { x -= 19u << 21; z = 9; y = 3; } goto M2; 
L3: x -= 1u << 21; if (x >= 19u << 18) 
    { x -= 19u << 18; z = 9; y = 3; } goto M3; 
L4: x -= 1u << 18; if (x >= 19u << 15) 
    { x -= 19u << 15; z = 9; y = 3; } goto M4; 
L5: x -= 1u << 15; if (x >= 19u << 12) 
    { x -= 19u << 12; z = 9; y = 3; } goto M5; 
L6: x -= 1u << 12; if (x >= 19u << 09) 
    { x -= 19u << 09; z = 9; y = 3; } goto M6; 
L7: x -= 1u << 09; if (x >= 19u << 06) 
    { x -= 19u << 06; z = 9; y = 3; } goto M7; 
L8: x -= 1u << 06; if (x >= 19u << 03) 
    { x -= 19u << 03; z = 9; y = 3; } goto M8; 

M0: y *= 2; z *= 4; b = 3 * y + 3 * z + 1 << 24; 
    if (x >= b) { x -= b; z += 2 * y + 1; y += 1; } 
M1: y *= 2; z *= 4; b = 3 * y + 3 * z + 1 << 21; 
    if (x >= b) { x -= b; z += 2 * y + 1; y += 1; } 
M2: y *= 2; z *= 4; b = 3 * y + 3 * z + 1 << 18; 
    if (x >= b) { x -= b; z += 2 * y + 1; y += 1; } 
M3: y *= 2; z *= 4; b = 3 * y + 3 * z + 1 << 15; 
    if (x >= b) { x -= b; z += 2 * y + 1; y += 1; } 
M4: y *= 2; z *= 4; b = 3 * y + 3 * z + 1 << 12; 
    if (x >= b) { x -= b; z += 2 * y + 1; y += 1; } 
M5: y *= 2; z *= 4; b = 3 * y + 3 * z + 1 << 09; 
    if (x >= b) { x -= b; z += 2 * y + 1; y += 1; } 
M6: y *= 2; z *= 4; b = 3 * y + 3 * z + 1 << 06; 
    if (x >= b) { x -= b; z += 2 * y + 1; y += 1; } 
M7: y *= 2; z *= 4; b = 3 * y + 3 * z + 1 << 03; 
    if (x >= b) { x -= b; z += 2 * y + 1; y += 1; } 
M8: y *= 2; return x <= 3 * y + 12 * z ? y : y + 1; 
}

來源

2013-09-26 12:13:09

我認爲這在32位微控制器上會非常快。 – Rocketmagnet

按位整數立方根算法

回答

相關問題