Bổ sung và trừ mô-đun an toàn tràn trong C?

Question

Tôi đang triển khai một thuật toán trong C cần thực hiện phép cộng và trừ mô-đun một cách nhanh chóng trên các số nguyên không dấu và có thể xử lý đúng các điều kiện tràn. Dưới đây là những gì tôi hiện có (hoạt động không hoạt động):

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

Bất kỳ ai biết thuật toán tốt hơn? Các thư viện tôi đã tìm thấy rằng làm số học mô-đun tất cả dường như được cho số lượng lớn chính xác tùy ý đó là cách overkill.

Chỉnh sửa: Tôi muốn điều này chạy tốt trên máy 32 bit. Ngoài ra, các chức năng hiện tại của tôi được chuyển đổi trivially để làm việc trên các kích thước khác của số nguyên unsigned, một tài sản mà sẽ được tốt đẹp để giữ lại.

Answer 1

Hoạt động mô-đun thường giả định rằng a và b nhỏ hơn m. Điều này cho phép các thuật toán đơn giản hơn:

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

Nguồn: Matters Computational, chương 39.1.

Answer 2

Tôi chỉ làm phép tính số học trong uint32_t nếu nó phù hợp và trong uint64_t nếu không.

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

Trên kiến ​​trúc với các loại số nguyên 64 bit, điều này hầu như không có phí, bạn thậm chí có thể nghĩ chỉ làm mọi thứ trong uint64_t. Trên các kiến ​​trúc mà ở đó uint64_t được tổng hợp để cho trình biên dịch quyết định những gì anh ta nghĩ là tốt nhất, sau đó nhìn vào bộ tạo được tạo ra và mmeasure để xem điều này có thỏa đáng hay không.

Answer 3

tràn an toàn mô-đun bổ sung

Đầu tiên thiết lập rằng a<m và b<m với bình thường % m.

Thêm cập nhật a và b.

nên a (hoặc b) vượt quá tổng uintN_t, sau đó tổng toán học là một uintN_t tràn và phép trừ của m sẽ "mod" các mặt toán học tổng hợp vào trong phạm vi của uintN_t.

Nếu số tiền vượt quá m, thì giống như bước trên, một phép trừ đơn là m sẽ "mod" tổng.

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

Khá đơn giản cuối cùng.

---

tràn an toàn mô-đun trừ

Biến thể trên @Evgeny Kluev câu trả lời tốt.

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

---

Lưu ý phương pháp này làm việc cho nhiều N như 32, 64, 16 hoặc unsigned, unsigned long, vv mà không phải dùng đến loại rộng hơn. Nó cũng hoạt động cho các loại unsigned hẹp hơn int/unsigned.