Đánh giá đa thức - vấn đề về điểm nổi hoặc tối ưu hóa?

Question

Từ Bí quyết Numerical:

Chúng tôi giả định rằng bạn biết đủ không bao giờ để đánh giá một đa thức theo cách này: p = c [0] + c [1] * x + c [2] * x * x + c [3] * x * x * x + c [4] * x * x * x * x; ...

Rõ ràng là tôi không biết đủ ...

Đây có phải là chỉ là một vấn đề tối ưu hóa hoặc là nó cũng là một điểm vấn đề số học nổi và tại sao?

Answer 1

Bạn có thể tính toán p=c[0]+c[1]*x+c[2]*x*x+c[3]*x*x*x+c[4]*x*x*x*x; như:

p=c[0]+(c[1]+(c[2]+(c[3]+c[4]*x)*x)*x)*x; 

Có ít nhiều phép nhân theo hình thức thứ hai. Dạng thứ hai này được gọi là “Horner's”.

Đây chỉ là vấn đề tối ưu hóa hay nó cũng là vấn đề số học dấu chấm động và tại sao?

Chủ yếu là vấn đề tối ưu hóa. Tuy nhiên, một số bộ vi xử lý hiện đại có một phép toán dấu chấm động để thực hiện phép nhân và phép cộng trong một lệnh đơn mà không làm tròn trung gian cho phép nhân, và trong khi lợi ích mà hầu hết người lập trình thấy vẫn là tối ưu hóa, nó cũng có nghĩa là kết quả chính xác hơn .

Biểu mẫu của Horner rất phù hợp để tính toán với số fused-multiply-add instruction này.

---

Cuối cùng, tôi nên chỉ ra vì mục đích hoàn chỉnh mà các bộ xử lý hiện đại có thể hiệu quả hơn nếu đa thức được trình bày cho chúng dưới dạng song song hơn. Xem ví dụ Estrin's scheme hoặc this blog post để được giải thích trực tiếp. Cuốn sách của bạn không ám chỉ đến yêu cầu biết về kế hoạch của Estrin. Nó chỉ ám chỉ đến yêu cầu biết về kế hoạch của Horner.