Discussion Overview
The discussion revolves around methods and complexity for computing square roots, specifically focusing on the computational cost in big O notation and the algorithms commonly used in computers and calculators. Participants explore various algorithms and their complexities, including Newton's method and a long division-like algorithm.
Discussion Character
- Exploratory
- Technical explanation
- Debate/contested
- Mathematical reasoning
Main Points Raised
- Yiorgos inquires about the computational cost of calculating sqrt(x) in big O notation, where x is an integer of n digits.
- Some participants suggest that Newton's method is commonly used for finding square roots, although it is not confirmed as the most prevalent method.
- Another participant mentions an algorithm resembling long division for square roots, suggesting it has a similar time complexity to long division.
- There is a request for the computational cost of Newton's method, specifically in relation to the number of digits in the result.
- A participant proposes calculating sqrt(2) to n-digits precision as a simpler starting point for understanding complexity.
Areas of Agreement / Disagreement
Participants express differing views on the most commonly used algorithm for computing square roots and the associated complexities. No consensus is reached regarding the exact computational costs or the best method to use.
Contextual Notes
The discussion includes assumptions about the number of digits in the result and the nature of the input (e.g., whether A is a square of an integer). The complexity of Newton's method is not fully resolved, and the implications of precision in calculations are noted but not detailed.
Who May Find This Useful
Individuals interested in numerical methods, algorithm complexity, and computational mathematics may find this discussion relevant.