Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit21400e3

Browse files
committed
Simplify Horner's Method code and add the link to it in main READMe.
1 parentfb6a1fa commit21400e3

File tree

6 files changed

+68
-32
lines changed

6 files changed

+68
-32
lines changed

‎README.md‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -73,6 +73,7 @@ a set of rules that precisely define a sequence of operations.
7373
*`B`[Complex Number](src/algorithms/math/complex-number) - complex numbers and basic operations with them
7474
*`B`[Radian & Degree](src/algorithms/math/radian) - radians to degree and backwards conversion
7575
*`B`[Fast Powering](src/algorithms/math/fast-powering)
76+
*`B`[Horner's method](src/algorithms/math/horner-method) - polynomial evaluation
7677
*`A`[Integer Partition](src/algorithms/math/integer-partition)
7778
*`A`[Square Root](src/algorithms/math/square-root) - Newton's method
7879
*`A`[Liu Hui π Algorithm](src/algorithms/math/liu-hui) - approximate π calculations based on N-gons
Lines changed: 10 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -1,21 +1,20 @@
11
#Horner's Method
22

3-
In mathematics, Horner's method (or Horner's scheme) is an algorithm for polynomial evaluation.
4-
With this method, it is possible to evaluate a polynomial with only n additions and n multiplications.
5-
Hence, its storage requirements are n times the number of bits of x.
3+
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`.
64

75
Horner's method can be based on the following identity:
8-
![](https://wikimedia.org/api/rest_v1/media/math/render/svg/2a576e42d875496f8b0f0dda5ebff7c2415532e4)
9-
, which is called Horner's rule.
106

11-
To solve the right part of the identity above, for a given x, we start by iterating through the polynomial from the inside out,
12-
accumulating each iteration result. After n iterations, with n being the order of the polynomial, the accumulated result gives
13-
us the polynomial evaluation.
7+
![Horner's rule](https://wikimedia.org/api/rest_v1/media/math/render/svg/2a576e42d875496f8b0f0dda5ebff7c2415532e4)
148

15-
Using the polynomial:
16-
![](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.
9+
This identity is called_Horner's rule_.
10+
11+
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.
12+
13+
**Using the polynomial:**
14+
![Traditional approach](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`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).
15+
16+
Now,**using the same scenario but with Horner's rule**, the polynomial can be re-written as![Horner's rule approach](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`4` additions and`4` multiplications.
1717

18-
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.
1918
##References
2019

2120
-[Wikipedia](https://en.wikipedia.org/wiki/Horner%27s_method)
Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
importclassicPolynomefrom'../classicPolynome';
2+
3+
describe('classicPolynome',()=>{
4+
it('should evaluate the polynomial for the specified value of x correctly',()=>{
5+
expect(classicPolynome([8],0.1)).toBe(8);
6+
expect(classicPolynome([2,4,2,5],0.555)).toBe(7.68400775);
7+
expect(classicPolynome([2,4,2,5],0.75)).toBe(9.59375);
8+
expect(classicPolynome([1,1,1,1,1],1.75)).toBe(20.55078125);
9+
expect(classicPolynome([15,3.5,0,2,1.42,0.41],0.315)).toBe(1.1367300651406251);
10+
expect(classicPolynome([0,0,2.77,1.42,0.41],1.35)).toBe(7.375325000000001);
11+
expect(classicPolynome([0,0,2.77,1.42,2.3311],1.35)).toBe(9.296425000000001);
12+
expect(classicPolynome([2,0,0,5.757,5.31412,12.3213],3.141)).toBe(697.2731167035034);
13+
});
14+
});
Lines changed: 17 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -1,14 +1,21 @@
11
importhornerMethodfrom'../hornerMethod';
2+
importclassicPolynomefrom'../classicPolynome';
23

34
describe('hornerMethod',()=>{
4-
it('should evaluate the polynomialon the specifiedpoint correctly',()=>{
5-
expect(hornerMethod([8],0.1)).toBe(8);
6-
expect(hornerMethod([2,4,2,5],0.555)).toBe(7.68400775);
7-
expect(hornerMethod([2,4,2,5],0.75)).toBe(9.59375);
8-
expect(hornerMethod([1,1,1,1,1],1.75)).toBe(20.55078125);
9-
expect(hornerMethod([15,3.5,0,2,1.42,0.41],0.315)).toBe(1.136730065140625);
10-
expect(hornerMethod([0,0,2.77,1.42,0.41],1.35)).toBe(7.375325000000001);
11-
expect(hornerMethod([0,0,2.77,1.42,2.3311],1.35)).toBe(9.296425000000001);
12-
expect(hornerMethod([2,0,0,5.757,5.31412,12.3213],3.141)).toBe(697.2731167035034);
5+
it('should evaluate the polynomialfor the specifiedvalue of x correctly',()=>{
6+
expect(hornerMethod([8],0.1)).toBe(8);
7+
expect(hornerMethod([2,4,2,5],0.555)).toBe(7.68400775);
8+
expect(hornerMethod([2,4,2,5],0.75)).toBe(9.59375);
9+
expect(hornerMethod([1,1,1,1,1],1.75)).toBe(20.55078125);
10+
expect(hornerMethod([15,3.5,0,2,1.42,0.41],0.315)).toBe(1.136730065140625);
11+
expect(hornerMethod([0,0,2.77,1.42,0.41],1.35)).toBe(7.375325000000001);
12+
expect(hornerMethod([0,0,2.77,1.42,2.3311],1.35)).toBe(9.296425000000001);
13+
expect(hornerMethod([2,0,0,5.757,5.31412,12.3213],3.141)).toBe(697.2731167035034);
1314
});
14-
});
15+
16+
it('should evaluate the same polynomial value as classical approach',()=>{
17+
expect(hornerMethod([8],0.1)).toBe(classicPolynome([8],0.1));
18+
expect(hornerMethod([2,4,2,5],0.555)).toBe(classicPolynome([2,4,2,5],0.555));
19+
expect(hornerMethod([2,4,2,5],0.75)).toBe(classicPolynome([2,4,2,5],0.75));
20+
});
21+
});
Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
/**
2+
* Returns the evaluation of a polynomial function at a certain point.
3+
* Uses straightforward approach with powers.
4+
*
5+
*@param {number[]} coefficients - i.e. [4, 3, 2] for (4 * x^2 + 3 * x + 2)
6+
*@param {number} xVal
7+
*@return {number}
8+
*/
9+
exportdefaultfunctionclassicPolynome(coefficients,xVal){
10+
returncoefficients.reverse().reduce(
11+
(accumulator,currentCoefficient,index)=>{
12+
returnaccumulator+currentCoefficient*(xVal**index);
13+
},
14+
0,
15+
);
16+
}
Lines changed: 10 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -1,17 +1,16 @@
11
/**
22
* Returns the evaluation of a polynomial function at a certain point.
33
* Uses Horner's rule.
4-
*@param {number[]} numbers
4+
*
5+
*@param {number[]} coefficients - i.e. [4, 3, 2] for (4 * x^2 + 3 * x + 2)
6+
*@param {number} xVal
57
*@return {number}
68
*/
7-
exportdefaultfunctionhornerMethod(numbers,point){
8-
// polynomial function is just a constant.
9-
if(numbers.length===1){
10-
returnnumbers[0];
11-
}
12-
returnnumbers.reduce((accumulator,currentValue,index)=>{
13-
returnindex===1
14-
?numbers[0]*point+currentValue
15-
:accumulator*point+currentValue;
16-
});
9+
exportdefaultfunctionhornerMethod(coefficients,xVal){
10+
returncoefficients.reduce(
11+
(accumulator,currentCoefficient)=>{
12+
returnaccumulator*xVal+currentCoefficient;
13+
},
14+
0,
15+
);
1716
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp