flat assembler
Message board for the users of flat assembler. Index > Main > Mystery Sequence Contest Goto page 1, 2  Next
Author
 Thread  bitRAKE Joined: 21 Jul 2003 Posts: 3844 Location: vpcmipstrm bitRAKE 01 Aug 2009, 05:52 We explore another self-generating sequence with prefix bits in common across terms. Looking for smallest code fragments generating a range of terms. I have rediscovered this one many times. This sequence has many interesting properties. What can you discover? A perspective I like to entertain is one of the limit T(infinity), and imagine the result as a field. Instead of clearing or setting memory another field can be applied. In the case of Thue-Morse it is rather easy to query any point in the field without actually generating the field - it's the bit index parity. What is required to do the same with this sequence? How can this sequence be expanded into higher-dimensions? T0 = 0 T1 = 01 T2 = 010 T3 = 01001 T4 = 01001010 T5 = 0100101001001 T6 = 010010100100101001010 T7 = 0100101001001010010100100101001001 T8 = 0100101001001010010100100101001001010010100100101001010 Dynamic winner categories created by participation: processor mode (16-bit, 32-bit, 64-bit), supported range, and output format: Code:``` Author Format Code T-Range Bytes Notes Madis731 ASCII 64-bit 2 - 43 34 range 89 with 64-bit registers and sufficient memory. ``` _________________¯\(°_o)/¯ The hardcore cynic mistakes good for guile.Last edited by bitRAKE on 06 Aug 2009, 02:01; edited 2 times in total 01 Aug 2009, 05:52
 MHajduk Joined: 30 Mar 2006 Posts: 6110 Location: Poland MHajduk 01 Aug 2009, 19:11 Hi, bitRAKE! Let us define this sequence of strings made of 0 and 1 symbols by simple recursion: Code:```T(0) = 0 T(1) = 01 T(n) = T(n-1)T(n-2) for every natural number n >= 2 ```Every term T(n) of the sequence T for n >= 2 is defined as a concatenation of preceding two terms (which are strings). First, rather obvious, feature, which we can notice is that for every even n last character of the T(n) is 0 and for every odd n last character of T(n) is 1. It could be proved by induction as follows: For the first two terms of this sequence it's obvious. Let our assumption will be true for every natural k which are less than or equal some natural n>=1. We'll prove that then it would be true also for n+1. If n+1 is even, then it could be denoted as 2m for some natural m. We have Code:`T(n+1) = T(n+1-1)T(n+1-2) = T(2m-1)T(2m-2) `But, from our assumption, T(2m-2) has the last character equal to 0 (2m-2 is an even number less than n = 2m-1). If n+1 is odd, then it could be denoted as 2m+1 for some natural m. We have Code:`T(n+1) = T(n+1-1)T(n+1-2) = T(2m+1-1)T(2m+1-2) = T(2m)T(2m-1) `But 2m-1 is an odd number less than n = 2m and, from the given assumption, T(2m-1) has the last character equal to 1.  01 Aug 2009, 19:11
 MHajduk Joined: 30 Mar 2006 Posts: 6110 Location: Poland MHajduk 01 Aug 2009, 19:52 Next almost obvious feature. There doesn't exist term of the sequence which has substring made of 1 with length greater than 1. This also could be proved by induction as follows:For T(0) and T(1) it's obvious. Let our assumption will be true for every natural k less than or equal some natural n>=1. We'll prove that it would be also true for n+1. We have Code:`T(n+1) = T(n+1-1)T(n+1-2) = T(n)T(n-1) `There is only one place in the T(n+1) string where 1 symbols could be duplicated: place where ending symbol of the T(n) is a neighbor of the first symbol of T(n-1). But, from the obvious fact, starting symbol of every term of the T sequence is 0, hence newly created string also fulfills our assumption.We can also prove this way another simple fact: there doesn't exist substring made of 0 with length greater than 2 (we can prove that if we observe that every term T(n) for n>=1 starts from the sequence 01 and there doesn't exist term which can have other ending sequence than 01 or 10 [for n>=1]). BTW, what do you exactly mean by this bitRAKE wrote:How can this sequence be expanded into higher-dimensions?  01 Aug 2009, 19:52
 bitRAKE Joined: 21 Jul 2003 Posts: 3844 Location: vpcmipstrm bitRAKE 01 Aug 2009, 23:05 MHajduk wrote:BTW, what do you exactly mean by this bitRAKE wrote:How can this sequence be expanded into higher-dimensions? It is very ambiguous, but ideally we would want to bring as many features of this sequence into higher dimensions. It could be something as silly as shells in 2D/3D. (Another good example is the hilbert curve in higher-dimensions.) Or the sequence can be transformed into a higher dimensional object directly: 00->x++, 01->y++, 10->z++ (rotate on selected axis, and always move forward one unit). The limits are only the imagination and what can be discovered about the sequence. My intent was the former, but the pseudo-palindromic and fractal nature of the sequence could be fun. http://www.youtube.com/watch?v=ZDGGEQqSXew _________________¯\(°_o)/¯ The hardcore cynic mistakes good for guile. 01 Aug 2009, 23:05
 MHajduk Joined: 30 Mar 2006 Posts: 6110 Location: Poland MHajduk 02 Aug 2009, 19:19 Yeah, I've realized that lengths of the terms of the T sequence correspond with the terms of the Fibonacci numbers sequence F. If we define l(n) as a length of the T(n) string, we will have Code:`l(n) = l(n-1) + l(n-2) ` because length of the concatenation of strings T(n-1) and T(n-2) is equal to the sum of lengths of these strings. There is only one thing: we start from the natural numbers 1 and 2, not from the 0 and 1: Code:```T(0) = 0 l(0) = 1 = F(2) T(1) = 01 l(1) = 2 = F(3) T(2) = 010 = T(1)T(0) l(2) = l(1) + l(0) = 2 + 1 = 3 = F(4) T(3) = 01001 = T(2)T(1) l(3) = l(2) + l(1) = 3 + 2 = 5 = F(5) T(4) = 01001010 = T(3)T(2) l(4) = l(3) + l(2) = 5 + 3 = 8 = F(6) ... ```  02 Aug 2009, 19:19
 MHajduk Joined: 30 Mar 2006 Posts: 6110 Location: Poland MHajduk 02 Aug 2009, 19:42 As you said previously, terms of our sequence T show us some symmetry. But this symmetry is hidden rather in the rule of creation of the new terms than in the visible form of these strings (they usually aren't palindromes). From definition of the T sequence we have Code:`T(n) = T(n-1)T(n-2) = T(n-2)T(n-3)T(n-2) for every natural n>=3 `It's obvious that T(n) for odd n can't be palindrome, because every term of the T sequence starts from 0, and every T(n) for odd n has 1 as a last symbol. T(n) for even n>=4 also can't be palindrome, because (from the formula presented above in this post) even if T(n-2) would be palindrome T(n-3) isn't (n-3 is an odd number). Only palindromic terms of the T sequence are T(0) and T(2).  02 Aug 2009, 19:42
 bitRAKE Joined: 21 Jul 2003 Posts: 3844 Location: vpcmipstrm bitRAKE 03 Aug 2009, 00:21 Just remove the last two digits of a term and it's a palindrome. (So, I made up the term pseudo-palindromic - close enough.) T(-1) = 1, and use the substitution definition: 0->01, 1->0; and the lengths are still F(n+2). Bit counts are also F() connected! (Another topic perhaps: the substitution definition also allows us to construct an interesting tree.) What can be said about the partitions of T(inf)? We know 2-bit partitions consist of: 00 01 10. 2 | 00 01 10 3 | 001 010 100 101 4 | 0010 0100 0101 1001 1010 Hm... 03 Aug 2009, 00:21
 bitRAKE Joined: 21 Jul 2003 Posts: 3844 Location: vpcmipstrm bitRAKE 03 Aug 2009, 13:53 It is possible to find bit-N of the infinite sequence in less than O(log base golden ratio N). This can be done by subtracting the largest fibonacci number until 0 or 1 is reached, then the bit value is opposite. (Bit count used here is 1 based not the typical 0 based bit numbering of x86.) For example, bit 54 is 1: 54 - 34 = 20 20 - 13 = 7 7 - 5 = 2 2 - 2 = 0 <-- result is opposite. 03 Aug 2009, 13:53
 Madis731 Joined: 25 Sep 2003 Posts: 2139 Location: Estonia Madis731 03 Aug 2009, 15:18 Observation#1: There are no ones ('1') next to each-other Observation#2: When you start taking Fibonacci sequence amount of digits from the start you can notice they are all palindromes. Example: T8 = 0100101001001010010100100101001001010010100100101001010 '0', '1', '00', '101', '00100', '10100101', etc. Observation#3: When we construct the sequence throught T0 and T1, it is obvious where the reversing / palindrome effect comes from: T0; T1; T1+T0; T1+T0+T1; T1+T0+T1+T1+T0; etc. @bitRAKE: Isn't is easier to use 0-based counting. This way bitat=0, bitat=1, bitat=2-2=0, bitat=3-3=0, bitat=4-3=1, etc. 03 Aug 2009, 15:18
 bitRAKE Joined: 21 Jul 2003 Posts: 3844 Location: vpcmipstrm bitRAKE 04 Aug 2009, 14:08 Yeah, it works just fine with 0-based bit indexing: Code:``` irp i,2,3,5,8,13,21,34 { reverse cmp rcx,i jc @F sub rcx,i @@: } ```...it seems there is a method without the branch miss-penalties. Code:``` irp i,2,3,5,8,13,21,34 { reverse mov rax,-i xadd rcx,rax cmovs rcx,rax } ```(XADD/CMOV** is a nice combo. ) Sure beats trying to calculate: Last edited by bitRAKE on 06 Aug 2009, 00:54; edited 5 times in total 04 Aug 2009, 14:08
 r22 Joined: 27 Dec 2004 Posts: 805 r22 04 Aug 2009, 20:43 Expanding on the fact that there are never 2 consecutive 1's you can compress the sequence by only using the number of 0's between the 1's. Uncompressed T4 = 01001010 T5 = 0100101001001 Compressed 0 = one zero 1 = 2 zeros T4 = 0100 T5 = 01011 When decompressing you'd add 1's between the sets of 0's and add the trailing 1 for the Odd iterations. Perhaps the compressed sequence could be calculated in a more efficient manner than the original ? 04 Aug 2009, 20:43
 Madis731 Joined: 25 Sep 2003 Posts: 2139 Location: Estonia Madis731 05 Aug 2009, 10:18 Maybe I don't get the compression, but shouldn't it be: Code:```T0 = 0 0 T1 = 01 1 T2 = 010 10 T3 = 01001 101 T4 = 01001010 10110 Just a find&replace Pack: 01=>1; 0=>0 Unpack: 1=>01; 0=>0 ``` EDIT: I get it Rule#1: There are no two consecutive '1's Rule#2: There are exactly {one | two} '0's Observation: The string consists of two substrings - a '01' and a '001' 05 Aug 2009, 10:18
 Madis731 Joined: 25 Sep 2003 Posts: 2139 Location: Estonia Madis731 05 Aug 2009, 11:24 Maybe we can draw an "Ant" algorithm in the bitmap where it follows the cadence of 1-1-0-1-1-0 (odd-odd-even) and it turns left (in 2D) on each 1 (odd) and goes straight on on each 0 (even), flipping output bits if odd. If we get on a visited square, the bits in the output are inverted from that point on. Example T5 = 0100101001001 Generating starts from co-ordinates (x:0,y:0), direction vector is (x:-1,y:0), "left" means vector is turned 90° so that new is (x:0,y:1). 1) print '0', mark (0,0) visited, odd=LEFT+FLIP 2) print '1', mark (0,1) visited, odd=LEFT+FLIP 3) print '0', mark (1,1) visited, even=STRAIGHT 4) print '0', mark (2,1) visited, odd=LEFT+FLIP etc. its a thought it progress so I don't promise anything  05 Aug 2009, 11:24
 Madis731 Joined: 25 Sep 2003 Posts: 2139 Location: Estonia Madis731 05 Aug 2009, 12:47 Anyway my first try. Version1 - 34 bytes. Rather elegant, not anything cryptic. 64-bit fastcall Note: you can save a byte when mov word[rcx],'01' is replaced with mov byte[rcx+1],1 Code:``` fastcall Mystery,TM,8 Mystery: ;34 bytes mov word[rcx],'01' ;5 xor eax,eax ;2 mov al,1 ;2 lea ebx,[rax*2] ;3 dec edx ;2 mov esi,ecx ;2 lea edi,[rcx+rbx] ;3 - 19 bytes init @@: mov ecx,eax ;2 rep movsb ;2 sub esi,eax ;2 add eax,ebx ;2 xchg eax,ebx ;1 dec edx ;2 jnz @b ;2 ret ;1 - 14 bytes program ``` 05 Aug 2009, 12:47
 r22 Joined: 27 Dec 2004 Posts: 805 r22 05 Aug 2009, 20:41 I've found the bit pattern in my compressed version Here's T 01001010010010100101001001010010010100101001001010010100100101001001010010100100101001001 Here's T compressed (see above explanation) 0101101011011010110101101101011011 Fib. Numbers 0,1,1,2,3,5,8 etc. If you notice they have a pattern of EVEN ODD ODD EVEN ODD ODD EVEN ODD ODD .etc Here's the Even Odd pattern And the compressed T mapped to the even odd pattern Code:```0110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110110 01----01--1----01----01--1----01--1----01----01--1----01----01--1----01--1----01----01--1----01--1 ``` Here's the pseudo code to generate the compressed pattern * EDIT * I'll post actual code once I work it out. The pseudo code was flawed. Pretty interesting 05 Aug 2009, 20:41
 bitRAKE Joined: 21 Jul 2003 Posts: 3844 Location: vpcmipstrm bitRAKE 06 Aug 2009, 03:37 r22, data compression is one of the contexts in which I discovered this sequence. I asked myself, "Why nature doesn't use binary?" In a general sense, effective use of binary requires arbitrary quantities of two substances (one for 0 and one for 1). In reality often one substance is in short supply while another is abundant. My conclusion was that nature would choose an information storage method relying on a single limiting substance, and another which was abundant. Code:```.0100101001001010010100100101001001 0101101011011010110101101101011011 ```FYI: "Compressed" it becomes the same as uncompressed.  06 Aug 2009, 03:37
 Azu Joined: 16 Dec 2008 Posts: 1159 Azu 06 Aug 2009, 07:56 bitRAKE wrote:r22, data compression is one of the contexts in which I discovered this sequence. I asked myself, "Why nature doesn't use binary?" In a general sense, effective use of binary requires arbitrary quantities of two substances (one for 0 and one for 1). In reality often one substance is in short supply while another is abundant. My conclusion was that nature would choose an information storage method relying on a single limiting substance, and another which was abundant. Code:```.0100101001001010010100100101001001 0101101011011010110101101101011011 ```FYI: "Compressed" it becomes the same as uncompressed. I think nature compresses data pretty well already. Amoeba dubia, for example, have 670 billion base pairs (which are the equivilant of 1 or 2 bits each I think) in their genome.. in a single microscopic cell! When/if computers start getting that kind of insane data compression, then criticize nature.  06 Aug 2009, 07:56
 bitRAKE Joined: 21 Jul 2003 Posts: 3844 Location: vpcmipstrm bitRAKE 06 Aug 2009, 13:43 Azu wrote:When/if computers start getting that kind of insane data compression, then criticize nature. Quite the contrary - I always look to nature for answers! How can we compete with trillions of simulations per second over billions of years? It is the language of nature which we have difficulty understanding (if history is any indication, it's our egos in the way). _________________¯\(°_o)/¯ The hardcore cynic mistakes good for guile. 06 Aug 2009, 13:43
 Tomasz Grysztar Joined: 16 Jun 2003 Posts: 8250 Location: Kraków, Poland Tomasz Grysztar 06 Aug 2009, 13:46 Actually, DNA contains a lot of redundant data (as it makes it more resistant to damage, etc.), so I wouldn't really use it as an example of a good data compression - quite the opposite.  06 Aug 2009, 13:46
 Azu Joined: 16 Dec 2008 Posts: 1159 Azu 06 Aug 2009, 13:50 A lot of redundant data compressed into a very tiny space..  06 Aug 2009, 13:50
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First  Jump to: Select a forum Official----------------AssemblyPeripheria General----------------MainTutorials and ExamplesDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsOS ConstructionIDE DevelopmentProjects and IdeasNon-x86 architecturesHigh Level LanguagesProgramming Language DesignCompiler Internals Other----------------FeedbackHeapTest Area
Goto page 1, 2  Next

Forum Rules:
 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot vote in polls in this forumYou cannot attach files in this forumYou can download files in this forum