thực hiện lại modulo bằng cách sử dụng các thay đổi bit?

Question

Tôi đang viết một số mã cho một hệ thống rất hạn chế trong đó toán tử mod rất chậm. Trong mã của tôi, modulo cần được sử dụng khoảng 180 lần mỗi giây và tôi nghĩ rằng việc loại bỏ nó càng nhiều càng tốt sẽ làm tăng đáng kể tốc độ mã của tôi, vì bây giờ một chu kỳ của vòng lặp chính của tôi không chạy ở 1/60 của một thứ hai như nó cần. Tôi đã tự hỏi nếu nó có thể tái thực hiện các modulo bằng cách sử dụng chỉ thay đổi chút như là có thể với phép nhân và chia. Vì vậy, đây là mã của tôi cho đến nay trong c + + (nếu tôi có thể thực hiện một modulo bằng cách sử dụng lắp ráp nó sẽ được tốt hơn). Làm thế nào tôi có thể loại bỏ các modulo mà không cần sử dụng phân chia hoặc phép nhân?

while(input > 0) 
{ 
    out = (out << 3) + (out << 1); 
    out += input % 10; 

    input = (input >> 8) + (input >> 1); 
} 

EDIT: Trên thực tế tôi nhận ra rằng tôi cần phải làm điều đó cách hơn 180 lần mỗi giây. Việc xem như giá trị của đầu vào có thể là một số rất lớn lên đến 40 chữ số.

Answer 1

Bạn có thể làm gì với đơn giản hoạt động bitwise đang lấy một giá trị modulo (số chia) của giá trị (cổ tức) bằng cách AND 'với số chia là 1. Một vài ví dụ:

unsigned int val = 123; // initial value 
unsigned int rem; 

rem = val & 0x3; // remainder after value is divided by 4. 
       // Equivalent to 'val % 4' 
rem = val % 5; // remainder after value is divided by 5. 
       // Because 5 isn't power of two, we can't simply AND it with 5-1(=4). 

Tại sao lại hoạt động? Hãy xem xét một mẫu bit cho giá trị 123 là 1111011 và sau đó ước số 4, có mẫu bit là 00000100. Như chúng ta biết bây giờ, ước số phải là sức mạnh của hai (như 4 là) và chúng ta cần phải giảm nó bằng một (từ 4 đến 3 trong số thập phân) cho chúng ta mẫu bit 00000011. Sau bitwise-AND cả 123 và 3 ban đầu, mẫu bit kết quả sẽ là 00000011. Điều đó hóa ra là 3 thập phân. Lý do tại sao chúng ta cần một ước số lũy thừa là khi chúng ta cắt giảm chúng bằng một, chúng ta nhận được tất cả các bit ít quan trọng hơn được đặt thành 1 và phần còn lại là 0. Khi chúng ta thực hiện bitwise AND, nó 'hủy bỏ' các bit quan trọng hơn từ giá trị ban đầu, và để chúng ta chỉ đơn giản là phần còn lại của giá trị ban đầu chia cho số chia.

Tuy nhiên, việc áp dụng điều gì đó cụ thể như thế này cho các ước số tùy ý sẽ không hoạt động trừ khi bạn biết số chia của bạn trước (lúc biên dịch, và thậm chí yêu cầu mã số riêng biệt) - giải quyết thời gian chạy không khả thi, đặc biệt không phải trong trường hợp của bạn, nơi hiệu suất quan trọng.

Cũng có a previous question related to the subject có thể có thông tin thú vị về vấn đề này từ các quan điểm khác nhau.

Answer 2

Làm modulo 10 với các thay đổi bit sẽ khó và xấu xí, vì các thay đổi bit vốn đã là nhị phân (trên bất kỳ máy nào bạn sẽ chạy vào ngày hôm nay). Nếu bạn nghĩ về điều đó, các thay đổi bit đơn giản là nhân hoặc chia cho 2.

Nhưng có một giao dịch không gian rõ ràng bạn có thể thực hiện ở đây: thiết lập bảng giá trị out và out % 10 và tra cứu. Sau đó, dòng trở thành

out += tab[out] 

và với bất kỳ may mắn nào, sẽ trở thành một hoạt động thêm 16 bit và cửa hàng.

Answer 3

Nếu bạn muốn thực hiện modulo 10 và thay đổi, có thể bạn có thể điều chỉnh double dabble algorithm theo nhu cầu của bạn?

Thuật toán này được sử dụng để chuyển đổi số nhị phân sang thập phân mà không cần sử dụng modulo hoặc phân chia.

