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

Commit339ae02

Browse files
committed
Add square root finding algorithm.
1 parent4aecd57 commit339ae02

File tree

4 files changed

+172
-0
lines changed

4 files changed

+172
-0
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`[Radian & Degree](src/algorithms/math/radian) - radians to degree and backwards conversion
7474
*`B`[Fast Powering](src/algorithms/math/fast-powering)
7575
*`A`[Integer Partition](src/algorithms/math/integer-partition)
76+
*`A`[Square Root](src/algorithms/math/square-root) - Newton's method
7677
*`A`[Liu Hui π Algorithm](src/algorithms/math/liu-hui) - approximate π calculations based on N-gons
7778
*`A`[Discrete Fourier Transform](src/algorithms/math/fourier-transform) - decompose a function of time (a signal) into the frequencies that make it up
7879
***Sets**
Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,62 @@
1+
#Square Root (Newton's Method)
2+
3+
In numerical analysis, a branch of mathematics, there are several square root
4+
algorithms or methods of computing the principal square root of a non-negative real
5+
number. As, generally, the roots of a function cannot be computed exactly.
6+
The root-finding algorithms provide approximations to roots expressed as floating
7+
point numbers.
8+
9+
Finding![](https://wikimedia.org/api/rest_v1/media/math/render/svg/bff86975b0e7944720b3e635c53c22c032a7a6f1) is
10+
the same as solving the equation![](https://wikimedia.org/api/rest_v1/media/math/render/svg/6cf57722151ef19ba1ca918d702b95c335e21cad) for a
11+
positive`x`. Therefore, any general numerical root-finding algorithm can be used.
12+
13+
**Newton's method** (also known as the Newton–Raphson method), named after
14+
_Isaac Newton_ and_Joseph Raphson_, is one example of a root-finding algorithm. It is a
15+
method for finding successively better approximations to the roots of a real-valued function.
16+
17+
Let's start by explaining the general idea of Newton's method and then apply it to our particular
18+
case with finding a square root of the number.
19+
20+
##Newton's Method General Idea
21+
22+
The Newton–Raphson method in one variable is implemented as follows:
23+
24+
The method starts with a function`f` defined over the real numbers`x`, the function's derivative`f'`, and an
25+
initial guess`x0` for a root of the function`f`. If the function satisfies the assumptions made in the derivation
26+
of the formula and the initial guess is close, then a better approximation`x1` is:
27+
28+
![](https://wikimedia.org/api/rest_v1/media/math/render/svg/52c50eca0b7c4d64ef2fdca678665b73e944cb84)
29+
30+
Geometrically,`(x1, 0)` is the intersection of the`x`-axis and the tangent of
31+
the graph of`f` at`(x0, f (x0))`.
32+
33+
The process is repeated as:
34+
35+
![](https://wikimedia.org/api/rest_v1/media/math/render/svg/710c11b9ec4568d1cfff49b7c7d41e0a7829a736)
36+
37+
until a sufficiently accurate value is reached.
38+
39+
![](https://upload.wikimedia.org/wikipedia/commons/e/e0/NewtonIteration_Ani.gif)
40+
41+
##Newton's Method of Finding a Square Root
42+
43+
As it was mentioned above, finding![](https://wikimedia.org/api/rest_v1/media/math/render/svg/bff86975b0e7944720b3e635c53c22c032a7a6f1) is
44+
the same as solving the equation![](https://wikimedia.org/api/rest_v1/media/math/render/svg/6cf57722151ef19ba1ca918d702b95c335e21cad) for a
45+
positive`x`.
46+
47+
The derivative of the function`f(x)` in case of square root problem is`2x`.
48+
49+
After applying the Newton's formula (see above) we get the following equation for our algorithm iterations:
50+
51+
```text
52+
x := x - (x² - S) / (2x)
53+
```
54+
55+
The`x² − S` above is how far away`x²` is from where it needs to be, and the
56+
division by`2x` is the derivative of`x²`, to scale how much we adjust`x` by how
57+
quickly`x²` is changing.
58+
59+
##References
60+
61+
-[Methods of computing square roots on Wikipedia](https://en.wikipedia.org/wiki/Methods_of_computing_square_roots)
62+
-[Newton's method on Wikipedia](https://en.wikipedia.org/wiki/Newton%27s_method)
Lines changed: 69 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,69 @@
1+
importsquareRootfrom'../squareRoot';
2+
3+
describe('squareRoot',()=>{
4+
it('should throw for negative numbers',()=>{
5+
functionfailingSquareRoot(){
6+
squareRoot(-5);
7+
}
8+
expect(failingSquareRoot).toThrow();
9+
});
10+
11+
it('should correctly calculate square root with default tolerance',()=>{
12+
expect(squareRoot(0)).toBe(0);
13+
expect(squareRoot(1)).toBe(1);
14+
expect(squareRoot(2)).toBe(1);
15+
expect(squareRoot(3)).toBe(2);
16+
expect(squareRoot(4)).toBe(2);
17+
expect(squareRoot(15)).toBe(4);
18+
expect(squareRoot(16)).toBe(4);
19+
expect(squareRoot(256)).toBe(16);
20+
expect(squareRoot(473)).toBe(22);
21+
expect(squareRoot(14723)).toBe(121);
22+
});
23+
24+
it('should correctly calculate square root for integers with custom tolerance',()=>{
25+
lettolerance=1;
26+
27+
expect(squareRoot(0,tolerance)).toBe(0);
28+
expect(squareRoot(1,tolerance)).toBe(1);
29+
expect(squareRoot(2,tolerance)).toBe(1.4);
30+
expect(squareRoot(3,tolerance)).toBe(1.8);
31+
expect(squareRoot(4,tolerance)).toBe(2);
32+
expect(squareRoot(15,tolerance)).toBe(3.9);
33+
expect(squareRoot(16,tolerance)).toBe(4);
34+
expect(squareRoot(256,tolerance)).toBe(16);
35+
expect(squareRoot(473,tolerance)).toBe(21.7);
36+
expect(squareRoot(14723,tolerance)).toBe(121.3);
37+
38+
tolerance=3;
39+
40+
expect(squareRoot(0,tolerance)).toBe(0);
41+
expect(squareRoot(1,tolerance)).toBe(1);
42+
expect(squareRoot(2,tolerance)).toBe(1.414);
43+
expect(squareRoot(3,tolerance)).toBe(1.732);
44+
expect(squareRoot(4,tolerance)).toBe(2);
45+
expect(squareRoot(15,tolerance)).toBe(3.873);
46+
expect(squareRoot(16,tolerance)).toBe(4);
47+
expect(squareRoot(256,tolerance)).toBe(16);
48+
expect(squareRoot(473,tolerance)).toBe(21.749);
49+
expect(squareRoot(14723,tolerance)).toBe(121.338);
50+
51+
tolerance=10;
52+
53+
expect(squareRoot(0,tolerance)).toBe(0);
54+
expect(squareRoot(1,tolerance)).toBe(1);
55+
expect(squareRoot(2,tolerance)).toBe(1.4142135624);
56+
expect(squareRoot(3,tolerance)).toBe(1.7320508076);
57+
expect(squareRoot(4,tolerance)).toBe(2);
58+
expect(squareRoot(15,tolerance)).toBe(3.8729833462);
59+
expect(squareRoot(16,tolerance)).toBe(4);
60+
expect(squareRoot(256,tolerance)).toBe(16);
61+
expect(squareRoot(473,tolerance)).toBe(21.7485631709);
62+
expect(squareRoot(14723,tolerance)).toBe(121.3383698588);
63+
});
64+
65+
it('should correctly calculate square root for integers with custom tolerance',()=>{
66+
expect(squareRoot(4.5,10)).toBe(2.1213203436);
67+
expect(squareRoot(217.534,10)).toBe(14.7490338667);
68+
});
69+
});
Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
/**
2+
* Calculates the square root of the number with given tolerance (precision)
3+
* by using Newton's method.
4+
*
5+
*@param number - the number we want to find a square root for.
6+
*@param [tolerance] - how many precise numbers after the floating point we want to get.
7+
*@return {number}
8+
*/
9+
exportdefaultfunctionsquareRoot(number,tolerance=0){
10+
// For now we won't support operations that involves manipulation with complex numbers.
11+
if(number<0){
12+
thrownewError('The method supports only positive integers');
13+
}
14+
15+
// Handle edge case with finding the square root of zero.
16+
if(number===0){
17+
return0;
18+
}
19+
20+
// We will start approximation from value 1.
21+
letroot=1;
22+
23+
// Delta is a desired distance between the number and the square of the root.
24+
// - if tolerance=0 then delta=1
25+
// - if tolerance=1 then delta=0.1
26+
// - if tolerance=2 then delta=0.01
27+
// - and so on...
28+
constrequiredDelta=1/(10**tolerance);
29+
30+
// Approximating the root value to the point when we get a desired precision.
31+
while(Math.abs(number-(root**2))>requiredDelta){
32+
// Newton's method reduces in this case to the so-called Babylonian method.
33+
// These methods generally yield approximate results, but can be made arbitrarily
34+
// precise by increasing the number of calculation steps.
35+
root-=((root**2)-number)/(2*root);
36+
}
37+
38+
// Cut off undesired floating digits and return the root value.
39+
returnMath.round(root*(10**tolerance))/(10**tolerance);
40+
}

0 commit comments

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