¿Cuál es la forma más rápida de obtener el valor absoluto de un número

Question

¿Cuál es la forma más rápida de implementar una operación que devuelve el valor absoluto de un número?

x=root(x²) 

o

if !isPositive(x): 
    x=x*(-1) 

En realidad esta pregunta puede ser traducido como, qué tan rápido es un if (y por favor).

Mis profesores de programación universitaria siempre me dijeron que evite if s porque son extremadamente lentos, pero siempre olvidé preguntarme qué tan lento y por qué. ¿Alguien aquí lo sabe?

Answer 1

Las condiciones son más lentas que las operaciones aritméticas simples, pero mucho, mucho más rápido que algo tan tonto como calcular la raíz cuadrada.

Reglas de oro de mis días de montaje:

• entero o bit a bit op: 1 ciclo
• de punto flotante de añadir/sub/mul: 4 ciclos
• de coma flotante Div: ~ 30 ciclos
• de coma flotante exponenciación: ~ 200 ciclos
• de coma flotante sqrt: ~ 60 ciclos, dependiendo de la aplicación
• rama condicional: avg.10 ciclos, mejor si bien pronosticado, mucho peor si mispredicted

Answer 2

Ugh, ¿tus profesores realmente te dijeron eso? La regla que sigue la mayoría de las personas es hacer que su código sea legible primero, y luego modificar cualquier problema de rendimiento después de que se demuestre que realmente son problemas. 99.999% de las veces nunca verá un problema de rendimiento porque usó demasiadas declaraciones if. Knuth said it best, "la optimización prematura es la raíz de todo mal".

Answer 3

La operación de módulo se usa para encontrar un resto, quiere decir valor absoluto. Modifiqué la pregunta porque debería ser si! Pos (x) luego x = x * -1. (no faltaba)

No me preocuparía la eficacia de una sentencia if. En cambio, concéntrese en la legibilidad de su código. Si identifica que hay un problema de eficiencia, entonces concéntrese en perfilar su código para encontrar cuellos de botella reales.

Si desea estar atento a la eficacia mientras codifica, solo debe preocuparse por la gran complejidad de sus algoritmos.

Si las declaraciones son muy eficientes, evalúa cualquier expresión y luego simplemente cambia el program counter en función de esa condición. El contador del programa almacena la dirección de la próxima instrucción que se ejecutará.

Mulitplication por -1 y comprobar si un valor es mayor que 0 ambos se pueden reducir a una sola instrucción de ensamblaje.

Encontrar la raíz de un número y cuadrar ese número primero es definitivamente más operaciones que si con una negación.

Answer 4

La variante if es casi seguro que sea cegador rápido en comparación con la raíz cuadrada, ya que normalmente se traduce en una instrucción de salto condicional a nivel de código máquina (después de la evaluación de la expresión, que puede ser compleja, pero no en este caso, ya que es una verificación simple para menos de 0).

Tomando la raíz cuadrada de un número es probable que sea mucho más lento (el método de Newton, por ejemplo, podría utilizar muchos muchosif declaraciones a nivel de código máquina).

La posible fuente de confusión es el hecho de que if conduce invariablemente a cambiar el puntero de instrucción de una manera no secuencial. Esto puede ralentizar a los procesadores que preseleccionan las instrucciones en una canalización ya que tienen que volver a llenar la interconexión cuando la dirección cambia inesperadamente.

Sin embargo, el costo de eso sería minúsculo en comparación con la realización de una operación de raíz cuadrada en comparación con un simple check-and-negate.

Answer 5

Calcular la raíz cuadrada es probablemente una de las peores cosas que podrías hacer porque es muy lenta. Usualmente hay una función de biblioteca para hacer esto; algo así como Math.Abs ​​(). Multiplicar con -1 también es innecesario; solo devuelve -x. Entonces una buena solución sería la siguiente.

(x >= 0) ? x : -x 

El compilador probablemente optimice esto en una sola instrucción. Las condiciones pueden ser bastante costosas en los procesadores modernos debido a la larga ejecución de las tuberías: los cálculos deben descartarse si una derivación se omitió y el procesador comenzó a ejecutar las instrucciones desde la ruta de código incorrecta. Pero debido a la optimización del compilador mencionada, no es necesario que se preocupe en este caso.

Answer 6

El tiempo necesario para hacer una raíz cuadrada es mucho mayor que el tiempo necesario para hacer un condicional. Si te han enseñado a evitar condicionales porque son lentos, entonces has sido mal informado. Son mucho más lentas que las operaciones triviales, como sumar o restar enteros o cambios de bit, por lo que los bucles de desenrollado pueden ser beneficiosos solo si se realizan operaciones tan triviales. Pero en el gran esquema de las cosas, los condicionales son buenos y rápidos, no malos y lentos. Hacer algo tan complicado como llamar a una función o calcular una raíz cuadrada para evitar una declaración condicional es una locura.

Además, en lugar de (x = x * -1) ¿por qué no hacer (x = 0 - x)? Quizás el compilador los optimice de la misma manera, ¿pero no es el segundo más simple de todos modos?

Answer 7