Answer 4

Mọi quyền của 16 kết thúc bằng 6.Nếu bạn đại diện cho số như một tổng của các quyền hạn của 16 (tức là chia nó thành nybbles), sau đó mỗi thuật ngữ đóng góp cho chữ số cuối cùng trong cùng một cách, ngoại trừ vị trí của một người.

0x481A % 10 = (0x4 * 6 + 0x8 * 6 + 0x1 * 6 + 0xA) % 10 

Lưu ý rằng 6 = 5 + 1 và 5 sẽ hủy nếu có số chẵn. Vì vậy, chỉ cần tổng hợp các nybbles (ngoại trừ cái cuối cùng) và thêm 5 nếu kết quả là lẻ.

0x481A % 10 = (0x4 + 0x8 + 0x1 /* sum = 13 */ 
       + 5 /* so add 5 */ + 0xA /* and the one's place */) % 10 
      = 28 % 10 

Điều này làm giảm 16 bit, 4 nybble modulo thành số tối đa 0xF * 4 + 5 = 65. Trong hệ nhị phân, đó là khó chịu vẫn còn 3 nybbles vì ​​vậy bạn sẽ cần phải lặp lại các thuật toán (mặc dù một trong số họ không thực sự đếm).

Nhưng 286 cần có thêm BCD hiệu quả hợp lý mà bạn có thể sử dụng để thực hiện tổng và nhận kết quả trong một lần truyền. (Điều đó đòi hỏi phải chuyển đổi từng nybble sang BCD theo cách thủ công; Tôi không biết đủ về nền tảng để nói cách tối ưu hóa nó hoặc cho dù đó là vấn đề.)

Answer 5

Thực tế chia theo hằng số là một tối ưu hóa nổi tiếng cho trình biên dịch và trên thực tế, gcc đã làm nó.

này đoạn mã đơn giản:

int mod(int val) { 
    return val % 10; 
} 

Tạo đoạn mã sau vào gcc khá cũ của tôi với O3:

_mod: 
     push ebp 
     mov  edx, 1717986919 
     mov  ebp, esp 
     mov  ecx, DWORD PTR [ebp+8] 
     pop  ebp 
     mov  eax, ecx 
     imul edx 
     mov  eax, ecx 
     sar  eax, 31 
     sar  edx, 2 
     sub  edx, eax 
     lea  eax, [edx+edx*4] 
     mov  edx, ecx 
     add  eax, eax 
     sub  edx, eax 
     mov  eax, edx 
     ret 

Nếu bạn bỏ qua các chức năng bạt/mở đầu, về cơ bản hai muls (thực trên x86 chúng tôi may mắn và có thể sử dụng lea cho một) và một số thay đổi và thêm/subs. Tôi biết rằng tôi đã giải thích lý thuyết đằng sau việc tối ưu hóa này ở đâu đó, vì vậy tôi sẽ xem liệu tôi có thể tìm thấy bài viết đó trước khi giải thích nó một lần nữa hay không. Bây giờ trên các CPU hiện đại chắc chắn nhanh hơn việc truy cập bộ nhớ (ngay cả khi bạn nhấn cache), nhưng liệu CPU của bạn có nhanh hơn một chút hay không là một câu hỏi chỉ có thể được trả lời với điểm chuẩn (và cũng đảm bảo trình biên dịch của bạn đang làm tối ưu hóa đó, nếu không bạn luôn có thể "ăn cắp" phiên bản gcc tại đây;)). Đặc biệt là xem xét rằng nó phụ thuộc vào một mulhs hiệu quả (tức là bit cao hơn của một hướng dẫn nhân) để có hiệu quả. Lưu ý rằng mã này là không phải là kích thước độc lập - chính xác là thay đổi số ma thuật (và cũng có thể là một phần của việc thêm/thay đổi), nhưng điều đó có thể được điều chỉnh.

Answer 6

Nhận một bản sao "Chương trình Viết hiệu quả" của Jon Bentley (thật đáng buồn khi in ra, bản tóm tắt nằm trong số "Programming Pearls") của Jon Bentley. Nó thảo luận cách thức (và khi nào!) Để ép ra sự sụt giảm hiệu suất cuối cùng trong các chương trình. Những thay đổi đơn giản như những gì được thảo luận ở đây được thực hiện như một vấn đề của khóa học bởi các trình biên dịch hiện tại, kiểm tra mã bộ mã nguồn của các nguồn thay thế và giữ cho bất cứ điều gì rõ ràng hơn.