[Non-obvious algorithms of obvious things] Algorithm 1. Square root
A series of posts [Unobvious algorithms of obvious things] will contain action algorithms that seem obvious and simple, but if you ask yourself the question “how is this done?”, The answer is far from obvious. Of course, all these algorithms can be found in the literature. Under the cat is the algorithm for calculating the root of the square number X.
A rectangle is formed with sides a = 1 and b = X. The area of this rectangle is S = a * b = X * 1 = X. Transforming the rectangle into a square so that its area remains the same, we get the side length equal to the square root of the area of the figure, which is equal to X.
Each iteration of converting a rectangle into a square is performed as follows:
S = a 0 b 0 ;
A new quadrilateral is created, which has one side equal to the arithmetic average of the sides of the current rectangle, but the area is the same:
S = a 1 b 1 , where a 1 = (a 0 + b 0 ) / 2, and b 1 = S / a 1
S = a 2 b 2 , where a 2 = (a 1 + b 1 ) / 2, and b 2 = S / a 2
...
S = a n b n , where a n = (a n-1 + b n-1 ) / 2, and b n = S / a n
And so on until | a n -b n | <Eps.
')
Root square number X
Idea
A rectangle is formed with sides a = 1 and b = X. The area of this rectangle is S = a * b = X * 1 = X. Transforming the rectangle into a square so that its area remains the same, we get the side length equal to the square root of the area of the figure, which is equal to X.
Each iteration of converting a rectangle into a square is performed as follows:
S = a 0 b 0 ;
A new quadrilateral is created, which has one side equal to the arithmetic average of the sides of the current rectangle, but the area is the same:
S = a 1 b 1 , where a 1 = (a 0 + b 0 ) / 2, and b 1 = S / a 1
S = a 2 b 2 , where a 2 = (a 1 + b 1 ) / 2, and b 2 = S / a 2
...
S = a n b n , where a n = (a n-1 + b n-1 ) / 2, and b n = S / a n
And so on until | a n -b n | <Eps.
Function code
#define EPS 1e-10 float my_sqrt(float x){ float S=x, a=1,b=x; while(fabs(ab)>EPS){ a=(a+b)/2; b = S / a;} return (a+b)/2; } ')
Source: https://habr.com/ru/post/128468/
All Articles