Add Horner's Method (trekhleb#575)

MatheusBonavite · matheus · web-flow · commit fb6a1fae0a04 · 2020-12-08T08:59:32.000+01:00
* Add Horner's Method

* Update README.md

Co-authored-by: matheus &lt;matheus.cardoso@sydle.com&gt;
diff --git a/src/algorithms/math/horner-method/README.md b/src/algorithms/math/horner-method/README.md
@@ -0,0 +1,21 @@
+# Horner's Method
+
+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:
+![](https://wikimedia.org/api/rest_v1/media/math/render/svg/2a576e42d875496f8b0f0dda5ebff7c2415532e4)
+, which 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:
+![](http://www.sciweavers.org/tex2img.php?eq=%244x%5E4%20%2B%202x%5E3%20%2B%203x%5E2%2B%20x%5E1%20%2B%203%24&bc=White&fc=Black&im=jpg&fs=12&ff=arev&edit=0), 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 15 operations would have happened, composed of 5 additions, 5 multiplications, and 5 pows.
+
+Now, using the same scenario but with Horner's rule, the polynomial can be re-written as ![](http://www.sciweavers.org/tex2img.php?eq=%24x%28x%28x%284x%2B2%29%2B3%29%2B1%29%2B3%24&bc=White&fc=Black&im=jpg&fs=12&ff=arev&edit=0), 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 5 additions and 5 multiplications.
+## References
+
+- [Wikipedia](https://en.wikipedia.org/wiki/Horner%27s_method)
diff --git a/src/algorithms/math/horner-method/__test__/hornerMethod.test.js b/src/algorithms/math/horner-method/__test__/hornerMethod.test.js
@@ -0,0 +1,14 @@
+import hornerMethod from '../hornerMethod';
+
+describe('hornerMethod', () => {
+  it('should evaluate the polynomial on the specified point correctly', () => {
+    expect(hornerMethod([8],0.1)).toBe(8);
+    expect(hornerMethod([2,4,2,5],0.555)).toBe(7.68400775);
+    expect(hornerMethod([2,4,2,5],0.75)).toBe(9.59375);
+    expect(hornerMethod([1,1,1,1,1],1.75)).toBe(20.55078125);
+    expect(hornerMethod([15,3.5,0,2,1.42,0.41],0.315)).toBe(1.136730065140625);
+    expect(hornerMethod([0,0,2.77,1.42,0.41],1.35)).toBe(7.375325000000001);
+    expect(hornerMethod([0,0,2.77,1.42,2.3311],1.35)).toBe(9.296425000000001);
+    expect(hornerMethod([2,0,0,5.757,5.31412,12.3213],3.141)).toBe(697.2731167035034);
+  });
+});
diff --git a/src/algorithms/math/horner-method/hornerMethod.js b/src/algorithms/math/horner-method/hornerMethod.js
@@ -0,0 +1,17 @@
+/**
+ * Returns the evaluation of a polynomial function at a certain point.
+ * Uses Horner's rule.
+ * @param {number[]} numbers
+ * @return {number}
+ */
+export default function hornerMethod(numbers, point) {
+  // polynomial function is just a constant.
+  if (numbers.length === 1) {
+    return numbers[0];
+  }
+  return numbers.reduce((accumulator, currentValue, index) => {
+    return index === 1
+      ? numbers[0] * point + currentValue
+      : accumulator * point + currentValue;
+  });
+}
