suma - Módulo con números negativos en C++

sacar modulo de un número

Question

Esta pregunta ya tiene una respuesta aquí:

• ¿Por qué C ++ genera números negativos cuando se usa el módulo? 3 respuestas

He estado escribiendo un programa para la siguiente relación de recurrencia:

An = 5An-1 - 2An-2  - An-3 + An-4

La salida debe ser el módulo de respuesta 10 ^ 9 + 7 .. Escribí un enfoque de fuerza bruta para este de la siguiente manera ...

long long int t1=5, t2=9, t3=11, t4=13, sum;
while(i--)
{
    sum=((5*t4) - 2*t3 - t2 +t1)%MOD;
    t1=t2;
    t2=t3;
    t3=t4;
    t4=sum;
}
printf("%lld/n", sum);

donde MOD= 10^9 +7 Todo parece ser verdad ... pero obtengo una respuesta negativa para algunos valores ... y debido a este problema, no puedo encontrar la solución correcta ... Por favor, ayuda sobre el lugar correcto para mantener el Modulus

Answer 1

Como han dicho otros, % es solo un operador restante en lugar de mod . Sin embargo, la operación mod / resto se distribuye correctamente a través de relaciones de recurrencia como esta, por lo que si solo ajusta su solución final para que sea positiva, así:

if (sum < 0) { sum = sum + MOD; }

entonces debería obtener la respuesta correcta. La ventaja de hacerlo de esta manera es que introduce una llamada de función menos y / o ramificación por iteración de bucle. (Lo que puede o no puede importar dependiendo de lo inteligente que sea su compilador).

Answer 2

El uso de % por segunda vez en @ sellibitze''s y @ liquidblueocean probablemente las respuestas no serán tan lentas como % tiende a ser en general, ya que se reduce a una resta de b o ninguna. En realidad, déjame comprobar que ...

int main(int argc, char **argv) {
    int a = argc;    //Various tricks to prevent the
    int b = 7;       //compiler from optimising things out.
    int c[10];       //Using g++ 4.8.1
    for (int i = 0; i < 1000111000; ++i)
        c[a % b] = 3;
        //c[a < b ? a : a-b] = 3;
    return a;
}

Alternativamente al comentar la línea con % o la otra línea, obtenemos:

• Con % : 14 segundos

• Con ? : 7 segundos

Así que % no está tan optimizado como sospechaba. Probablemente porque esa optimización agregaría gastos generales.

Por lo tanto, es mejor no usar % dos veces, por razones de rendimiento.

En cambio, como esta respuesta sugiere y explica, haz esto:

int mod(int k, int n) {
    return ((k %= n) < 0) ? k+n : k;
}

Requiere un poco más de trabajo si desea que funcione correctamente también para n negativo , pero eso casi nunca es necesario.

Answer 3

La cosa es que el operador% no es el "operador de módulo" sino el operador "resto de división" con la siguiente igualdad

(a/b)*b + a%b == a    (for b!=0)

Entonces, si su división de enteros se redondea a cero (lo cual es obligatorio desde C99 y C ++ 11, creo), -5/4 será -1 y tenemos

(-5/4)*4 + -5%4 == -5
  -1  *4    -1  == -5

Para obtener un resultado positivo (para la operación de módulo) debe agregar el divisor en caso de que el resto sea negativo o hacer algo como esto:

long mod(long a, long b)
{ return (a%b+b)%b; }

Answer 4

Solo reemplaza % por una función que maneja valores negativos:

long long int mod(long long int a, long long int b) {
    long long int ret = a % b;
    if (ret < 0)
        ret += b;
    return ret;
}

EDIT: Cambió el tipo de datos a long long int .

Answer 5

Todas las respuestas actualmente aquí que tienen una adición única en su fórmula son incorrectas cuando abs (a)> b. Utilice este o similar:

int modulo (int a, int b) { return a >= 0 ? a % b : ( b - abs ( a%b ) ) % b; }