Addestramento e sottrazione modulari sicuri per il troppo pieno in C?

Question

Sto implementando un algoritmo in C che deve eseguire rapidamente addizioni e sottrazioni modulari su interi senza segno e gestire correttamente le condizioni di overflow. Ecco cosa ho ora (che funziona):

/* 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; 
} 

Qualcuno sa di un algoritmo migliore? Le librerie che ho trovato che fanno l'aritmetica modulare sembrano tutte per numeri di precisione arbitrari di grandi dimensioni che sono decisamente eccessivi.

Modifica: voglio farlo funzionare correttamente su una macchina a 32 bit. Inoltre, le mie funzioni esistenti sono banalmente convertite per funzionare su altre dimensioni di numeri interi senza segno, una proprietà che sarebbe piacevole conservare.

Answer 1

Le operazioni modulari di solito presuppongono che a e b siano inferiori a m. Questo permette di algoritmi più semplici:

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; 
} 

Fonte: Matters Computational, capitolo 39.1.

Answer 2

Mi piacerebbe fare l'aritmetica in uint32_t se si adatta e in uint64_t in caso 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; 
} 

su un'architettura con i tipi 64 bit integer, questo dovrebbe essere quasi nessuno in testa, si potrebbe anche pensare di fare solo tutto in uint64_t. Sulle architetture in cui uint64_t viene sintetizzato, , lascia che il compilatore decida ciò che pensa sia il migliore, quindi controlla l'assemblatore generato e verifica se è soddisfacente.

Answer 3

Overflow-safe aggiunta modulare

prima stabilire che a<m e b<m con il solito % m.

Aggiungi aggiornato a e b.

Qualora a (o b) superano la somma uintN_t, allora la somma matematicamente era un uintN_t trabocco e la sottrazione di m sarà "mod" matematicamente riassumere nella gamma di uintN_t.

Se la somma supera m, come nel passaggio precedente, una singola sottrazione di m "mod" la somma.

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; 
} 

Abbastanza semplice alla fine.

---

Overflow-safe sottrazione modulare

Variazione su @Evgeny Kluev buona risposta.

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 questo approccio funziona per vari N come 32, 64, 16 o unsigned, unsigned long, ecc senza ricorrere a tipi più ampi. Funziona anche per tipi non firmati più stretti di int/unsigned.