Cómo codificar un operador modulo ( % ) en C/C++ / Obj-C que maneja números negativos

Aquí hay una función C que maneja valores enteros O fraccionarios positivos O negativos para AMBOS OPERANDOS

#include <math.h>
float mod(float a, float N) {return a - N*floor(a/N);} //return in range [0, N)

Esta es sin duda la solución más elegante desde un punto de vista matemático. Sin embargo, no estoy seguro de si es robusto en el manejo de enteros. A veces los errores de coma flotante se arrastran al convertir int - > fp - > int.

Estoy usando este código para s no-int, y una función separada para int.

NOTA: necesidad de atrapar N=0 !

Código del probador:

#include <math.h>

float mod(float a, float N)
{
    float ret = a - N * floor (a / N);

    printf("%f.1 mod %f.1 = %f.1 \n", a, N, ret);

    return ret;
}

int main (char* argc, char** argv)
{
    printf ("fmodf(-10.2, 2.0) = %f.1  == FAIL! \n\n", x);

    float x;
    x = mod(10.2f, 2.0f);
    x = mod(10.2f, -2.0f);
    x = mod(-10.2f, 2.0f);
    x = mod(-10.2f, -2.0f);

    return 0;
}

(Nota: Puedes compilarlo y ejecutarlo directamente desde el CodePad: http://codepad.org/UOgEqAMA )

Salida:

Fmodf(-10.2, 2.0) = -0.20 == FAIL!

10.2 mod 2.0 = 0.2
10,2 mod -2,0 = -1,8
-10,2 mod 2,0 = 1,8
-10.2 mod -2.0 = -0.2

Acabo de notar que Bjarne Stroustrup etiqueta % como el operador remainder, no el operador modulo.

Apostaría a que este es su nombre formal en las especificaciones de ANSI C & C++, y que el abuso de terminología se ha colado. ¿Alguien sabe esto a ciencia cierta?

Pero si este es el caso, entonces la función fmodf() de C (y probablemente otras) son muy engañosas. deben etiquetarse como fremf (), etc

Para enteros esto es simple. Solo hazlo

(((x < 0) ? ((x % N) + N) : x) % N)

Donde estoy suponiendo que N es positivo y representable en el tipo de x. Su compilador favorito debería ser capaz de optimizar esto, de modo que termine en una sola operación mod en assembler.

La mejor solución 1para un matemático es usar Python.

La sobrecarga del operador de C++ tiene poco que ver con esto. No puede sobrecargar los operadores para los tipos incorporados. Lo que quieres es simplemente una función. Por supuesto, puede usar plantillas de C++ para implementar esa función para todos los tipos relevantes con solo 1 pieza de código.

La biblioteca estándar de C proporciona fmod, si recuerdo el nombre correctamente, para los tipos de coma flotante.

Para enteros puede definir una plantilla de función C++ que siempre devuelve el resto no negativo (correspondiente a la división euclidiana) como ...

#include <stdlib.h>  // abs

template< class Integer >
auto mod( Integer a, Integer b )
    -> Integer
{
    Integer const r = a%b;
    return (r < 0? r + abs( b ) : r);
}

... y simplemente escribe mod(a, b) en lugar de a%b.

Aquí el tipo Integer debe ser un tipo entero con signo.

Si desea el comportamiento matemático común donde el signo del resto es el mismo que el signo del divisor, entonces puede hacer, por ejemplo,

template< class Integer >
auto floor_div( Integer const a, Integer const b )
    -> Integer
{
    bool const a_is_negative = (a < 0);
    bool const b_is_negative = (b < 0);
    bool const change_sign  = (a_is_negative != b_is_negative);

    Integer const abs_b         = abs( b );
    Integer const abs_a_plus    = abs( a ) + (change_sign? abs_b - 1 : 0);

    Integer const quot = abs_a_plus / abs_b;
    return (change_sign? -quot : quot);
}

template< class Integer >
auto floor_mod( Integer const a, Integer const b )
    -> Integer
{ return a - b*floor_div( a, b ); }

With con la misma restricción en Integer, que es un tipo firmado.

^{1 Porque la división entera de Python rondas hacia infinito negativo.}

La función general más simple para encontrar el módulo positivo sería esta- Funcionaría tanto en valores positivos como negativos de x.

int modulo(int x,int N){
    return (x % N + N) %N;
}

Oh, odio % design para esto también....

Puede convertir dividendo a sin signo de una manera como:

unsigned int offset = (-INT_MIN) - (-INT_MIN)%divider

result = (offset + dividend) % divider

Donde el desplazamiento es el más cercano a (-INT_MIN) múltiplo del módulo, por lo que sumarlo y restarlo no cambiará el módulo. Tenga en cuenta que tiene tipo sin signo y el resultado será entero. Desafortunadamente no puede convertir correctamente los valores INT_MIN...(- offset-1) ya que causan desbordamiento arifmético. Pero este método tiene ventaja de solo una aritmética adicional por operación (y no condicionales) cuando se trabaja con divisor constante, por lo que es utilizable en aplicaciones similares a DSP.

Hay un caso especial, donde el divisor es 2^N (potencia entera de dos), para lo cual el módulo se puede calcular usando aritmética simple y lógica de bits como

dividend&(divider-1)

Por ejemplo

x mod 2 = x & 1
x mod 4 = x & 3
x mod 8 = x & 7
x mod 16 = x & 15

La forma más común y menos complicada es obtener modulo usando esta función (solo funciona con divisor positivo):

int mod(int x, int y) {
    int r = x%y;
    return r<0?r+y:r;
}

Este solo resultado correcto si es negativo.

También tú truco de mayo:

(p % q + q) % q

Es muy corto pero usa dos %-s que son comúnmente lentos.

Creo que otra solución a este problema sería usar variables de tipo long en lugar de int.

Estaba trabajando en algún código donde el operador % estaba devolviendo un valor negativo lo que causó algunos problemas( para generar variables aleatorias uniformes en [0,1] realmente no desea números negativos:)), pero después de cambiar las variables a type long, todo se estaba ejecutando sin problemas y los resultados coincidían con los que estaba obteniendo al ejecutar el mismo código en python (importante para mí, ya que quería ser capaz de generar los mismos números "aleatorios" a través de varias plataformas.

/* Warning: macro mod evaluates its arguments' side effects multiple times. */
#define mod(r,m) (((r) % (m)) + ((r)<0)?(m):0)

... o simplemente acostúmbrate a conseguir cualquier representante para la clase de equivalencia.

Aquí hay una nueva respuesta a una vieja pregunta, basada en este documento de investigación de Microsoft y las referencias en el mismo.

Tenga en cuenta que a partir de C11 y C++11 en adelante, la semántica de divse ha convertido en truncamiento hacia cero (véase [expr.mul]/4). Además, para D dividido por d, C++11 garantiza lo siguiente sobre el cociente qT y el resto rT

auto const qT = D / d;
auto const rT = D % d;
assert(D == d * qT + rT);
assert(abs(rT) < abs(d));
assert(signum(rT) == signum(D));

Donde signum se asigna a -1, 0, +1, dependiendo de si su argumento es que 0 (ver esto Q & A para el código fuente).

Con la división truncada, el signo del resto es igual al signo del dividendo D, es decir, -1 % 8 == -1. C++11 también proporciona una función std::div que devuelve una estructura con miembros quot y rem de acuerdo con la división truncada.

Hay otras definiciones posibles, por ejemplo, la llamada división floored se puede definir en términos de la división truncada incorporada

auto const I = signum(rT) == -signum(d) ? 1 : 0;
auto const qF = qT - I;
auto const rF = rT + I * d;
assert(D == d * qF + rF);
assert(abs(rF) < abs(d));
assert(signum(rF) == signum(d));

Con división de piso, el signo del resto es igual al signo del divisor d. En idiomas como Haskell y Oberon, hay operadores integrados para la división de pisos. En C++, necesitarías escribir una función usando las definiciones anteriores.

Otra forma es La división euclidiana , que también se puede definir en términos de la división truncada incorporada

auto const I = rT >= 0 ? 0 : (d > 0 ? 1 : -1);
auto const qE = qT - I;
auto const rE = rT + I * d;
assert(D == d * qE + rE);
assert(abs(rE) < abs(d));
assert(signum(rE) != -1);

Con la división euclidiana, el signo del resto es siempre positivo.

Plantilla de ejemplo para C++

template< class T >
T mod( T a, T b )
{
    T const r = a%b;
    return ((r!=0)&&((r^b)<0) ? r + b : r);
}

Con esta plantilla, el resto devuelto será cero o tendrá el mismo signo que el divisor (denominador) (el equivalente del redondeo hacia infinito negativo), en lugar del comportamiento de C++ de que el resto sea cero o tenga el mismo signo que el dividendo (numerador) (el equivalente del redondeo hacia cero).

define  MOD(a, b)       ((((a)%(b))+(b))%(b))

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

Esta solución (para usar cuando mod es positiva) evita tomar operaciones de división o resto negativas todas juntas:

int core_modulus(int val, int mod)
{
    if(val>=0)
        return val % mod;
    else
        return val + mod * ((mod - val - 1)/mod);
}

Yo haría:

((-1)+8) % 8 

Esto agrega el último número al primero antes de hacer el módulo dando 7 como se desee. Esto debería funcionar para cualquier número hasta -8. Donde dice -9 añádase 2 * 8.