Oleksii Trekhleb | Javascript algorithms (Horner's method)

This is a series of books diving deep into the core mechanisms of the JavaScript language.

 · 2 phút đọc.

This is a series of books diving deep into the core mechanisms of the JavaScript language.

In mathematics, Horner’s method (or Horner’s scheme) is an algorithm for polynomial evaluation. With this method, it is possible to evaluate a polynomial with only n additions and n multiplications. Hence, its storage requirements are n times the number of bits of x.

Horner’s method can be based on the following identity:

Horner's rule

This identity is called Horner’s rule.

To solve the right part of the identity above, for a given x, we start by iterating through the polynomial from the inside out, accumulating each iteration result. After n iterations, with n being the order of the polynomial, the accumulated result gives us the polynomial evaluation. Using the polynomial: 4 x^4 + 2 x^3 + 3 x^2 + x^1 + 3, a traditional approach to evaluate it at x = 2, could be representing it as an array [3, 1, 3, 2, 4] and iterate over it saving each iteration value at an accumulator, such as acc += pow(x=2, index) array[index]. In essence, each power of a number (pow) operation is n-1 multiplications. So, in this scenario, a total of 14 operations would have happened, composed of 4 additions, 5 multiplications, and 5 pows (we’re assuming that each power is calculated by repeated multiplication).

Now, using the same scenario but with Horner’s rule, the polynomial can be re-written as x (x (x (4 x + 2) + 3) + 1) + 3, representing it as [4, 2, 3, 1, 3] it is possible to save the first iteration as acc = arr[0] (x=2) + arr[1], and then finish iterations for acc = (x=2) + arr[index]. In the same scenario but using Horner’s rule, a total of 10 operations would have happened, composed of only 4 additions and 4 multiplications.

nhavantuonglai

Share:
Quay lại.

Có thể bạn chưa đọc

Xem tất cả »
Mở rộng Sitemaps

Mở rộng Sitemaps

Giúp Google và người dùng tìm thấy nội dung website hướng dẫn nâng cao những kỹ thuật giúp tối ưu SEO hiệu quả đem lại thứ hạng tốt trên công…

Tại sao giải pháp cần làm website?

Tại sao giải pháp cần làm website?

Chuỗi bài viết về kiến thức kinh doanh vàng bạc đá quý quỹ ủy thác đầu tư do nhavantuonglai chia sẻ sẽ cung cấp những kiến thức hữu ích giúp…

Đăng ký nhận bảng tin hàng tuần

Liên lạc trao đổi

Liên lạc thông qua Instagram

Thông qua Instagram, bạn có thể trao đổi trực tiếp và tức thời, cũng như cập nhật những thông tin mới nhất từ nhavantuonglai.

Tức thời

Bạn có thể gửi và nhận tin nhắn nhanh chóng, trực tiếp, giúp những vấn đề cá nhân của bạn được giải quyết tức thời và hiệu quả hơn.

Thân thiện

Vì tính chất là kênh liên lạc nhanh, nên bạn có thể bỏ qua những nghi thức giao tiếp thông thường, chỉ cần lịch sự và tôn trọng thì sẽ nhận được sự phản hồi đầy thân thiện, thoải mái từ tác giả.

Trao đổi trên email

Thông qua email cá nhân, bạn có thể trao đổi thỏa thuận hợp tác, kết nối chuyên sâu và mang tính chuyên nghiệp.

Tin cậy

Trong một số trường hợp, email được dùng như một tài liệu pháp lý, chính vì vậy mà bạn có thể an tâm và tin cậy khi trao đổi với tác giả thông qua email.

Chuyên nghiệp

Cấu trúc của email đặt tính chuyên nghiệp lên hàng đầu, nên những thông tin, nội dung được viết trong email từ tác giả sẽ luôn đảm bảo điều này ở mức cao nhất.