Timeline for What is the fastest way to count square-free words?
Current License: CC BY-SA 3.0
27 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 3, 2012 at 20:26 | comment | added | Daniel Lichtblau | After some reading and more thought I've come to a few conclusions. (1) I did not earn the bounty. Can I return it (or at least a part of it)? (2) Memory remains a consireable impediment. Even with one bit per character (can be done, since preceding bit forces next bit to two possibilities) it still seems likely to require out-of-core methods. (3) Quick square free testing remains elusive. I have yet to figure out a viable subquadratic test. The one I last described may well be subquadratic on average but that's about the best I'd claim for it. This has been, all in all, quite a chase. | |
| Aug 30, 2012 at 22:02 | history | bounty ended | CommunityBot | ||
| Aug 30, 2012 at 15:43 | history | edited | Daniel Lichtblau | CC BY-SA 3.0 |
outlines various improvements
|
| Aug 29, 2012 at 21:20 | comment | added | Daniel Lichtblau | Sorry, cut-and-paste error (I took the wrong one). I just fixed it in the code section above. Need to either change Leonid's code to return True/False, or else change my usage (which is what I just did) to check squareFreeQLSC[newwd] == 0. | |
| Aug 29, 2012 at 21:18 | history | edited | Daniel Lichtblau | CC BY-SA 3.0 |
code fix
|
| Aug 29, 2012 at 21:08 | comment | added | M.R. | When I run AbsoluteTiming[sf = squareFreeTernaryWordsC[55];] CompiledFunction::cflist: Nontensor object generated; proceeding with uncompiled evaluation. >> | |
| Aug 29, 2012 at 20:24 | history | edited | Daniel Lichtblau | CC BY-SA 3.0 |
compiled code added, with a speed test
|
| Aug 29, 2012 at 20:18 | comment | added | Daniel Lichtblau | I had originally thought of doing this as a tree in the usual structred sense. Decided against it when I realized I could save both time and memory laying it out the way I did. That leaves open the problem of recovering individual words by walking the "tree" (that is, the set of integer arrays I use that represents a tree). | |
| Aug 29, 2012 at 20:16 | comment | added | Daniel Lichtblau | Actually what I wrote emulates a tree. The jth entry in allwds contains the children of the element list (that is, word) formed by traversal to j-1 (so the parent word has length j-1). Each value is between 0 and 7, and indicates which new elements (if any) can follow that word to get a longer square free word. I'll make related comment separately. | |
| Aug 29, 2012 at 20:06 | comment | added | M.R. | For maximal compression, instead of a list of words, we should be using a tree. Does anyone know if there any Internal` tree implementations that are packed and quickly traversable? | |
| Aug 29, 2012 at 19:26 | history | edited | M.R. | CC BY-SA 3.0 |
attempted parallelization
|
| Aug 29, 2012 at 13:52 | history | edited | Daniel Lichtblau | CC BY-SA 3.0 |
code fix and format
|
| Aug 29, 2012 at 13:40 | history | edited | Daniel Lichtblau | CC BY-SA 3.0 |
changed storage of intermediate results to something better suited to the problem
|
| Aug 29, 2012 at 4:28 | history | edited | Daniel Lichtblau | CC BY-SA 3.0 |
typo
|
| Aug 29, 2012 at 4:15 | history | edited | rm -rf♦ | CC BY-SA 3.0 |
added 118 characters in body
|
| Aug 29, 2012 at 4:15 | vote | accept | M.R. | ||
| Aug 29, 2012 at 3:48 | comment | added | Daniel Lichtblau | @Mike Not sure how far it will go, but I added enumeration code. | |
| Aug 29, 2012 at 3:48 | history | edited | Daniel Lichtblau | CC BY-SA 3.0 |
added code to enumerate sq-free ternary words
|
| Aug 28, 2012 at 5:06 | comment | added | M.R. | If you can get past 70 with this method, I'll award the points now. | |
| Aug 27, 2012 at 19:05 | comment | added | M.R. | The difficulty in enumeration is memory, the list becomes so long that Mathematica dies around n=63. | |
| Aug 27, 2012 at 14:19 | comment | added | Daniel Lichtblau | @Verde Thanks, good idea. I thought that would not help because "InlineExternalDefinitions" should just slurp in the definition (or so I thought). Also adding those options gave an ominous error message "Compile::nogen: A library could not be generated from the compiled function. >>" But it works anyway, and around 5x faster than what I had. Fascinating. (And a nice addition to my level of ignorance). | |
| Aug 27, 2012 at 3:42 | comment | added | Dr. belisarius |
Perhaps if you add , RuntimeOptions -> "Speed", CompilationTarget -> "C" to your notSqrFreeAtTail :D
|
|
| Aug 24, 2012 at 15:38 | history | edited | Daniel Lichtblau | CC BY-SA 3.0 |
complexity remarks
|
| Aug 24, 2012 at 14:30 | history | edited | Daniel Lichtblau | CC BY-SA 3.0 |
small change
|
| Aug 24, 2012 at 14:28 | comment | added | Daniel Lichtblau | Enumerating can be done roughly the same way. At each step where you add an element to an existing sq-free word, you have to check all subwords up to floor(half length of list) that end at this new element with the corresponding subwords to the left. | |
| Aug 24, 2012 at 9:56 | comment | added | M.R. | Correct, I want to count them. | |
| Aug 23, 2012 at 23:49 | history | answered | Daniel Lichtblau | CC BY-SA 3.0 |