Timeline for Computational complexity of calculating the nth root of a real number
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 14, 2012 at 12:26 | vote | accept | aslan | ||
| Jun 13, 2012 at 13:45 | answer | added | Emil Jeřábek | timeline score: 12 | |
| Jun 13, 2012 at 11:05 | answer | added | Feldmann Denis | timeline score: 3 | |
| Jun 13, 2012 at 10:20 | comment | added | Stanislav | If you are interested in the floating point instruction latencies in real processors, see "Intel 64 and IA-32 Architectures Optimization Reference Manual" (Appendix C) | |
| Jun 13, 2012 at 10:17 | comment | added | Stanislav | In the paper of H. Alt, big O notation is used, which is only an asymptotic complexity bound, and it does not mean that the operations are equivalent. In the analysis of high-level algorithms (the book of Jean-Michel Muller), the complexity of multiplication and square root evaluation is assumed the same for simplicity. In real computation, a square root evaluation is about 5 times more expensive than a multiplication. | |
| Jun 13, 2012 at 10:09 | comment | added | aslan | Say single precision floating point real numbers | |
| Jun 13, 2012 at 10:04 | comment | added | Dima Pasechnik | How are your real numbers represented? Without specifying this, it's rather unclear... | |
| Jun 13, 2012 at 9:53 | history | asked | aslan | CC BY-SA 3.0 |