Gần đây tôi đã viết một lớp Vector 3 và tôi đã gửi hàm normalize() của mình để đánh giá cho một người bạn. Ông nói nó là tốt, nhưng tôi nên nhân với các đối ứng nếu có thể bởi vì "nhân rẻ hơn chia" trong thời gian CPU.Tại sao nhân rẻ hơn chia?
Câu hỏi của tôi đơn giản là, tại sao vậy?
Hãy suy nghĩ về điều đó trong các hoạt động cơ bản mà phần cứng có thể dễ dàng thực hiện hơn - cộng, trừ, thay đổi, so sánh. Phép nhân ngay cả trong một thiết lập tầm thường đòi hỏi ít bước cơ bản hơn - cộng thêm, nó đủ khả năng các thuật toán tiến bộ thậm chí còn nhanh hơn - xem ví dụ here ... nhưng phần cứng thường không tận dụng được (ngoại trừ phần cứng cực kỳ chuyên dụng). Ví dụ, như wikipedia URL nói, "Toom – Cook có thể làm một phép nhân kích thước-N cho chi phí của năm phép nhân kích thước N" - đó là khá nhanh cho các số rất lớn (thuật toán của Fürer, một sự phát triển khá gần đây, có thể làm Θ(n ln(n) 2Θ(ln*(n))) - một lần nữa, xem trang wikipedia và liên kết từ đó).
Bộ phận chỉ chậm hơn về mặt lý thuyết, như - một lần nữa - mỗi wikipedia; ngay cả các thuật toán tốt nhất (một số trong đó được thực hiện trong HW, chỉ vì họ không có nơi nào phức tạp và phức tạp như các thuật toán tốt nhất cho phép nhân ;-) không thể giữ một ngọn nến cho các phép nhân.
Chỉ cần định lượng vấn đề với số không lớn, dưới đây là một số kết quả với gmpy, một trình bao bọc Python dễ sử dụng xung quanh GMP, có xu hướng có triển khai khá tốt về số học mặc dù không nhất thiết phải là mới nhất- và thở khò khè lớn nhất. Trên một chậm (thế hệ thứ nhất ;-) Macbook Pro:
$ python -mtimeit -s'import gmpy as g; a=g.mpf(198792823083408); b=g.mpf(7230824083); ib=1.0/b' 'a*ib'
1000000 loops, best of 3: 0.186 usec per loop
$ python -mtimeit -s'import gmpy as g; a=g.mpf(198792823083408); b=g.mpf(7230824083); ib=1.0/b' 'a/b'
1000000 loops, best of 3: 0.276 usec per loop
Như bạn thấy, ngay cả ở quy mô nhỏ này (số bit trong số), và với các thư viện được tối ưu hóa bởi những người giống hệt nhau tốc độ bị ám ảnh , phép nhân bằng nghịch đảo có thể tiết kiệm 1/3 thời gian phân chia.
Nó có thể là chỉ trong những tình huống hiếm hoi mà những vài nano giây là một vấn đề sống hay chết, nhưng, khi họ là, và tất nhiên NẾU bạn vẫn liên tục chia cho giá trị như nhau (để trừ dần nguyên đi những 1.0/b hoạt động!), sau đó kiến thức này có thể là một cuộc sống tiết kiệm.
(Phần lớn trong bối cảnh đó - x*x thường sẽ tiết kiệm được thời gian so với x**2 [trong ngôn ngữ mà có một "nâng lên nắm quyền" điều hành **, như Python và Fortran] - và Horner scheme cho tính toán đa thức là bao la một lợi thế để lặp lại các hoạt động nâng cao quyền lực! -).
[Các thông tin hữu ích về các hướng dẫn lắp ráp.] (Http://www.agner.org/optimize/instruction_tables.pdf) – nonsensickle
Hoạt động CPU cho bộ phận (phao) phức tạp hơn nhiều so với phép nhân. CPU phải làm nhiều hơn nữa. Tôi không hiểu nhiều về phần cứng, nhưng bạn có thể tìm thấy rất nhiều thông tin về việc triển khai phân chia chung (ví dụ: dựa trên các thuật toán newton-raphson).
Tôi cũng sẽ cẩn thận về việc luôn sử dụng phép nhân của nghịch đảo thay vì chia để đạt được hiệu suất CPU: chúng có thể không cho kết quả chính xác như nhau. Điều này có thể hoặc có thể không quan trọng tùy thuộc vào ứng dụng của bạn.
Nếu bạn nghĩ đến lớp học, bạn sẽ nhớ rằng phép nhân khó hơn việc cộng và chia sẽ khó hơn phép nhân. Mọi thứ không khác gì CPU.
Cũng nên tính toán nghịch đảo liên quan đến một bộ phận, vì vậy trừ khi bạn tính toán nghịch đảo một lần và sử dụng nó ba lần, bạn sẽ không thấy tăng tốc.
+1 cho nhận xét cần thiết về sự cần thiết phải nhớ lại đối ứng. – Thilo
Đối với lớp học, tôi tìm thấy (vẫn còn làm) trừ khó hơn để làm hơn ngoài ra, nhưng hai dường như giống nhau cho một CPU. ;-) – Thilo
@Thilo: khi bạn cần thực hiện phép trừ, chỉ cần loại bỏ toán hạng thứ hai và sau đó bạn có thể thực hiện thay thế "dễ dàng hơn" thay thế. :-) –
Bạn có đang xử lý ints hoặc phao không? – Uri
Đối với vectơ3, số nguyên. Tại sao? – jkeys
Nhân bản: http://stackoverflow.com/questions/655537/is-multiplying-the-inverse-better-or-worse – womp