bit a bit algoritmo de raíz cúbica número entero

Question

He aquí una forma sencilla de calcular un número entero de raíz cuadrada:

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; 
    }  
} 

Genialmente (gracias Wikipedia), esto se puede optimizar de esta manera:

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; 
} 

Mi pregunta: ¿Se puede escribir un algoritmo optimizado de forma similar para una raíz cúbica entera? (Esto se va a ejecutar en un microcontrolador pequeño que prefiere no hacer multiplicaciones)

Answer 1

Según this SO pregunta y la respuesta marcada, del libro deleite del pirata informático puede encontrar esta aplicación:

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; 
} 

Answer 2

Sí, el algoritmo se puede extender a raíces de cubo, incluso sin multiplicaciones.

ver este código: http://www.hackersdelight.org/HDcode/icbrt.c.txt

y considerar al comprar el libro Hackers Delight código donde proviene. ¡Si tiene que resolver tales problemas más de una vez al año, definitivamente debería leerlo!

Answer 3

Ésta es una (extremo) C# versión optimizada del código deleite del Hacker, como se ha mencionado por otros.

Como referencia (en mi pc): Math.Sqrt tarda aproximadamente 35 ns, crtrt < 15 ns.

Se usan multiplicaciones por números pequeños, pero es fácil reemplazarlas por cambios y agrega . Por ejemplo, la mayor multipication (última línea): "12 * z" ==> "(z < < 3) + (z < < 2)"

Es difícil juzgar si el tamaño del código es aceptable para un microcontrolador pequeño

Primer paso: Una búsqueda binaria, las sentencias "if", los valores grandes (> = 1u < < 24) se encuentran relativamente más rápido, valores pequeños (< 64) se manejan durante la búsqueda.

Segundo paso: Un salto en el bucle desenrollado, las "etiquetas".

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; 
}