Timeline for Square root algorithm
Current License: CC BY-SA 4.0
30 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 5, 2022 at 16:18 | history | edited | YCor | CC BY-SA 4.0 |
removed capitals from title
|
| Jul 8, 2013 at 23:38 | answer | added | Dan Piponi | timeline score: 6 | |
| Jul 8, 2013 at 20:54 | comment | added | François G. Dorais | @Kaveh: Yes, that's the difference. That model makes sense for relative error but not for absolute error. | |
| Jul 8, 2013 at 20:53 | comment | added | Kaveh | In any case, it is not very clear what OP is looking for: just some algorithm to roughly compute the square root or an algorithm to compute the square root accurately up to a given precision $p$. | |
| Jul 8, 2013 at 20:45 | comment | added | Kaveh | @François, that issue is dealt with in computable analysis. See e.g. Ker-I Ko's book "Complexity Theory of Real Functions". Also see this question. | |
| Jul 8, 2013 at 20:43 | comment | added | François G. Dorais | @Kaveh: Presumably yes, but the problem with numerical analysis is that they systematically use floating point arithmetic, so the algorithms used there are good for a given relative error as opposed to a given absolute error. | |
| Jul 8, 2013 at 20:40 | comment | added | Kaveh | @François, not sure I understand. Numerical analysis algorithms work on a larger set of values but they also work on integers. Is the question finding $\lfloor \sqrt{n} \rfloor$ given $n$? | |
| Jul 8, 2013 at 20:35 | comment | added | Will Jagy | @François, I imagine that is correct. It was just amusing. | |
| Jul 8, 2013 at 20:35 | comment | added | François G. Dorais | @Kaveh: The question is specifically about integer square roots, so numerical analysis textbooks wouldn't help much. (Other than explaining the Newton method, which you can also learn in most calculus textbooks.) | |
| Jul 8, 2013 at 20:33 | comment | added | François G. Dorais | @Will: We shouldn't migrate questions to the wrong place, our paths will get shut down. | |
| Jul 8, 2013 at 20:32 | comment | added | Piyush Grover | en.wikipedia.org/wiki/Fast_inverse_square_root might of be (passing) interest. | |
| Jul 8, 2013 at 20:29 | answer | added | Will Jagy | timeline score: 4 | |
| S Jul 8, 2013 at 20:28 | history | edited | user9072 |
adding the tag numerical analysis
|
|
| S Jul 8, 2013 at 20:28 | history | suggested | Kaveh | CC BY-SA 3.0 |
adding the tag numerical analysis
|
| Jul 8, 2013 at 20:23 | comment | added | Kaveh | Have you checked any numerical analysis textbook? | |
| Jul 8, 2013 at 20:21 | review | Suggested edits | |||
| Jul 8, 2013 at 20:28 | |||||
| Jul 8, 2013 at 20:20 | comment | added | Will Jagy | @FrançoisG.Dorais, you have gone mad with power. | |
| Jul 8, 2013 at 20:19 | comment | added | user9072 | As a general reference if this should also be of interest, I would recommend the relevant chapters, in pparticular 1.5, of the recent book of Brent and Zimmermann 'Modern Computer Arithmetic', CUP 2011. For a version close to the published one see loria.fr/~zimmerma/mca/pub226.html | |
| Jul 8, 2013 at 20:11 | comment | added | Aaron Meyerowitz | The first method is quite good and works for any positive real. A more careful $x_0$ will save several steps (perhaps $x_0=d\ 10^n$ where $A$ has $2n$ or $2n+1$ decimal digits and $d$ is a one digit approximation to the square root of the first digit or two). How large are your integers? Do you want an integer answer? rational with small denominator? Floating point? | |
| Jul 8, 2013 at 20:05 | answer | added | François G. Dorais | timeline score: 7 | |
| S Jul 8, 2013 at 19:45 | history | unlocked | François G. Dorais | ||
| S Jul 8, 2013 at 19:45 | history | reopened | François G. Dorais | ||
| Jul 8, 2013 at 19:41 | comment | added | François G. Dorais | Migration to math.se was clearly inappropriate, so I moved it back. | |
| Jul 8, 2013 at 19:40 | comment | added | François G. Dorais | Paul Zimmerman wrote several papers about this. In particular, together with Bertot, Magaud and Zimmerman have formally verified the square root algorithm used in GMP, which is presumably current state of the art. | |
| S Jul 8, 2013 at 19:39 | history | locked | CommunityBot | ||
| S Jul 8, 2013 at 19:39 | history | closed |
Steven Landsburg Will Jagy Andrey Rekalo Misha Andrew Stacey |
Not suitable for this site | |
| Jul 8, 2013 at 19:20 | review | Close votes | |||
| Jul 8, 2013 at 19:40 | |||||
| Jul 8, 2013 at 19:05 | review | First posts | |||
| Jul 8, 2013 at 19:09 | |||||
| Jul 8, 2013 at 19:02 | comment | added | Joe Silverman | Not sure this really qualifies as a research level question, you might be better off posting on MathStackexchage. But a very fast and easy algorithm to compute square root of $A$ to $N$ decimal places for some reasonable $N$ is Newton's algorithm to find a root of $X^2 - A$. So pick an initial $x_0$, say $x_0=A/2$, and then iteratively compute $x_{i+1} = \dfrac{x_i}{2}-\dfrac{A}{2x_i}$. | |
| Jul 8, 2013 at 18:47 | history | asked | Richard Warren | CC BY-SA 3.0 |