-
Notifications
You must be signed in to change notification settings - Fork 5
/
Copy pathindex.html
37 lines (34 loc) · 3.82 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
<html>
<head>
<title>Sqrt</title>
<style>
@font-face {
font-family: 'LibreBaskerville';
src: url('fonts/LibreBaskerville-Regular.ttf') format('truetype');
}
</style>
<link rel="stylesheet" href="css/reset.css"/>
<link rel="stylesheet" href="css/index.css"/>
</head>
<body>
<h1>Sqrt() Algorithms Visualization</h1>
<div class='author'><a href="https://github.com/rexim" target="_blank">Author: Alexey Kutepov</a></div>
<p>Here I keep a collection of visualizations for algorithms that compute <a href="https://en.wikipedia.org/wiki/Square_root">Square root</a> as I experiment with them. This page is presented as is and does not claim to be a complete guide on such algorithms. You can find the source code at <a href="https://github.com/tsoding/dumb-sqrt">GitHub</a></p>
<h2 id="binary-search"><a href="#binary-search">Binary Search (Very Dumb)</a></h2>
<p>I came up with this algorithm myself based on my understanding of the square root definition. If you have <code>y</code> it is very easy to check if it is a square root of <code>x</code>. You just check if <code>y*y == x</code>.</p>
<p>So the algorithm starts with defining two values: <code>y0 = 0</code> and <code>y1 = x</code>. The value <code>sqrt(x)</code> lies somewhere between <code>y0</code> and <code>y1</code>. We simply perform <a href="https://en.wikipedia.org/wiki/Binary_search_algorithm">Binary search</a> on them until we narrow down <code>y0</code> and <code>y1</code> to <code>y == sqrt(x)</code> with an acceptable precision.</p>
<p>Very slow algorithm but it works and was fun to implement and animate.</p>
<canvas id="app-binary-search" class="plot" width="1600" height="800"></canvas>
<p>Click the plot to set the <code>x</code> value.</p>
<h2 id="newton-method"><a href="#newton-method">Newton's Method</a></h2>
<p>The algorithm based on <a href="https://en.wikipedia.org/wiki/Newton%27s_method">Newton's method</a> is much more efficient and actually really clever. The thing about Newton's method is that it's not designed specifically for finding square roots. It's a method that finds roots of any function. (the root of a function <code>f</code> is a such value <code>x</code> that <code>f(x) == 0</code>)</p>
<p>So what you need to do given a value <code>a</code> the square root of which you want to find is to come up with such function <code>f</code> the root of which is equal to <code>sqrt(a)</code>. That is <code>f(sqrt(a)) == 0</code>. A good instance of such function would be <code>f(x) = x^2 - a</code>. Once you've got such function you just need to apply the Newton's method on it and voilà! You found <code>sqrt(a)</code>.</p>
<p>The idea of Newton's method is really simple. You start with a certain approximation <code>x[0]</code>. And you keep computing the next approximation <code>x[i] = x[i-1] - f(x[i-1])/f'(x[i-1])</code> iteratively until you've reached an acceptable precision. <code>f'(x)</code> is the first derivative of function <code>f(x)</code>.</p>
<p>Since the derivative of a function is basically the velocity of that function at a certain point by dividing by it and subtracting it we sort of move in an opposite direction trying to reach the zero. But I personally do not fully understand how it works yet.</p>
<p>In case of the function <code>f(x) = x^2 - a</code> the next approximation looks like <code>x[i] = x[i-1] - (x[i-1]^2 - a)/(2*x[i-1])</code>.</p>
<canvas id="app-newton-method" class="plot" width="1600" height="800"></canvas>
<p>Click the plot to set the <code>x</code> value.</p>
<p>Source Code on <a href="https://github.com/tsoding/dumb-sqrt" target="_blank">GitHub</a> | Font <a href="https://github.com/impallari/Libre-Baskerville" target="_blank">Libre Baskerville</a></p>
<script src="index.js"></script>
</body>
</html>