Thue-Morse Sequence Contest

Index > Main > Thue-Morse Sequence Contest

Goto page 1, 2, 3 Next

Author

Thread

bitRAKE

Joined: 21 Jul 2003
Posts: 4060
Location: vpcmpistri

bitRAKE 25 Jan 2009, 22:32

What is the smallest routine to generate a Thue-Morse block?
(assume zeroed output memory pointer and term ordinal are passed in registers)

For T(n), a block consists of the first 2^n terms of the the Thue-Morse sequence t(n):

T0 = 0
T1 = 01
T2 = 0110
T3 = 01101001
T4 = 0110100110010110
.
.
.
...output can be in any form: ASCII, binary,etc. A distinction shall be made between entries which output a range of terms without writing additional data to the output buffer, and those which output a single term (which includes all lesser terms as suffixes). In the later case those entries output a single term rather than selecting output range based on parameter passed.

No register preservation is required, but as a leaf routine RET is required. I appreciate the understanding of participants as the contest has gotten broader in scope than originally intended - for the good I hope. Previous entry rankings have been updated to reflect these changes without the need for re-submission.

There are so many ways to generate the sequence.
(the task itself is not difficult)

Winners will exist for each execution environment and output format.
(Decided by participation.)

Results:

Code:

Bytes  Type   Output   Entrant          Notes
   23  32bit  ASCII    Mikolaj Hajduk   T0-?, negative copy
   18  32bit  ASCII    Mikolaj Hajduk   T0-T8, parity
   29  32bit  ASCII    Grom PE          T0-?, substitution map  
   28  16bit  ASCII    Grom PE          T0-?, substitution map

   16  32bit  Binary   revolution       T0-T8, parity
   18  32bit  Binary   revolution       T0-T16, parity
   22  32bit  Binary   revolution       T0-T31, parity
   34  64bit  Binary   revolution       T0-T63, parity

   38  64bit  Binary   revolution       only T64 output
   26  32bit  Binary   revolution       only T32 output
   19  32bit  Binary   revolution       only T31 output
   31  16bit  Binary   Tomasz Grysztar  only T19 output
   16  32bit  Binary   revolution       only T16 output
   12  32bit  Binary   revolution       only T8 output
   17  16bit  Binary   Tomasz Grysztar  only T6 output
5/6/7  *      Binary   Tomasz Grysztar  only T4 output
    4  *      Binary   Tomasz Grysztar  only T3 output
    2  *      Binary    ( Example )     only T0 output

_________________
¯\(°_o)/¯ “languages are not safe - uses can be” Bjarne Stroustrup

Last edited by bitRAKE on 31 Jan 2009, 15:34; edited 15 times in total

25 Jan 2009, 22:32

MHajduk

Joined: 30 Mar 2006
Posts: 6115
Location: Poland

MHajduk 26 Jan 2009, 12:48

OK, here is my corrected solution:

Code:

        ; Procedure produces terms of the Thue-Morse sequence denoted as an ASCII
   ; sequence of 0's and 1's.
        ;
   ; Parameters:
   ;       
    ;       - ebx    - pointer to the allocated memory block filled with zero
   ;                  bytes,
   ;
   ;       - edx    - ordinal number of the created term.
      ;
   ThueMorse:
              pushad

          mov     edi, ebx
            mov     al, '0'
           stosb

           .NextTerm:
                      test    edx, edx
                    jz      .End

                    mov     esi, ebx
                    mov     ecx, edi
                    sub     ecx, esi

                        .Loop:
                          lodsb
                               xor     al, 1
                               stosb
                               loop    .Loop

                   dec edx

                 jmp     .NextTerm

               .End:
                   popad
                       retn

Here you have a program which makes easier testing of this procedure:

Code:

;
; Written with FASM simple Windows application which presents in human readable
; form terms of the Thue-Morse sequence produced by a given procedure.
;
; (C) Mikolaj Hajduk, 26.01.2009.
;
;
format PE GUI 4.0

include      'win32ax.inc'

