Timeline for What tools can help in realizing tail recursion?
Current License: CC BY-SA 3.0
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 23, 2017 at 12:35 | history | edited | CommunityBot |
replaced http://stackoverflow.com/ with https://stackoverflow.com/
|
|
| Apr 11, 2015 at 15:30 | history | edited | Reb.Cabin | CC BY-SA 3.0 |
micro-English corrections
|
| Mar 22, 2013 at 0:08 | comment | added | Leonid Shifrin | @Mr.Wizard I think I tried it and something did not work, but I don't remember for sure. Besides, conceptually, I like the composition idea more, since it clearly states that what I pass is a composition of a previous and current functions. | |
| Mar 21, 2013 at 23:25 | comment | added | Mr.Wizard |
Leonid, is there any reason for using Composition (or composition) in the first place, rather than a pure function? The latter, being more terse, would be my first inclination, and I wouldn't expect it to be slower. I haven't tested it yet however.
|
|
| Mar 21, 2013 at 15:01 | comment | added | Leonid Shifrin | @Mr.Wizard *relevant, sorry. | |
| Mar 21, 2013 at 14:54 | comment | added | Leonid Shifrin | @Mr.Wizard Actually, when comparing the same functions ( addition in both cases), yours is about twice faster (a factor of 2 that I predicted:-)), but for multiplication they are asymptotically the same. Since it was fast to do, I added a relevent section with a fix, explanations, and a benchmark. | |
| Mar 21, 2013 at 14:52 | history | edited | Leonid Shifrin | CC BY-SA 3.0 |
Added a section on speed improvements
|
| Mar 21, 2013 at 14:38 | comment | added | Leonid Shifrin |
@Mr.Wizard Ok, here is a fix. The culprit it Composition with its Flat attribute - this is what leads to a quadratic complexity. Use instead ClearAll[composition]; SetAttributes[composition, HoldAllComplete]; composition[f_, g_][x_] := f[g[x]], and all seems sweet and dandy. In fact, for n = 100000, my new version beats yours 4 times, in my benchmarks.
|
|
| Mar 21, 2013 at 14:28 | comment | added | Leonid Shifrin |
@Mr.Wizard Alas it looks like I completely exhausted my time quota for SE today, so I can't dive into it right now (although I'd really like to). I don't yet know why the complexity is so bad, although I have some thoughts. Will get back to this as soon as I can. But, to rehabilitate a bit, I still think that the main value of the answer is in the concept. When you exceed a critical $RecursionLimit, the kernel will likely crash. With my method, this won't happen. Of course, I agree that performance should be improved for it to be practical, judging from your benchmarks.
|
|
| Mar 21, 2013 at 14:21 | comment | added | Mr.Wizard | Leonid, I added a harsh critique of your method to my answer. You acknowledge "a constant factor of 2 to 10 slower" but I'm afraid the situation is much worse than that. I look forward to your rebuttal. :-) | |
| Mar 21, 2013 at 2:49 | history | edited | Leonid Shifrin | CC BY-SA 3.0 |
Added a link to trampolines
|
| Mar 21, 2013 at 2:40 | comment | added | Leonid Shifrin | @rm-rf If I didn't, I wouldn't be worthy of an attempt, would I? | |
| Mar 21, 2013 at 2:39 | comment | added | rm -rf♦ | @LeonidShifrin Drat! You caught on to my plan to sow seed of tranquility in your head before sneaking up from behind... ;) | |
| Mar 21, 2013 at 2:34 | comment | added | Leonid Shifrin | @rm-rf The biggest threat is to start thinking "it was never in threat" :-) | |
| Mar 21, 2013 at 2:30 | comment | added | RunnyKine | @rm-rf, I know, not even close, just teasing :) | |
| Mar 21, 2013 at 2:29 | comment | added | rm -rf♦ | @RunnyKine It was never in threat :) | |
| Mar 21, 2013 at 2:29 | comment | added | Leonid Shifrin | @RunnyKine Ok, great, I can now go to sleep and have nice dreams of conquering other lands, without a danger of being strangled in my sleep :-) | |
| Mar 21, 2013 at 2:27 | comment | added | RunnyKine | It's safe to say the throne still belongs to you +1, great stuff. But where's the Preamble? :-) | |
| Mar 21, 2013 at 1:56 | history | edited | Leonid Shifrin | CC BY-SA 3.0 |
added 64 characters in body
|
| Mar 21, 2013 at 1:48 | history | answered | Leonid Shifrin | CC BY-SA 3.0 |