Tính toán (a * b) mod c nhanh chóng cho c = 2^N + -1

Question

Trong phép toán số nguyên 32 bit, phép tính cơ bản của phép cộng và nhân được tính ngầm ẩn 2^32, có nghĩa là kết quả của bạn sẽ là thứ tự thấp nhất bit của phép cộng hoặc nhân.

Nếu bạn muốn tính kết quả bằng một mô đun khác, bạn chắc chắn có thể sử dụng bất kỳ số lượng lớp BigInt nào bằng các ngôn ngữ khác nhau. Và đối với các giá trị a, b, c < 2^32, bạn có thể tính toán giá trị trung gian trong 64 bit ints dài và sử dụng được xây dựng trong% toán tử để giảm số trả lời thích hợp

Nhưng tôi đã được thông báo rằng có các thủ thuật đặc biệt để hiệu quả tính toán a * b mod C khi C có dạng (2^N) -1 hoặc (2^N) +1, không sử dụng phép toán 64 bit hoặc thư viện BigInt và khá hiệu quả, nhiều hơn một đánh giá mô đun tùy ý, và cũng có thể tính toán các trường hợp bình thường sẽ tràn một int 32 bit nếu bạn đã bao gồm phép nhân trung gian.

Thật không may, mặc dù nghe rằng các trường hợp đặc biệt như vậy có phương pháp đánh giá nhanh, tôi chưa thực sự tìm thấy mô tả về phương pháp. "Đó không phải là ở Knuth sao?" "Đó không phải là một nơi nào đó trên Wikipedia?" là những lầm bầm tôi đã nghe.

Có vẻ như đây là một kỹ thuật phổ biến trong các trình tạo số ngẫu nhiên đang làm số nhân * b mod 2147483647, vì 2147483647 là số nguyên bằng 2^31 -1.

Vì vậy, tôi sẽ hỏi các chuyên gia. Trường hợp đặc biệt thông minh này có phương pháp nhân với mod mà tôi không thể tìm thấy bất kỳ cuộc thảo luận nào?

Answer 1

Tôi nghĩ rằng Bí quyết là như sau (tôi sẽ làm điều đó trong cơ sở 10, vì nó dễ dàng hơn, nhưng nguyên tắc nên giữ)

Giả sử bạn là nhân a*b mod 10000-1, và

a = 1234 = 12 * 100 + 34 
b = 5432 = 54 * 100 + 32 

tại a*b = 12 * 54 * 10000 + 34 * 54 * 100 + 12 * 32 * 100 + 34 * 32

12 * 54 * 10000 = 648 * 10000 
34 * 54 * 100 = 1836 * 100 
12 * 32 * 100 = 384 * 100 
34 * 32   = 1088 

Kể từ x * 10000 ≡ x (mod 10000-1) [1], t anh ta đầu tiên và cuối cùng trở thành 648 + 1088. Thuật ngữ thứ hai và thứ ba là nơi 'lừa đảo' đến.Lưu ý rằng:

1836 = 18 * 100 + 36 
1836 * 100 ≡ 18 * 10000 + 3600 ≡ 3618 (mod 10000-1). 

Đây thực chất là một ca làm tròn. Cho kết quả 648 + 3618 + 8403 + 1088. Và cũng lưu ý rằng trong mọi trường hợp, các số nhân là < 10000 (kể từ < 100 và b < 100), vì vậy điều này có thể tính được nếu bạn chỉ có thể có nhiều số có 2 chữ số và thêm chúng.

Trong nhị phân, nó sẽ hoạt động tương tự.

Bắt đầu bằng a và b, cả hai đều là 32 bit. Giả sử bạn muốn nhân chúng mod 2^31 - 1, nhưng bạn chỉ có một hệ số 16 bit (cho 32 bit). Thuật toán sẽ là một cái gì đó như thế này:

a = 0x12345678 
b = 0xfedbca98 
accumulator = 0 
for (x = 0; x < 32; x += 16) 
    for (y = 0; y < 32; y += 16) 
     // do the multiplication, 16-bit * 16-bit = 32-bit 
     temp = ((a >> x) & 0xFFFF) * ((b >> y) & 0xFFFF) 

     // add the bits to the accumulator, shifting over the right amount 
     total_bits_shifted = x + y 
     for (bits = 0; bits < total_bits_shifted + 32; bits += 31) 
      accumulator += (temp >> (bits - total_bits_shifted)) & 0x7FFFFFFF 

     // do modulus if it overflows 
     if (accumulator > 0x7FFFFFFFF) 
      accumulator = (accumulator >> 31) + (accumulator & 0x7FFFFFFF); 

Cuối năm, do đó phần tích lũy của nó có thể không hoạt động. Tôi nghĩ về nguyên tắc nó là đúng mặc dù. Ai đó cảm thấy tự do để chỉnh sửa điều này để làm cho nó đúng.

Chưa được kiểm tra, điều này cũng khá nhanh, đó là những gì PRNG sử dụng, tôi đoán vậy.

[1]: x*10000 ≡ x*(9999+1) ≡ 9999*x + x ≡ x (mod 9999)

Answer 2

Tìm kiếm nhanh được bật lên: http://home.pipeline.com/~hbaker1/AB-mod-N.pdf. Thật không may, đã quá muộn để tôi có đủ ý nghĩa để chỉ viết vào công thức đơn giản, nhưng có lẽ trong bài báo đó ở đâu đó.

Answer 3

Giả sử bạn có thể tính toán * b là p*2^N+q. Điều này có thể yêu cầu tính toán 64 bit, hoặc bạn có thể chia a và b thành các phần 16 bit và tính toán trên 32 bit.

Sau đó, a*b mod 2^N-1 = p+q mod 2^N-1 từ 2^N mod 2^N-1 = 1.

Và a*b mod 2^N+1 = -p+q mod 2^N+1 từ 2^N mod 2^N+1 = -1.

Trong cả hai trường hợp, không có sự phân chia theo số 2^N-1 hoặc 2^N+1.

Answer 4

Thay vì giảm mô-đun ở mỗi bước, bạn có thể sử dụng Montgomery reduction (có descriptions) khác để giảm chi phí tính toán phép nhân. Điều này vẫn không sử dụng các thuộc tính của N là cộng/trừ đi một sức mạnh của hai, mặc dù.

Answer 5

Danh tính bạn đang muốn tìm x mod N = (x mod 2^q)- c*floor(x/2^q), cho rằng N = 2^q + c và c là số nguyên bất kỳ (nhưng thường ± 1).

Bạn có thể muốn đọc phần 9.2.3: "môđun của hình thức đặc biệt" trong "Số Thủ: Một tính toán Perspective" bởi Richard Crandall và Carl Pomerance. Bên cạnh lý thuyết, nó chứa mã giả cho một thuật toán thực hiện quan hệ trên.

Answer 6

Tôi đã tìm thấy một số rather extensive page về chủ đề này, không chỉ thảo luận về thuật toán mà còn cả lịch sử cụ thể của sự cố và giải pháp và cách mọi người sử dụng giải pháp.