section '.code' code readable executable

       start:
          n = 6   ; Ordinal number of the created term of the Thue-Morse sequence.

                invoke  LocalAlloc, LMEM_ZEROINIT, (1 shl n) + 1
            test    eax, eax
            jz      exit

            xchg    ebx, eax

                mov     edx, n

          call    ThueMorse

               invoke  MessageBox, 0, ebx, "Thue-Morse Sequence", MB_OK

              invoke  LocalFree, ebx

  exit:
           invoke  ExitProcess, 0

  ; Procedure produces terms of the Thue-Morse sequence denoted as an ASCII
   ; sequence of 0's and 1's.
        ;
   ; Parameters:
   ;       
    ;       - ebx    - pointer to the allocated memory block filled with zero
   ;                  bytes.
   ;
   ;       - edx    - ordinal number of the created term,
      ;
   ThueMorse:
              pushad

          mov     edi, ebx
            mov     al, '0'
           stosb

           .NextTerm:
                      test    edx, edx
                    jz      .End

                    mov     esi, ebx
                    mov     ecx, edi
                    sub     ecx, esi

                        .Loop:
                          lodsb
                               xor     al, 1
                               stosb
                               loop    .Loop

                   dec edx

                 jmp     .NextTerm

               .End:
                   popad
                       retn

.end start

Last edited by MHajduk on 26 Jan 2009, 17:53; edited 1 time in total

26 Jan 2009, 12:48

MHajduk

Joined: 30 Mar 2006
Posts: 6115
Location: Poland

MHajduk 26 Jan 2009, 17:39

bitRAKE wrote:

(assume zeroed output memory pointer and term sub-script are passed in registers)

I missed it previously. See my post above for the corrected solution.

26 Jan 2009, 17:39

bitRAKE

Joined: 21 Jul 2003
Posts: 4060
Location: vpcmpistri

bitRAKE 26 Jan 2009, 18:04

Well done. Dropped 20 bytes, too.

26 Jan 2009, 18:04

MHajduk

Joined: 30 Mar 2006
Posts: 6115
Location: Poland

MHajduk 26 Jan 2009, 19:33

Next version of the procedure (one byte smaller than previous):

Code:

   ; Procedure produces terms of the Thue-Morse sequence denoted as an ASCII
   ; sequence of 0's and 1's.
        ;
   ; Parameters:
   ;       
    ;       - ebx    - pointer to the allocated memory block filled with zero
   ;                  bytes,
   ;
   ;       - ecx    - ordinal number of the created term.
      ;
   ThueMorse:
              pushad

          mov     edi, ebx
            mov     al, '0'
           stosb

           jcxz    .End

            .NextTerm:
                      mov     esi, ebx
                    mov     edx, edi
                    sub     edx, esi

                        .Loop:
                          lodsb
                               xor     al, 1
                               stosb
                               dec     edx
                         jnz     .Loop

                   loop    .NextTerm

               .End:
                   popad
                       retn

and simple application for testing it:

Code:

;
; Written with FASM simple Windows application which presents in human readable
; form terms of the Thue-Morse sequence produced by a given procedure.
;
; (C) Mikolaj Hajduk, 26.01.2009.
;
;
format PE GUI 4.0

include     'win32ax.inc'

section '.code' code readable executable

       start:
          n = 4   ; Ordinal number of the created term of the Thue-Morse sequence.

                invoke  LocalAlloc, LMEM_ZEROINIT, (1 shl n) + 1
            test    eax, eax
            jz      exit

            xchg    ebx, eax

                mov     ecx, n

          call    ThueMorse

               invoke  MessageBox, 0, ebx, "Thue-Morse Sequence", MB_OK

              invoke  LocalFree, ebx

  exit:
           invoke  ExitProcess, 0

  ; Procedure produces terms of the Thue-Morse sequence denoted as an ASCII
   ; sequence of 0's and 1's.
        ;
   ; Parameters:
   ;       
    ;       - ebx    - pointer to the allocated memory block filled with zero
   ;                  bytes,
   ;
   ;       - ecx    - ordinal number of the created term.
      ;
   ThueMorse:
              pushad

          mov     edi, ebx
            mov     al, '0'
           stosb

           jcxz    .End

            .NextTerm:
                      mov     esi, ebx
                    mov     edx, edi
                    sub     edx, esi

                        .Loop:
                          lodsb
                               xor     al, 1
                               stosb
                               dec     edx
                         jnz     .Loop

                   loop    .NextTerm

               .End:
                   popad
                       retn

.end start

26 Jan 2009, 19:33

Grom PE

Joined: 13 Mar 2008
Posts: 114
Location: i@grompe.org.ru

Grom PE 27 Jan 2009, 09:06

Ok, I suck, but at least it's different algorithm =)
It allows linear generation.

31 bytes, 32-bit:

Code:

; ebx = pointer
; ecx = term
ThueMorse_by_Grom_PE:
        pushad
      mov     edi, ebx
    mov     esi, ebx
    mov     byte [ebx], '0'
   jecxz   zero

    xor     eax, eax
    inc     eax
 dec     ecx
 shl     eax, cl
     xchg    ecx, eax
x2:
 mov     ah, 0
       lodsb
       cmp     al, '1'
   adc     ah, '0'
   stosw
       loop    x2
