Lecture 12: Square Roots, Newton's Method

TL;DR

The complexity of computing square roots using the Newton's method is similar to that of multiplication.

Transcript

The following content is provided under a Creative Commons license. Your support will help MIT OpenCourseWare continue to offer high quality educational resources for free. To make a donation or view additional materials from hundreds of MIT courses, visit MIT OpenCourseWare at ocw.mit.edu. PROFESSOR: Good morning everyone. Morning. Let's get start... Read More

Key Insights

• 🫚 Newton's method is a useful iterative algorithm for computing square roots and can be extended to other numerical computations.
• 💗 The complexity of division in computing square roots is comparable to that of multiplication due to the growing number of digits of precision.
• 🫚 There are more efficient multiplication algorithms, such as Karatsuba and Toom-Cook, which can be used to improve the efficiency of computing square roots.

Questions & Answers

Q: What is the motivation behind finding the millionth digit of the square root of 2?

The motivation is to understand the algorithmic complexity of computing square roots and explore the intricacies of high-precision arithmetic.

Q: How does Newton's method work in computing square roots?

Newton's method is an iterative approach that uses an initial guess and improves it through each iteration. In the case of computing square roots, the algorithm iteratively updates the guess based on the previous guess and the number being squared.

Q: How does the complexity of division compare to multiplication in computing square roots?

The complexity of division in computing square roots is comparable to that of multiplication because the numbers involved start with a small number of digits of precision and grow as the iterations progress. The majority of the work is done when the number of digits is large.

Q: Are there more efficient algorithms than Newton's method for computing square roots?

Yes, there are more efficient algorithms, such as Schonhage-Strassen or Furer algorithm, that have better complexity than Newton's method for multiplication and can be applied to improve the computation of square roots.

Summary & Key Takeaways

• The lecture focuses on the computation of the square root of a number using numerical analysis techniques.

• The professor explains the use of high-precision arithmetic, Newton's method, and division algorithm in this computation.

• The complexity of computing square roots is determined by the complexity of multiplication, which is determined by the chosen multiplication algorithm.