Timeline for Can you tell if you have escaped from a recursive definition?
Current License: CC BY-SA 2.5
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 28, 2010 at 5:18 | vote | accept | S. Donovan | ||
| Mar 28, 2010 at 5:17 | comment | added | S. Donovan | The paper you posted is on the question I was trying to ask. | |
| Mar 28, 2010 at 5:05 | comment | added | Joel David Hamkins | Qiaochu, I think the question is not about the particular examples. Rather, the question (which I voted up), is about how in general are we to compare various methods of computing the same function? One very robust way, which I explain in my answer, is to use the measures of computational complexity. | |
| Mar 28, 2010 at 4:04 | comment | added | Qiaochu Yuan | The last example you give has the same problem: factorials are themselves defined by a recursion. While it's useful to know that it's easy to approximate the size of a factorial, if you know a way to compute large factorials exactly and quickly then you can use Wilson's theorem as a primality test, and nobody has been able to do this (yet). | |
| Mar 28, 2010 at 3:56 | answer | added | Qiaochu Yuan | timeline score: 5 | |
| Mar 28, 2010 at 3:52 | history | edited | S. Donovan | CC BY-SA 2.5 |
added 173 characters in body
|
| Mar 28, 2010 at 3:50 | answer | added | Joel David Hamkins | timeline score: 8 | |
| Mar 28, 2010 at 3:46 | comment | added | Qiaochu Yuan | The Fibonacci example is a bad one. The "naive" way of computing the power of something is to multiply it by itself over and over again, which is just a hidden form of the Fibonacci recursion if you do it exactly and requires you to compute a lot of digits of phi if you don't do it exactly. A much better algorithm to compute large Fibonacci numbers is to use a variant of binary exponentiation, which is still essentially recursive but only requires that you compute logarithmically many previous Fibonacci numbers. | |
| Mar 28, 2010 at 3:15 | history | edited | S. Donovan | CC BY-SA 2.5 |
added 957 characters in body; added 1 characters in body
|
| Mar 28, 2010 at 3:02 | answer | added | Jacques Carette | timeline score: 2 | |
| Mar 28, 2010 at 2:54 | comment | added | Jacques Carette | Your question is much too vague. Can you give an actual example? | |
| Mar 28, 2010 at 2:50 | history | asked | S. Donovan | CC BY-SA 2.5 |