zero:
     popad
       ret

30 bytes, 16-bit:

Code:

org 100h

n = 4
        mov     bx, buffer
  mov     cx, n 
      call    ThueMorse_by_Grom_PE_16bit
  mov     byte [bx + 1 shl n], '$'
  mov     ah, 9
       mov     dx, bx
      int     21h
 int     20h

; bx = pointer
; cx = term
ThueMorse_by_Grom_PE_16bit:
 pusha
       mov     di, bx
      mov     si, bx
      mov     byte [bx], '0'
    jcxz    zero

    xor     ax, ax
      inc     ax
  dec     cx
  shl     ax, cl
      xchg    cx, ax
x2:
   mov     ah, 0
       lodsb
       cmp     al, '1'
   adc     ah, '0'
   stosw
       loop    x2
zero:
     popa
        ret

buffer       rb 1 shl n + 1

MHajduk, change jcxz to jecxz in your code and you'll have 25 bytes.

27 Jan 2009, 09:06

MHajduk

Joined: 30 Mar 2006
Posts: 6115
Location: Poland

MHajduk 27 Jan 2009, 10:18

Grom PE wrote:

MHajduk, change jcxz to jecxz in your code and you'll have 25 bytes.

Yes, you are right. It's nice tip, thanks. Smile

Here is 25-byte version of the procedure:

Code:

  ; Procedure produces terms of the Thue-Morse sequence denoted as an ASCII
   ; sequence of 0's and 1's.
        ;
   ; Parameters:
   ;       
    ;       - ebx    - pointer to the allocated memory block filled with zero
   ;                  bytes,
   ;
   ;       - ecx    - ordinal number of the created term.
      ;
   ThueMorse:
              pushad

          mov     edi, ebx
            mov     al, '0'
           stosb

           jecxz   .End

            .NextTerm:
                      mov     esi, ebx
                    mov     edx, edi
                    sub     edx, esi

                        .Loop:
                          lodsb
                               xor     al, 1
                               stosb
                               dec     edx
                         jnz     .Loop

                   loop    .NextTerm

               .End:
                   popad
                       retn

27 Jan 2009, 10:18

Picnic

Joined: 05 May 2007
Posts: 1398
Location: Piraeus, Greece

Picnic 27 Jan 2009, 12:33

I read here that interesting visuals can be constructed using the Thue-Morse sequence.

27 Jan 2009, 12:33

MHajduk

Joined: 30 Mar 2006
Posts: 6115
Location: Poland

MHajduk 27 Jan 2009, 12:48

Very beautiful application of the mathematical idea, indeed. Very Happy

I liked especially this tiling:

Source: http://lcni.uoregon.edu/~mark/Geek_art/Simple_recursive_systems/Tesselations/Redundant_Quadrapii/Redundant_Quadrapii_x2.jpg

27 Jan 2009, 12:48

bitRAKE

Joined: 21 Jul 2003
Posts: 4060
Location: vpcmpistri

bitRAKE 27 Jan 2009, 16:59

Much smaller routines are possible using different algorithms and output formats. For example, if we say the output is limited to just the first term, and parameters are passed in EAX,EDI then "STOSB" would be a valid single byte entry. Sure, it is uninteresting but I am just demonstrating the point that all the outputs are limited - even though we haven't explicitly stated the term limit inherent in the output definition. Another example would be the difference between 32-bit and 16-bit routines -- clearly they have different output limits.

27 Jan 2009, 16:59

Tomasz Grysztar

Joined: 16 Jun 2003
Posts: 8357
Location: Kraków, Poland

Tomasz Grysztar 27 Jan 2009, 17:21

OK, so the shortest routine generating T3 as little-endian binary perhaps might be:

Code:

mov al,10010110b
stosb

And T4 in 6 bytes of 16-bit code:

Code:

mov al,10010110b
cbw
xor ah,al
stosw

Yeah, with plain MOV and STOSW it would be only 4 bytes, but this one is more interesting. Wink

27 Jan 2009, 17:21

bitRAKE

Joined: 21 Jul 2003
Posts: 4060
Location: vpcmpistri

bitRAKE 28 Jan 2009, 02:12

Tomasz, those are valid as are solutions which generate a range of terms.
(Hint: for example, there is a very small way to generate T0-T7.)

28 Jan 2009, 02:12

Tomasz Grysztar

Joined: 16 Jun 2003
Posts: 8357
Location: Kraków, Poland

Tomasz Grysztar 28 Jan 2009, 08:47

bitRAKE wrote:

(Hint: for example, there is a very small way to generate T0-T7.)

Well, I've got something for T0-T6:

