¿Sumas y restas modulares de desbordamiento seguro en C?

Question

Estoy implementando un algoritmo en C que necesita hacer adiciones y restas de forma rápida en enteros sin signo y puede manejar condiciones de desbordamiento correctamente. Esto es lo que tengo ahora (que funciona):

/* a and/or b may be greater than m */ 
uint32_t modadd_32(uint32_t a, uint32_t b, uint32_t m) { 
    uint32_t tmp; 
    if (b <= UINT32_MAX - a) 
     return (a + b) % m; 

    if (m <= (UINT32_MAX>>1)) 
     return ((a % m) + (b % m)) % m; 

    tmp = a + b; 
    if (tmp > (uint32_t)(m * 2)) // m*2 must be truncated before compare 
     tmp -= m; 
    tmp -= m; 
    return tmp % m; 
} 

/* a and/or b may be greater than m */ 
uint32_t modsub_32(uint32_t a, uint32_t b, uint32_t m) { 
    uint32_t tmp; 
    if (a >= b) 
     return (a - b) % m; 

    tmp = (m - ((b - a) % m)); /* results in m when 0 is needed */ 
    if (tmp == m) 
     return 0; 
    return tmp; 
} 

¿Alguien sabe de un mejor algoritmo? Las bibliotecas que he encontrado que hacen aritmética modular parecen ser para grandes números de precisión arbitraria que es demasiado exagerado.

Editar: Quiero que esto funcione bien en una máquina de 32 bits. Además, mis funciones existentes se convierten trivialmente para trabajar en otros tamaños de enteros sin signo, una propiedad que sería bueno retener.

Answer 1

Las operaciones modulares suelen suponer que a y b son menores que m. Esto permite que los algoritmos más simples:

umod_t sub_mod(umod_t a, umod_t b, umod_t m) 
{ 
    if (a>=b) 
    return a - b; 
    else 
    return m - b + a; 
} 

umod_t add_mod(umod_t a, umod_t b, umod_t m) 
{ 
    if (0==b) return a; 

    // return sub_mod(a, m-b, m); 
    b = m - b; 
    if (a>=b) 
    return a - b; 
    else 
    return m - b + a; 
} 

Fuente: Matters Computational, capítulo 39.1.

Answer 2

Me gustaría hacer la aritmética en uint32_t si cabe y en uint64_t de lo contrario.

uint32_t modadd_32(uint32_t a, uint32_t b, uint32_t m) { 
    if (b <= UINT32_MAX - a) 
     return (a + b) % m; 
    else 
     return ((uint64_t)a + b) % m; 
} 

en una arquitectura de 64 bits con los tipos enteros, esto debería ser casi ninguna sobrecarga, incluso se podría pensar en simplemente hacer todo en uint64_t. En arquitecturas donde uint64_t se sintetiza , deje que el compilador decida qué es lo que cree que es mejor, y luego mire en el ensamblador generado y mida para ver si esto es satisfactorio.

Answer 3

desbordamiento de fallos Además modular

Primera establece que a<m y b<m con el habitual % m.

Agregar actualización a y b.

caso de a (o b) superior a la suma uintN_t, entonces la suma matemáticamente era un uintN_t desbordamiento y resta de m será "mod" la suma matemáticamente en el rango de uintN_t.

Si la suma excede m, entonces como en el paso anterior, una sola resta de m "modificará" la suma.

uintN_t modadd_N(uintN_t a, uintN_t b, uintN_t m) { 
    // may omit these 2 steps if a < b and a < m are known before the call. 
    a %= m; 
    b %= m; 

    uintN_t sum = a + b; 
    if (sum >= m || sum < a) { 
    sum -= m; 
    } 
    return sum; 
} 

Absolutamente simple en el extremo.

---

desbordamiento de fallos sustracción modular

Variación sobre @Evgeny Kluev buena respuesta.

uintN_t modsub_N(uintN_t a, uintN_t b, uintN_t m) { 
    // may omit these 2 steps if a < b and a < m are known before the call. 
    a %= m; 
    b %= m; 

    uintN_t diff = a - b; 
    if (a < b) { 
    diff += m; 
    } 
    return diff; 
} 

---

Nota que este enfoque funciona para diversos N como 32, 64, 16 o unsigned, unsigned long, etc. sin tener que recurrir a tipos más amplios. También funciona para tipos sin signo más estrecho que int/unsigned.