按位整数立方根算法

下面是一个简单的方法来计算的整数平方根：按位整数立方根算法

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

按位整数立方根算法

回答

相关问题