Code:

        mov     al,10010110b
        mov     dl,al
  @loop:
        stosb
        test    dl,11b
        jp      @f
        not     al
     @@:
        shr     dl,1
        jnz     @loop

I'm not sure if mine is "very small", but look - I use JP instruction. Wink

It could act as an example for the thread about cases of JP being useful.

28 Jan 2009, 08:47

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20430
Location: In your JS exploiting you and your system

revolution 28 Jan 2009, 09:30

This "generates" T0 in one bit

Code:

db 0b ;T0: assumes little endian bit storage

This "generates" T1 in two bits

Code:

db 10b ;T1: assumes little endian bit storage

This "generates" T2 in four bits

Code:

db 0110b ;T2: assumes little endian bit storage

This "generates" T3 in one byte

Code:

db 10010110b ;T3: assumes little endian bit storage

This "generates" T4 in two bytes

Code:

dw 0110100110010110b ;T4: assumes little endian bit storage

This "generates" T5 in four bytes

Code:

dd 10010110011010010110100110010110b ;T5: assumes little endian bit storage

This "generates" T6 in eight bytes

Code:

dq 0110100110010110100101100110100110010110011010010110100110010110b ;T6: assumes little endian bit storage

28 Jan 2009, 09:30

Tomasz Grysztar

Joined: 16 Jun 2003
Posts: 8357
Location: Kraków, Poland

Tomasz Grysztar 28 Jan 2009, 10:21

As further playing with that JP idea Wink

, this 16-bit code generates T19 in binary form (revolution, this one you won't beat that way Wink

Code:

        xor     bx,bx ; how many bytes generate? 0 gives 65536.

        mov     si,di
        xor     cx,cx
        mov     al,10010110b
  @loop:
        stosb
        mov     dx,[si]
        shr     dx,cl
        test    dl,11b
        jp      @f 
        not     al 
     @@: 
        inc     cx
        and     cl,111b
        jnz     @f
        inc     si
     @@:
        dec     bx
        jnz     @loop

It assumes DS=ES, but I already saw this assumption be allowed for 16-bit code here. However it fills whole segment with data, so don't try it from .COM file unless you get yourself some free segment. Wink

But by putting some smaller value into BX you may generate smaller amount of data (like 8000h in BX will give you T18).

28 Jan 2009, 10:21

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20430
Location: In your JS exploiting you and your system

revolution 28 Jan 2009, 10:46

Code:

        use32
up_to_T8:
        xor     eax,eax ;bit counter
    .loop:
        jpe     @f
        btc     [edi],eax
    @@: inc     al
        jnz     .loop                   ;11 bytes

Code:

 use32
up_to_T16:
     xor     eax,eax ;bit counter
    .loop:
      mov     cl,al
       xor     cl,ah
       jpe     @f
  btc     [edi],eax
    @@:        inc     ax
  jnz     .loop                   ;15 bytes

Code:

        use32
up_to_T32:
        xor     eax,eax ;bit counter
    .loop:
        shld       ecx,eax,16
        xor     ecx,eax
        xor     ch,cl
        jpe     @f
        btc     [edi],eax
    @@: inc     eax
        jnz     .loop                   ;18 bytes

28 Jan 2009, 10:46

Tomasz Grysztar

Joined: 16 Jun 2003
Posts: 8357
Location: Kraków, Poland

Tomasz Grysztar 28 Jan 2009, 11:13

Yeah, much better application of parity check that mine. Smile

But doesn't it assume the memory is pre-initialized?

28 Jan 2009, 11:13

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20430
Location: In your JS exploiting you and your system

revolution 28 Jan 2009, 11:14

Of course it requires this:

bitRAKE wrote:

assume zeroed output memory pointer

else a prefixed rep stosb is in order.

28 Jan 2009, 11:14

Tomasz Grysztar

Joined: 16 Jun 2003
Posts: 8357
Location: Kraków, Poland

Tomasz Grysztar 28 Jan 2009, 11:16

Oh, I guess I should read the thread before participating. Very Happy

I even did not read the definition of the series earlier. Wink

And now I see that your solution just follows the definition in the most strict sense.

Last edited by Tomasz Grysztar on 28 Jan 2009, 11:18; edited 1 time in total

28 Jan 2009, 11:16

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20430
Location: In your JS exploiting you and your system

revolution 28 Jan 2009, 11:18

Tomasz Grysztar wrote:

Oh, I guess I should read the thread before participating.

If all else fails read the instructions Very Happy

28 Jan 2009, 11:18

Goto page 1, 2, 3 Next

< Last Thread | Next Thread >

Forum Rules:

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