Làm cách nào để tôi có thể giảm phân chia theo 2^n + 1?

Question

Tôi cần thực hiện một số bộ phận số nguyên trong đường dẫn nóng của mã. Tôi đã được xác định thông qua hồ sơ và chu kỳ đếm rằng các bộ phận nguyên đang chi phí cho tôi. Tôi hy vọng có điều gì đó tôi có thể làm để tăng sức mạnh cho các bộ phận thành một thứ rẻ hơn.

Trong đường dẫn này, tôi chia cho 2^n + 1, trong đó n là biến. Về cơ bản, tôi muốn tối ưu hóa chức năng này để loại bỏ toán tử phân chia:

unsigned long compute(unsigned long a, unsigned int n) 
{ 
    return a/((1 << n) + 1); 
} 

Nếu tôi chia cho 2^n, tôi chỉ thay thế div bằng shift phải bằng n. Nếu tôi được chia cho một hằng số, tôi sẽ để sức mạnh trình biên dịch giảm phân chia cụ thể đó, có khả năng biến nó thành một số nhân và một số thay đổi.

Có tối ưu hóa tương tự áp dụng cho 2^n + 1 không?

Chỉnh sửa: đây có thể là số nguyên 64 bit tùy ý. n chỉ mất một vài giá trị giữa 10 và, ví dụ, 25. Tôi chắc chắn có thể tính toán trước một số giá trị cho mỗi n, nhưng không phải cho a.

Answer 1

Vì bạn chỉ có thể thay đổi một int rất nhiều nơi, bạn có thể đặt tất cả những trường hợp này thành một sự lựa chọn của một trong những bộ phận của một hằng số:

unsigned long compute(unsigned long a, unsigned int n) 
{ 
    // assuming a 32-bit architecture (making this work for 64-bits 
    // is left as an exercise for the reader): 
    switch (n) { 
     case 0: return a/((1 << 0) + 1); 
     case 1: return a/((1 << 1) + 1); 
     case 2: return a/((1 << 2) + 1); 

      // cases 3 through 30... 

     case 31: return a/((1 << 31) + 1); 
    } 
} 

Vì vậy, bây giờ mỗi bộ phận là bởi một hằng số, mà trình biên dịch thường sẽ giảm xuống một loạt các câu lệnh nhân/thay đổi/thêm (như câu hỏi được đề cập). Xem Does a c/c++ compiler optimize constant divisions by power-of-two value into shifts? cho các trang trí nội thất.

Answer 2

Bạn có thể thay thế phân chia số nguyên theo hằng số, bằng phép nhân (modulo wordsize) với số ma thuật và thay đổi.

Các số ma thuật có thể được tính toán trước cho các hằng số đã biết.

Vì n không thể lấy nhiều giá trị, ví dụ: 0..31 nó là "dễ dàng" để tính toán trước những con số ma thuật cho tất cả n và lưu trữ nó trong một bảng với 32 yếu tố.

Javascript Page for calculating the magic numbers

Một trình biên dịch tốt có thể tính toán các con số ma thuật và thay thế phân chia số nguyên bằng cách nhân và chuyển nếu số chia là hằng số tại thời gian biên dịch. Tùy thuộc vào cách phần còn lại của mã được cấu trúc xung quanh mã quan trọng hiệu suất, bạn có thể sử dụng thủ thuật macro hoặc nội tuyến để hủy đăng ký tất cả giá trị có thể của n và để trình biên dịch thực hiện công việc tìm số ma thuật (tương tự câu trả lời với chuyển đổi, nhưng tôi sẽ đặt thêm mã trong khu vực liên tục nếu không nó có thể là một tradeof không có giá trị nó - phân nhánh có thể chi phí bạn hiệu suất cũng)

Mô tả chi tiết cùng với mã để tính số ma thuật có thể được tài trợ trong Cuốn sách "Tin tặc Delight" của Henry S. Warren, Jr. (rất khuyến khích phải có cuốn sách!) pp. 180ff.

liên kết vào Google Sách cho chương có liên quan:

Chapter 10-9 Unsigned Division by Divisors >= 1