Nhanh hơn std :: pow là gì?

Question

Chương trình của tôi dành 90% thời gian CPU trong hàm std::pow(double,int). Độ chính xác không phải là một mối quan tâm chính ở đây, vì vậy tôi đã tự hỏi nếu có bất kỳ lựa chọn thay thế nhanh hơn. Một điều tôi đã nghĩ đến việc cố gắng là đúc để nổi, thực hiện các hoạt động và sau đó trở lại gấp đôi (chưa thử này chưa); Tôi lo ngại rằng đây không phải là một cách di động của cải thiện hiệu suất (không nhất CPU hoạt động trên đôi về bản chất không?)

Cheers

Answer 1

Dường như Martin Ankerl có một vài bài viết về vấn đề này, Optimized Approximative pow() in C/C++ rất độc đáo và có hai phiên bản nhanh, một là như sau:

inline double fastPow(double a, double b) { 
    union { 
    double d; 
    int x[2]; 
    } u = { a }; 
    u.x[1] = (int)(b * (u.x[1] - 1072632447) + 1072632447); 
    u.x[0] = 0; 
    return u.d; 
} 

dựa vào loại punning thông qua một liên minh mà là hành vi không xác định trong C++, từ dự thảo tiêu chuẩn phần 9.5[class.union]:

đang kết hôn, ít nhất một trong các thành viên dữ liệu tĩnh không có thể là một ctive bất cứ lúc nào, có nghĩa là, giá trị của hầu hết các thành viên dữ liệu không tĩnh có thể được lưu trữ trong một liên minh bất cứ lúc nào. [...]

nhưng hầu hết các trình biên dịch bao gồm gcc support this with well defined behavior:

Việc thực hành đọc từ một thành viên công đoàn khác với thời gian gần đây hầu hết các văn bản (gọi là “type-punning”) là phổ biến. Ngay cả với -fstrict-aliasing, type-punning được phép, với điều kiện bộ nhớ được truy cập thông qua các loại hình công đoàn

nhưng điều này không phải là phổ biến như this article points out và như tôi point out in my answer here sử dụng memcpy nên tạo mã giống hệt nhau và không gọi không xác định hành vi.

Anh ấy cũng liên kết đến số thứ hai Optimized pow() approximation for Java, C/C++, and C#.

Các bài viết đầu tiên cũng liên kết tới microbenchmarks mình here

Answer 2

Tùy thuộc vào những gì bạn cần phải làm, hoạt động trong lĩnh vực đăng nhập có thể làm việc - nghĩa là, bạn thay thế tất cả các giá trị của mình bằng logarit của chúng; phép nhân trở thành phép cộng, phép chia trở thành phép trừ và lũy thừa trở thành phép nhân. Nhưng bây giờ cộng và trừ trở thành các hoạt động tốn kém và có phần dễ bị lỗi.

Answer 3

lớn như thế nào là số nguyên của bạn? Họ có biết thời gian biên dịch không? Sẽ tốt hơn nếu tính x^2 là x*x thay vì pow(x,2). Lưu ý: Hầu như tất cả các ứng dụng của pow() là một lũy thừa số nguyên liên quan đến việc nâng một số lên lũy thừa thứ hai hoặc thứ ba (hoặc nghịch đảo nhân trong trường hợp số mũ âm). Sử dụng pow() là quá mức cần thiết trong các trường hợp như vậy. Sử dụng mẫu cho các quyền hạn số nguyên nhỏ này hoặc chỉ sử dụng x*x.

Nếu số nguyên nhỏ, nhưng không biết tại thời gian biên dịch, hãy nói giữa -12 và +12, phép nhân vẫn sẽ đánh bại pow() và sẽ không mất độ chính xác. Bạn không cần mười một phép nhân để tính x^12. Bốn sẽ làm. Sử dụng thực tế là x^(2n) = (x^n)^2 và x^(2n + 1) = x * ((x^n)^2). Ví dụ, x^12 là ((x * x * x)^2)^2.Hai phép nhân để tính x^3 (x * x * x), một số khác để tính x^6 và một số cuối để tính x^12.