Cách hiệu quả nhất để tính toán một đa thức

Question

Đa thức: a0x^0 + a1x^1 + a2x^2 + a3x^3 + ... + ANX^n

Array: array_a [] = {a0, a1, a2, a3 ... an};

tôi đã viết một hàm để tính toán đa thức này trong Java:

public double cal(double x) { 
    double y = 0.0; 
    for (int index = array_a.length - 1; index >= 0; index--) { 
     y = array_a[index] + y * x; 
    } 
    return y; 
} 

Điều này có vẻ nhanh hơn gấp 5 lần so với vòng lặp y += array_a[index] * Math.Pow(x, index);

Nhưng tôi tự hỏi nếu có một cách tốt hơn để tính toán đa thức này?

** Đối với bất kỳ ai nghĩ đó là phép tính khác: tôi đã thử nghiệm hàm ở trên. Nó làm điều tương tự với y += array_a[index] * Math.Pow(x, index); và chúng tính toán cùng một kết quả.

Cảm ơn.

Answer 1

Đây là Phương pháp của Horner. Nếu bạn chỉ muốn để tính toán nó một lần mỗi đa thức, this is the most efficient algorithm:

... phương pháp Horner chỉ đòi hỏi n bổ sung và n phép nhân, và các yêu cầu lưu trữ của nó là chỉ n lần so với số bit của x. …

Phương pháp của Horner là tối ưu, theo nghĩa là bất kỳ thuật toán nào để đánh giá đa thức tùy ý đều phải sử dụng ít nhất là nhiều thao tác. Alexander Ostrowski đã chứng minh vào năm 1954 rằng số lượng bổ sung cần thiết là tối thiểu. Victor Pan đã chứng minh năm 1966 rằng số lượng phép nhân là tối thiểu.

Nếu bạn cần để đánh giá đa thức rất nhiều lần và mức độ rất cao, sau đó có phương pháp để chuyển đổi các đại diện của các đa thức (Việc chuẩn bị trước) sao cho số lượng nhân được giảm xuống & lfloor; n/2 & rfloor; + 2. Điều này có vẻ không thực tế lắm, ít nhất tôi chưa bao giờ thấy điều này trong tự nhiên. I've found an online paper that describes some of the algorithms if you are interested.

Cũng đề cập trong bài báo, do kiến ​​trúc CPU nó có thể hiệu quả hơn nếu bạn đánh giá thậm chí và các điều khoản lẻ riêng biệt để họ có thể được đặt trong đường ống song song:

public double cal(double x) { 
    double x2 = x * x; 
    double y_odd = 0.0, y_even = 0.0; 
    int index = array_a.length - 1; 
    if (index % 2 == 0) { 
     y_even = array_a[index]; 
     index -= 1; 
    } 
    for (; index >= 0; index -= 2) { 
     y_odd = array_a[index] + y_odd * x2; 
     y_even = array_a[index-1] + y_even * x2; 
    } 
    return y_even + y_odd * x; 
} 

Các JIT/biên dịch có thể có thể thực hiện chuyển đổi này cho bạn hoặc thậm chí sử dụng SIMD để làm cho nó tự động hóa rất nhanh. Dù sao, đối với loại tối ưu hóa vi mô, luôn luôn hồ sơ trước khi cam kết một giải pháp cuối cùng.