Tính toán hiệu quả các bit thứ tự cao của phép nhân

Question

Nhiều CPU có mã hóa đơn lẻ để trả về các bit thứ tự của số nguyên 32 bit là cao. Thông thường nhân hai số nguyên 32 bit tạo ra một kết quả 64 bit, nhưng điều này được cắt ngắn xuống 32 bit thấp nếu bạn lưu trữ nó trong một số nguyên 32 bit.

Ví dụ, trên PowerPC, mã mở mulhw trả về 32 bit cao của kết quả 64 bit của một bit 32x32 nhân trong một đồng hồ. Đây chính xác là những gì tôi đang tìm kiếm, nhưng đáng giá hơn. Có một opcode tương tự, umulhi(), trong NVidia CUDA.

Trong C/C++, có cách hiệu quả để trả lại các bit thứ tự cao của 32x32 nhân không? Hiện nay tôi tính toán nó bằng cách đúc đến 64 bit, một cái gì đó như:

unsigned int umulhi32(unsigned int x, unsigned int y) 
{ 
    unsigned long long xx=x; 
    xx*=y; 
    return (unsigned int)(xx>>32); 
} 

nhưng điều này là chậm hơn so với một thường xuyên 32 bởi 32 nhân hơn 11 lần vì tôi đang sử dụng quá mức cần thiết chút toán 64 ngay cả đối với các nhân.

Có cách nào nhanh hơn để tính toán các bit thứ tự cao không?

Điều này rõ ràng là không phải là được giải quyết tốt nhất với thư viện BigInteger (quá mức cần thiết và sẽ có phí rất lớn).

SSE dường như có PMULHUW, 16x16 -> phiên bản 16 bit hàng đầu này, nhưng không phải phiên bản 32x32 -> hàng đầu như tôi đang tìm kiếm.

Answer 1

gcc 4.3.2, với tối ưu hóa -O1 hoặc cao hơn, dịch chức năng của bạn chính xác như bạn thấy nó để IA32 lắp ráp như thế này:

umulhi32: 
     pushl %ebp 
     movl %esp, %ebp 
     movl 12(%ebp), %eax 
     mull 8(%ebp) 
     movl %edx, %eax 
     popl %ebp 
     ret 

nào chỉ được làm một đơn 32 bit mull và đưa mức cao 32 bit của kết quả (từ %edx) vào giá trị trả lại.

Đó là những gì bạn muốn, phải không?Có vẻ như bạn chỉ cần bật tối ưu hóa trên trình biên dịch của mình;) Có thể bạn có thể đẩy trình biên dịch theo đúng hướng bằng cách loại bỏ biến trung gian:

unsigned int umulhi32(unsigned int x, unsigned int y) 
{ 
    return (unsigned int)(((unsigned long long)x * y)>>32); 
} 

Answer 2

Tôi không nghĩ rằng có một cách để làm điều này trong tiêu chuẩn C/C++ tốt hơn so với những gì bạn đã có. Những gì tôi muốn làm là viết lên một wrapper lắp ráp đơn giản mà trả về kết quả mà bạn muốn. Không phải là bạn đang hỏi về Windows, nhưng là một ví dụ mặc dù Windows có một API có vẻ như nó làm những gì bạn muốn (32 32 bit nhân trong khi thu được kết quả 64 bit đầy đủ), nó thực hiện nhân với macro làm những việc bạn đang làm:

#define UInt32x32To64(a, b) (ULONGLONG)((ULONGLONG)(DWORD)(a) * (DWORD)(b)) 

Answer 3

Trên intel 32 bit, nhân ảnh hưởng đến hai thanh ghi cho đầu ra. Đó là, 64 bit có sẵn hoàn toàn, cho dù bạn có muốn hay không. Chỉ là một hàm của trình biên dịch đủ thông minh để tận dụng nó.

Trình biên dịch hiện đại làm những điều tuyệt vời, vì vậy đề xuất của tôi là thử nghiệm với cờ tối ưu hóa một số chi tiết, ít nhất là trên Intel. Bạn sẽ nghĩ rằng trình tối ưu hóa có thể biết rằng bộ xử lý tạo ra một giá trị 64 bit từ 32 x 32 bit. Điều đó nói rằng, tại một thời điểm nào đó, tôi đã cố gắng để trình biên dịch sử dụng modulo cũng như cổ tức trên kết quả phân chia, nhưng trình biên dịch Microsoft cũ từ năm 1998 không đủ thông minh để nhận ra cùng một lệnh tạo ra cả hai kết quả.