Thue-Morse Sequence Contest

Index > Main > Thue-Morse Sequence Contest

Goto page Previous 1, 2, 3 Next

Author

Thread

Tomasz Grysztar

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

Tomasz Grysztar 28 Jan 2009, 11:36

One note though: your up_to_T32 won't work, because the bit count for BTx instructions is a signed value (!).

BTW, I find it funny that I managed to use JP instruction for solution, not realizing that the direct definition of problem (which I didn't even care to read Wink

) imposes the usage of parity check, even though in a bit different way. Smile

28 Jan 2009, 11:36

revolution
When all else fails, read the source

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

revolution 28 Jan 2009, 11:39

Easy fixed Wink

Code:

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

28 Jan 2009, 11:39

revolution
When all else fails, read the source

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

revolution 28 Jan 2009, 11:42

Tomasz Grysztar wrote:

BTW, I find it funny that I managed to use JP instruction for solution, not realizing that the direct definition of problem (which I didn't even care to read ) imposes the usage of parity check, even though in a bit different way.

Perhaps someone can edit the Wikipedia entry and add a paragraph stating that the output is the 2's parity of the position counter.

28 Jan 2009, 11:42

MHajduk

Joined: 30 Mar 2006
Posts: 6115
Location: Poland

MHajduk 28 Jan 2009, 11:42

OK, here is the next version of my procedure, has 21 bytes (if I would remove such instructions as 'pushad', 'popad' and 'retn' it could be also 18 byte Wink

), one loop, using parity of bits:

Code:

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

          xor     eax, eax
            mov     al, 1
               shl     eax, cl
             xchg    eax, ecx
            xor     edx, edx                

                .Loop:
                  setnp   al
                  or      al, '0'
                   stosb
                       inc     edx
                 loop    .Loop

           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-28.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    edi, eax

                mov     ecx, n

          call    ThueMorse

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

              invoke  LocalFree, edi

  exit:
           invoke  ExitProcess, 0

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

          xor     eax, eax
            mov     al, 1
               shl     eax, cl
             xchg    eax, ecx
            xor     edx, edx                

                .Loop:
                  setnp   al
                  or      al, '0'
                   stosb
                       inc     edx
                 loop    .Loop

           popad
               retn

.end start

28 Jan 2009, 11:42

revolution
When all else fails, read the source

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

revolution 28 Jan 2009, 11:45

MHajduk: Parity is only calculated for the lowest 8 bits in x86. So anything above n=8 may fail.

28 Jan 2009, 11:45

revolution
When all else fails, read the source

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

revolution 28 Jan 2009, 11:48

MHajduk wrote:

Code:

...
                xor     eax, eax
                mov     al, 1
                shl     eax, cl
...

Is it shorter to put:

Code:

xor eax,eax
bts eax,ecx

28 Jan 2009, 11:48

Tomasz Grysztar

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

Tomasz Grysztar 28 Jan 2009, 11:50

revolution wrote:

Perhaps someone can edit the Wikipedia entry and add a paragraph stating that the output is the 2's parity of the position counter.

The very definition of the sequence says exactly this.

If you read it carefully, you'll also notice, that it's not T0, T1, etc. that are really the terms of Thue-Morse sequence, but t0, t1, as:
t0 = 0
t1 = 1
t2 = 1
t3 = 0
etc.

So, in fact, the answer to "What is the smallest routine to generate a Thue-Morse term?" might rather be something like:

Code:

        shld    ecx,eax,16
        xor     ecx,eax 
        xor     ch,cl
        setpo   al

Input - number of term in EAX. Output - the term value in the lowest bit of EAX. Smile

Last edited by Tomasz Grysztar on 28 Jan 2009, 11:55; edited 2 times in total

28 Jan 2009, 11:50

revolution
When all else fails, read the source

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

revolution 28 Jan 2009, 11:52

Tomasz Grysztar wrote:

revolution wrote:
Perhaps someone can edit the Wikipedia entry and add a paragraph stating that the output is the 2's parity of the position counter.

The very definition of the sequence says exactly this.

But it doesn't have the word "parity". Any computer programmer should instantly understand it if it did.

28 Jan 2009, 11:52

MHajduk

Joined: 30 Mar 2006
Posts: 6115
Location: Poland

MHajduk 28 Jan 2009, 11:55

revolution wrote:

MHajduk wrote:

Code:

...
                xor     eax, eax
                mov     al, 1
                shl     eax, cl
...

Is it shorter to put:

Code:

xor eax,eax
bts eax,ecx

Yes, you are right. Wink

28 Jan 2009, 11:55

revolution
When all else fails, read the source

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

revolution 28 Jan 2009, 12:05

Tomasz Grysztar wrote:

So, in fact, the answer to "What is the smallest routine to generate a Thue-Morse term?" might rather be something like:
Code:
        shld    ecx,eax,16
        xor     ecx,eax 
        xor     ch,cl
        setpo   al    
Input - number of term in EAX. Output - the term value in the lowest bit of EAX.

11 bytes.

This is also the same length (11 bytes) but has one more instruction:

Code:

    mov     ecx,eax
     bswap   ecx
        xor     ecx,eax 
        xor     ch,cl
        setpo   al

28 Jan 2009, 12:05

MHajduk

Joined: 30 Mar 2006
Posts: 6115
Location: Poland

MHajduk 28 Jan 2009, 12:18

But, accordingly to the competition conditions, we are concerned on generation T_{n} elements, not t_{n}. Sequence T is a sequence of sequences of 0's and 1's. Wink

28 Jan 2009, 12:18

bitRAKE

Joined: 21 Jul 2003
Posts: 4016
Location: vpcmpistri

bitRAKE 28 Jan 2009, 15:55

Although the terms are suffixes of following terms, the reason for passing the term number into the routine is to limit effect on target memory. So, these latest entries are not capable of producing a range of T# terms. Of course, they are still valid entries.

Bravo for finding the parity definition - it was hidden, imho.
http://mathworld.wolfram.com/Thue-MorseSequence.html
At the MathWorld site it is stated at the start!

(I'll update the results after work today, and will update the description to make the output limit more explict.)

Last edited by bitRAKE on 28 Jan 2009, 16:03; edited 1 time in total

28 Jan 2009, 15:55

revolution
When all else fails, read the source

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

revolution 28 Jan 2009, 16:01

bitRAKE wrote:

Although the terms are suffixes of following terms, the reason for passing the term number into the routine is to limit effect on target memory. So, these latest entries are not capable of producing a range of T# terms.

I was only coding the core idea. Others are welcome to copy/modify/extend my snippets and post record-breaking generic entries.

28 Jan 2009, 16:01

bitRAKE

Joined: 21 Jul 2003
Posts: 4016
Location: vpcmpistri

bitRAKE 28 Jan 2009, 16:05

Of course, they are still valid entries.

28 Jan 2009, 16:05

revolution
When all else fails, read the source

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

revolution 29 Jan 2009, 17:03

Code:

  use32

;Input:        edi = pointer to zeroed memory
;     ecx = T value

up_to_T8:
  xor     eax,eax ;bit counter
    .loop:
      test    al,0xff
     jpe     @f
  bts     [edi],eax
    @@:        inc     eax
 bt      eax,ecx
     jnc     .loop
       retn                    ;16 bytes

Code:

        use32

;Input:        edi = pointer to zeroed memory
;     ecx = T value

up_to_T16:
 xor     eax,eax ;bit counter
    .loop:
      mov     dl,al
       xor     dl,ah
       jpe     @f
  bts     [edi],eax
    @@:        inc     eax
 bt      eax,ecx
     jnc     .loop
       retn                    ;18 bytes

Code:

        use32

;Input:        edi = pointer to zeroed memory
;     ecx = T value

up_to_T31:
 xor     eax,eax ;bit counter
    .loop:
      shld    edx,eax,16
  xor     edx,eax
     xor     dl,dh
       jpe     @f
  bts     [edi],eax
    @@:        inc     eax
 bt      eax,ecx
     jnc     .loop
       retn                    ;22 bytes

Code:

        use64

;Input:        rdi = pointer to zeroed memory
;     rcx = T value

up_to_T63:
 xor     rax,rax ;bit counter
    .loop:
      shld    rdx,rax,32
  xor     edx,eax
     shld    ebx,edx,16
  xor     ebx,edx
     xor     bl,bh
       jpe     @f
  bts     [rdi],rax
    @@:        inc     rax
 bt      rax,rcx
     jnc     .loop
       retn                    ;34 bytes

29 Jan 2009, 17:03

LocoDelAssembly
Your code has a bug

Joined: 06 May 2005
Posts: 4624
Location: Argentina

LocoDelAssembly 29 Jan 2009, 17:08

BTW, why this thread is on Heap? Should I move it to Main?

29 Jan 2009, 17:08

revolution
When all else fails, read the source

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

revolution 29 Jan 2009, 17:10

LocoDelAssembly wrote:

BTW, why this thread is on Heap? Should I move it to Main?

Main wrote:

General discussion about flat assembler, not related to any particular operating system.

Doesn't seem to fit there.

29 Jan 2009, 17:10

LocoDelAssembly
Your code has a bug

Joined: 06 May 2005
Posts: 4624
Location: Argentina

LocoDelAssembly 29 Jan 2009, 17:21

Heap wrote:

Everything not related to assembly programming should be posted here.

Perhaps it doesn't fit on Main but I think that it fits better on there than here on Heap... (And Main has been used for "General Assembly Discussion" more than just talking about flat assembler exclusively).

I think Main's definition should be rewritten.

For now, thread moved Very Happy

29 Jan 2009, 17:21

Tomasz Grysztar

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

Tomasz Grysztar 29 Jan 2009, 17:27

LocoDelAssembly wrote:

I think Main's definition should be rewritten.

Perhaps you're right. The main reason for giving it that description was to discourage people from coming and asking questions about MASM/NASM, etc.

29 Jan 2009, 17:27

tom tobias

Joined: 09 Sep 2003
Posts: 1320
Location: usa

tom tobias 29 Jan 2009, 18:03

Loco wrote:

Perhaps it doesn't fit on Main but I think that it fits better on there than here on Heap...

dear friend, I disagree with you, completely.
MAIN, is for problems and or issues associated with FASM, not assembly language programming.
Ask yourself this simple question:
Is there something about this contest, Thue-Morse, for which use of FASM to implement a solution, poses a problem, when compared, for example, to use of MASM or any other assembler? If the answer is YES, then, this is the proper location for this thread. If, on the other hand, there is NOTHING unique about FASM, vis a vis finding a potential solution to the problem, then, this is a mere application, which DOES NOT BELONG in MAIN.
Heap is not a repository of useless thoughts. It is very suitable for discussions of this type, unless, the proposed solution to Thue-Morse uncovers a flaw with FASM.

29 Jan 2009, 18:03

Goto page Previous 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