How Square Roots Are Calculated

00:00 In the previous lesson, I showed you the sqrt() method in Python’s math library. In this lesson, I’ll show you how these values are calculated. Warning!

00:10 This lesson is a tangent. There’s some heavier math in here. You don’t need to understand any of this to use square roots. The previous lesson showed you enough that you can go and use square roots to your heart’s content. Now, if you’re interested in going down into the details, stay with me! If this stuff makes you yawn, feel free to skip on to the next lesson. You’ve been warned.

00:33 How does Python calculate square roots? Well, Python is written in C and it just passes the buck down. The Python function does a bit of extra work to make sure that Python’s representation of numbers and their boundaries work before calling C, but it pretty much just calls C. Okay, so, how does C do it then? Well, that depends.

00:55 Some processors actually have a square root function built into the CPU. In those cases, C may just call the processor’s instruction directly. If the processor doesn’t have a square root function, then a numerical method is used to calculate, or more correctly, to approximate, the square root.

01:13 One of the most common methods for doing this approximation is based on Newton’s method. Newton’s method is more formerly known as the Newton–Raphson method.

01:24 The reason it has two names? Both of these gents came up with similar concepts around the same time, but the publication of Raphson’s work wasn’t until 50 years after it was written down.

01:35 It was known as Newton’s method until the latter publication showed Raphson’s work predated Newton’s. That being said, both methods are improvements on earlier known methods.

01:45 What can you learn from this? Being first to publish makes all the difference if you want something named after you. The heart of this method is to find the roots of a general polynomial equation.

01:55 That’s the spots where it crosses the x-axis. And the calculation is done through successive approximations. That means a guess is made and a new value is determined based on the guess and then you keep doing that until you get the precision you desire.

02:12 This is the formula for the approximation. It states that the next guess is based on the previous guess minus the function whose roots you’re finding divided by the derivative of that same function.

02:29 You take the result, feed it into the formula again, and keep going until you’ve got the precision you want. You can always check the precision by squaring the result and seeing how close it is to the number you’re square rooting. If they’re identical, you’re done.

02:44 If they’re close enough to each other, you’re done. Otherwise, you keep doing it.

02:51 To apply this method to calculating square roots, you first need a polynomial formula for squares. Here, like you saw in the previous lesson, y is equal to the square of x, and you want to find x.

03:05 By rearranging the formula, you can get a function. If you graphed this, you’d get a parabola, or a horseshoe-like shape. Where the function crosses the x-axis is the roots.

03:17 One root will be negative. -5 times -5 is also 25. And the other root will be positive. The value of y in this function shifts the horseshoe shape, changing where the function crosses the axis. Now that you’ve got a function, the only other thing you need is the derivative of the function.

03:38 If you haven’t done any calculus before, just take my word at this. If you have done calculus, you were probably way ahead of me. This is one of the first ones you tend to learn. Taking the function and its derivatives then plugging them into the formula for Newton’s method from the previous screen, and you get this lovely little bunch of symbols.

03:58 You got that? On the next slide, I’ll simplify it a little bit.

04:03 Starting with that same formula, rewriting x sub n as a fraction with the same base as the right-hand side. Now collecting the terms,

04:16 subtracting what is in the brackets gives you 2 x squared minus x squared plus y. Doing the subtraction on the square terms, and splitting the fraction back up and pulling out the 1/2.

04:32 Or, in other words, your next guess is 1/2 times your current guess plus your initial guess, divided by the current guess. Let’s jump into some code with this formula.

04:47 Inside of newton.py, I’ve implemented my own square root function. On line 2, I’ve declared a constant that specifies the amount of precision to use.

04:58 This is 10 decimal points of precision. Line 8 is the formula from the previous slide, calculating the new value for the guess based on the previous value plus the original guess over the current guess, then all divided by 2, which is the same as multiplying by 1/2.

05:17 Line 8 is inside of a while loop that keeps going until the precision condition is met. The precision condition is based on the value being found, y, minus the square of the guess.

05:29 If the difference between those two is less than our tiny PRECISION constant, then you’re done! On line 5, you’ll find the initial guess. To keep things simple, the initial guess is just the value being square rooted.

05:43 To show you how this iterates, I’ve included a print statement with progress on line 9. Let’s give this a whirl. Importing the function,

05:57 calling it with 25, and eight iterations later, you get the right answer. Let’s do it with 36,

06:08 and now 30.

06:12 The end result is the same value as the built-in method. Of course, this won’t be anywhere near as fast as calling compiled libraries inside of Python, but now you know how it works.

06:24 Next up, I’ll show you a practical use of roots in your code.