¿Está utilizando el ensamblaje 8086? ;-)

   ; abs value of AX 
    cwd   ; replicate the high bit into DX 
    xor ax, dx ; take 1's complement if negative; no change if positive 
    sub ax, dx ; AX is 2's complement if it was negative The standard 
       : absolute value method works on any register but is much 
       ; slower: 

    or bx, bx ; see if number is negative 
    jge notneg ; if it is negative... 
    neg bx  ; ...make it positive 
notneg:   ; jump to here if positive 

(flagrante stolen)

Answer 8

Hay un gran truco para calcular el valor absoluto de un número entero 2s-complemento sin necesidad de utilizar una sentencia if. La teoría dice que si el valor es negativo, quiere alternar los bits y agregar uno; de lo contrario, quiere pasar los bits tal como están. Un XOR 1 pasa a activar A y A XOR 0 pasa a dejar intacto A. Entonces quiere hacer algo como esto:

uint32_t temp = value >> 31;  // make a mask of the sign bit 
    value ^= temp;     // toggle the bits if value is negative 
    value += temp & 1;    // add one if value was negative 

En principio, puede hacerlo en solo tres instrucciones de montaje (sin una derivación). Y le gustaría pensar que la función abs() que obtiene con math.h lo hace de manera óptima.

Sin ramas == mejor rendimiento. Contrariamente a la respuesta de @ paxdiablo anterior, esto realmente importa en las tuberías profundas donde cuantas más ramas tenga en su código, más probabilidades tendrá de que su pronosticador de rama se equivoque y tenga que retroceder, etc. Si evita la bifurcación donde posible, las cosas seguirán moviéndose a todo gas en tu núcleo :).

Answer 9

Para completar, aquí es una manera de hacerlo por IEEE flota en sistemas x86 en C++:

*(reinterpret_cast<uint32_t*>(&foo)) &= 0xffffffff >> 1; 

Answer 10

Si simplemente comparando los valores absolutos de dos números (por ejemplo, no es necesario que el valor absoluto de cualquiera de ellas después de la comparación), entonces simplemente cuadre ambos valores para que ambos sean positivos (elimine el signo de cada valor), el cuadrado más grande será mayor que el cuadrado más pequeño.

Answer 11

Lo que es más rápido depende mucho del compilador y de la CPU a la que se dirige. En la mayoría de las CPU y todos los compiladores x = (x> = 0)? x: -x; es la manera más rápida de obtener un valor absoluto, pero de hecho, a menudo las funciones estándar ya ofrecen esta solución (por ejemplo, fabs()). Se compila en comparación seguido de instrucción de asignación condicional (CMOV), no en salto condicional. Sin embargo, algunas plataformas carecen de esa instrucción. Aunque, el compilador Intel (pero no Microsoft o GCC) convertiría automáticamente if() en una asignación condicional, e incluso trataría de optimizar ciclos (si es posible).

El código de bifurcación en general es más lento que la asignación condicional, si la CPU usa predicción estadística. if() podría ser más lento en promedio si la operación se repite varias veces y el resultado de la condición cambia constantemente. CPUs como Intel, comenzarían a calcular ambas ramas, y dejarían caer el inválido, en el caso de cuerpos if() grandes o una gran cantidad de ciclos que podrían ser críticos.

sqr() y sqrt() en las CPU Intel modernas son instrucciones incorporadas simples y no son lentas, pero son imprecisas, y cargar registros también llevaría tiempo.

pregunta relacionada: Why is a CPU branch instruction slow?

Lo más probable, profesor quería estudiante para hacer la investigación sobre este asunto, que es semi-provocativa pregunta \ tarea que hacer sólo el bien, si el estudiante aprendería pensar de manera independiente y buscar fuentes adicionales.

Answer 12

¿Cuál es la manera más rápida para obtener el valor absoluto de un número

creo que la respuesta "correcta" no es en realidad aquí. La manera más rápida de obtener el número absoluto es probablemente usar Intel Intrinsic. Vea https://software.intel.com/sites/landingpage/IntrinsicsGuide/ y busque 'vpabs' (u otro intrínseco que haga el trabajo para su CPU). Estoy bastante seguro de que superará a todas las otras soluciones aquí.

Si no te gustan los intrínsecos (o no puedes usarlos o ...), es posible que desees comprobar si el compilador es lo suficientemente inteligente como para averiguar si una llamada al 'valor absoluto nativo' (std::abs en C++ o Math.Abs(x) en C#) cambiará automágicamente a lo intrínseco, básicamente eso implica mirar el código desensamblado (compilado). Si está en un JIT, asegúrese de que las optimizaciones de JIT no estén deshabilitadas.

Si eso tampoco le da las instrucciones optimizadas, puede utilizar el método descrito aquí: https://graphics.stanford.edu/~seander/bithacks.html#IntegerAbs.

Answer 13

que estoy haciendo un poco de programación gráficos retro en C para 8088/8086 y llamando abs() es mucho tiempo por lo que he reemplazado con:

/* assuming 'i' is int; this WILL NOT WORK on floating point */ 
if (i < 0) { 
    i = ~i + 1; 
} 

La razón de que esto es más rápido se debe a que en esencia operaciones al CALL en el montaje para JNE. Llamar a un método cambia un par de registros, empuja varios más, empuja los argumentos a la pila y puede vaciar la cola de captación previa. Además, estas acciones deben invertirse al final de la función y todo esto es muy costoso para la CPU.