usar - tipos de datos en c++
¿Cuál es la forma correcta de obtener(-1) ^ n? (7)
Muchos algoritmos requieren calcular
(-1)^n
(ambos enteros), generalmente como un factor en una serie.
Es decir, un factor que es
-1
para n impar y
1
para n par.
En un entorno C ++, a menudo se ve:
#include<iostream>
#include<cmath>
int main(){
int n = 13;
std::cout << std::pow(-1, n) << std::endl;
}
¿Qué es mejor o la convención habitual? (o algo mas),
std::pow(-1, n)
std::pow(-1, n%2)
(n%2?-1:1)
(1-2*(n%2)) // (gives incorrect value for negative n)
EDITAR:
Además, el usuario @SeverinPappadeux propuso otra alternativa basada en búsquedas de matriz (¿globales?). Mi versión es:
const int res[] {-1, 1, -1}; // three elements are needed for negative modulo results
const int* const m1pow = res + 1;
...
m1pow[n%2]
Esto probablemente no va a resolver la pregunta, pero al usar el código emitido podemos descartar algunas opciones.
Primero sin optimización, los contendientes finales son:
1 - ((n & 1) << 1);
(7 operaciones, sin acceso a memoria)
mov eax, DWORD PTR [rbp-20]
add eax, eax
and eax, 2
mov edx, 1
sub edx, eax
mov eax, edx
mov DWORD PTR [rbp-16], eax
y
retvals[n&1];
(5 operaciones, memoria - ¿registros? - acceso)
mov eax, DWORD PTR [rbp-20]
and eax, 1
cdqe
mov eax, DWORD PTR main::retvals[0+rax*4]
mov DWORD PTR [rbp-8], eax
Ahora con optimización (-O3)
1 - ((n & 1) << 1);
(4 operaciones, sin acceso a memoria)
add edx, edx
mov ebp, 1
and edx, 2
sub ebp, edx
.
retvals[n&1];
(4 operaciones, memoria - ¿registros? - acceso)
mov eax, edx
and eax, 1
movsx rcx, eax
mov r12d, DWORD PTR main::retvals[0+rcx*4]
.
n%2?-1:1;
(4 operaciones, sin acceso a memoria)
cmp eax, 1
sbb ebx, ebx
and ebx, 2
sub ebx, 1
La prueba está here . Tuve algunas acrobacias para tener un código significativo que no elude las operaciones por completo.
Conclusión (por ahora)
Entonces, al final, depende del nivel de optimización y expresividad:
-
1 - ((n & 1) << 1);siempre es bueno pero no muy expresivo. -
retvals[n&1];paga un precio por el acceso a la memoria. -
n%2?-1:1;es expresivo y bueno pero solo con optimización.
Muchos algoritmos requieren calcular (-1) ^ n (ambos enteros), generalmente como un factor en una serie. Es decir, un factor que es -1 para n impar y 1 para n par.
Considere evaluar la serie como una función de -x en su lugar.
Bueno, si estamos realizando el cálculo en una serie, ¿por qué no manejar el cálculo en un bucle positivo y un bucle negativo, omitiendo la evaluación por completo?
La expansión de la serie Taylor para aproximar el logaritmo natural de (1 + x) es un ejemplo perfecto de este tipo de problema. Cada término tiene (-1) ^ (n + 1) o (1) ^ (n-1). No hay necesidad de calcular este factor. Puede "cortar" el problema ejecutando 1 bucle por cada dos términos, o dos bucles, uno para los términos impares y otro para los términos pares.
Por supuesto, dado que el cálculo, por su naturaleza, es uno sobre el dominio de los números reales, de todos modos utilizará un procesador de coma flotante para evaluar los términos individuales. Una vez que haya decidido hacer eso, debe usar la implementación de la biblioteca para el logaritmo natural. Pero si, por alguna razón, decide no hacerlo, sin duda será más rápido, pero no mucho, no perder los ciclos calculando el valor de -1 a la enésima potencia.
Quizás cada uno incluso se puede hacer en hilos separados. Quizás el problema pueda ser vectorizado, incluso.
En primer lugar, la prueba isOdd más rápida que conozco (en un método en línea)
/**
* Return true if the value is odd
* @value the value to check
*/
inline bool isOdd(int value)
{
return (value & 1);
}
Luego, utilice esta prueba para devolver -1 si es impar, 1 de lo contrario (que es la salida real de (-1) ^ N)
/**
* Return the computation of (-1)^N
* @n the N factor
*/
inline int minusOneToN(int n)
{
return isOdd(n)?-1:1;
}
Por último, como se sugiere @Guvante, puede ahorrar una multiplicación simplemente volteando el signo de un valor (evitando usar la función minusOneToN)
/**
* Example of the general usage. Avoids a useless multiplication
* @value The value to flip if it is odd
*/
inline int flipSignIfOdd(int value)
{
return isOdd(value)?-value:value;
}
Por lo general, en realidad no calcula
(-1)^n
, sino que rastrea el signo actual (como un número que es
-1
o
1
) y lo
sign = -sign
en cada operación (
sign = -sign
), haga esto mientras maneja su
n
en orden y obtendrás el mismo resultado.
EDITAR: tenga en cuenta que parte de la razón por la que recomiendo esto se debe a que rara vez hay un valor semántico en realidad es la representación
(-1)^n
es simplemente un método conveniente para voltear el signo entre iteraciones.
Puede usar
(n & 1)
lugar de
n % 2
y
<< 1
lugar de
* 2
si desea ser súper pedante, quiero decir, optimizado.
Entonces, la forma más rápida de calcular en un procesador 8086 es:
1 - ((n & 1) << 1)
Solo quiero aclarar de dónde viene esta respuesta.
El póster original alfC hizo un excelente trabajo al publicar muchas formas diferentes de calcular (-1) ^ n algunas son más rápidas que otras.
Hoy en día, con los procesadores tan rápidos como son y la optimización de los compiladores tan buenos como son,
generalmente
valoramos la legibilidad sobre las mejoras leves (incluso insignificantes) de afeitar unos pocos ciclos de CPU de una operación.
Hubo un tiempo en que los compiladores de un solo paso gobernaban la tierra y las operaciones de MUL eran nuevas y decadentes;
en aquellos días un poder de operación 2 era una invitación para la optimización gratuita.
Qué pasa
(1 - (n%2)) - (n%2)
n%2
probablemente se computará solo una vez
ACTUALIZAR
En realidad, la forma más simple y correcta sería usar table
const int res[] {-1, 1, -1};
return res[n%2 + 1];
Si necesita velocidad, aquí va ...
int inline minus_1_pow(int n) {
static const int retvals[] {1, -1};
return retvals[n&1];
}
El compilador de Visual C ++ con optimización convertida a 11 compila esto en dos instrucciones de máquina, ninguna de las cuales es una rama. También optimiza la matriz de retvals, por lo que no se pierde memoria caché.