Timeline for The number of possible numeric outcomes of parenthesizations of 2^2^...^2
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 20, 2013 at 22:14 | comment | added | flornquake |
@PeterTaylor, the approach to take into account (a^b)^c = (a^c)^b sound interesting, I wonder if that would work if combined with my approach. Thanks for the bounty.
|
|
| Aug 20, 2013 at 22:11 | history | edited | flornquake | CC BY-SA 3.0 |
added 494 characters in body
|
| Jul 29, 2013 at 15:18 | comment | added | Peter Taylor | @Tobia, we overlapped. I've posted the code. | |
| Jul 29, 2013 at 15:16 | comment | added | Tobia | @PeterTaylor: Edit: As far as I can see, flornquake's algorithm relies on building sets of trees, where a tree is a set of trees itself, and so on. All the pieces of these trees, from the smallest empty set to the largest set of sets, are memoized. This means that all these trees contain "repeated structure" that is only computed once (by the CPU) and stored once (in RAM). Are you sure that your "addition in order" algorithm is identifying all of this repeated structure and computing it once? (what I called exponential complexity above) See also en.wikipedia.org/wiki/Dynamic_programming | |
| Jul 29, 2013 at 11:02 | history | bounty ended | Peter Taylor | ||
| Jul 29, 2013 at 11:02 | comment | added | Peter Taylor |
@Tobia, actually I found that in C# memoising the successor function made it slower. I also found that a more literal translation (using set operations) was significantly slower than my lower level addition. The only real improvement I've found over my original code was to take into account (a^b)^c = (a^c)^b, and it's still much slower than this Python implementation.
|
|
| Jul 27, 2013 at 22:39 | comment | added | Tobia | I haven't profiled @flornquake's (brilliant) code, but I'd assume much of the CPU time is spent doing set membership tests and set manipulation operations, which are both fairly well optimized in Python, using its ubiquitous hash table and hash key routines. Memoization is certainly a big thing, with an exponential algorithm such as this. If you left that out, you can expect exponentially slower performance. | |
| Jul 24, 2013 at 17:42 | comment | added | Peter Taylor | I made a C# translation but using sorted arrays and doing the addition in order rather than by set contains checks. It's much slower, and I haven't yet profiled to see whether that's due to not memoising the successor function or due to the cost of comparisons. | |
| Jul 24, 2013 at 0:13 | history | edited | flornquake | CC BY-SA 3.0 |
added 28 characters in body
|
| Jul 23, 2013 at 22:47 | history | edited | flornquake | CC BY-SA 3.0 |
added 153 characters in body
|
| Jul 23, 2013 at 22:37 | history | edited | flornquake | CC BY-SA 3.0 |
added 124 characters in body
|
| Jul 23, 2013 at 21:29 | history | answered | flornquake | CC BY-SA 3.0 |