Tại sao phân chia đắt hơn phép nhân?

Question

Tôi không thực sự cố gắng để tối ưu hóa bất cứ điều gì, nhưng tôi nhớ nghe điều này từ các lập trình viên tất cả các thời gian, mà tôi lấy nó như là một sự thật. Sau khi tất cả họ có nghĩa vụ phải biết công cụ này.

Nhưng tôi tự hỏi tại sao phân chia thực sự chậm hơn so với phép nhân? Không phải là phân chia chỉ là một phép trừ vinh quang, và phép nhân là một bổ sung vinh quang? Vì vậy, toán học tôi không thấy lý do tại sao đi một chiều hoặc khác có chi phí tính toán rất khác nhau.

Có ai vui lòng làm rõ nguyên nhân/nguyên nhân của điều này vì vậy tôi biết, thay vì những gì tôi đã nghe từ lập trình viên khác mà tôi đã hỏi trước đó là: "vì".

Answer 1

CPU ALU (Đơn vị số học-logic) thực hiện các thuật toán, mặc dù chúng được triển khai trong phần cứng. Thuật toán phép nhân cổ điển bao gồm Wallace tree và Dadda tree. Thêm thông tin có sẵn here. Các kỹ thuật phức tạp hơn có sẵn trong các bộ vi xử lý mới hơn. Nói chung, bộ vi xử lý cố gắng song song các hoạt động bit-cặp để giảm thiểu chu kỳ đồng hồ cần thiết. Thuật toán nhân có thể được song song khá hiệu quả (mặc dù cần nhiều bóng bán dẫn hơn).

Division algorithms không thể song song một cách hiệu quả. Thuật toán phân chia hiệu quả nhất là khá phức tạp (The Pentium FDIV bug thể hiện mức độ phức tạp). Nói chung, chúng đòi hỏi nhiều chu kỳ đồng hồ trên mỗi bit. Nếu bạn đang theo các chi tiết kỹ thuật khác, here là một lời giải thích thú vị từ Intel. Intel thực sự là patented thuật toán phân chia của họ.