Thue-Morse Sequence Contest

Index > Main > Thue-Morse Sequence Contest

Goto page Previous 1, 2, 3

Author

Thread

LocoDelAssembly
Your code has a bug

Joined: 06 May 2005
Posts: 4624
Location: Argentina

LocoDelAssembly 29 Jan 2009, 19:10

Quote:

Heap is not a repository of useless thoughts. It is very suitable for discussions of this type,

Then, looks that you choose to give Heap an arbitrary purpose because the description is very clear, it says: "Everything not related to assembly programming should be posted here".

BTW, may I wonder why you didn't suggest moving the XOR EAX, EAX debate to Heap? What it has to do to the Main's purpose you have described?

My decision was based on current practice rather than strict forum definition, and since there were posted several times on Main algos that were independent of the underlining OS I though this contest, fully based on Assembly, belongs to Main.

29 Jan 2009, 19:10

bitRAKE

Joined: 21 Jul 2003
Posts: 4024
Location: vpcmpistri

bitRAKE 30 Jan 2009, 03:10

Projects seems an applicable place for contests?

30 Jan 2009, 03:10

revolution
When all else fails, read the source

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

revolution 30 Jan 2009, 05:40

Code:

        use32

;Input: edi = pointer to zeroed memory

T32:
        xor     eax,eax ;bit counter
    .loop:
        shl     ebx,29
        shld    edx,eax,16
        xor     edx,eax
        xor     dl,dh
        jpe     @f
        bts     [edi+ebx],eax
    @@: inc     eax
        sets    bl
        jnz     .loop
        retn                    ;T32: 26 bytes

30 Jan 2009, 05:40

revolution
When all else fails, read the source

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

revolution 30 Jan 2009, 08:56

This one might take a while to finish:

Code:

        use64

;Input: rdi = pointer to zeroed memory

T64:
        xor     rax,rax ;bit counter
    .loop:
        shl     rcx,61
        shld    rdx,rax,32
        xor     edx,eax
        shld    ebx,edx,16
        xor     ebx,edx
        xor     bl,bh
        jpe     @f
        bts     [rdi+rcx],rax
    @@: inc     rax
        sets    cl
        jnz     .loop
        retn                    ;T64: 38 bytes

30 Jan 2009, 08:56

bitRAKE

Joined: 21 Jul 2003
Posts: 4024
Location: vpcmpistri

bitRAKE 31 Jan 2009, 04:57

revolution, these latest two routines T32/T64 have EBX/RCX undefined on entry - not until the end of the loop do the needed bits obtain a known value.

To all: Please, note I have refined the definition of the contest using the terminology of the Wikipedia entry - they refer to Tn as blocks. Thue-Morse is also a constant and confusion exists between the two Wikipedia entries, imho.

31 Jan 2009, 04:57

revolution
When all else fails, read the source

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

revolution 31 Jan 2009, 05:10

bitRAKE wrote:

revolution, these latest two routines T32/T64 have EBX/RCX undefined on entry - not until the end of the loop do the needed bits obtain a known value.

Yes, I know that, but the code is still correct. The fist pass through the loop is always with even parity so the undefined value is never used.

31 Jan 2009, 05:10

tom tobias

Joined: 09 Sep 2003
Posts: 1320
Location: usa

tom tobias 31 Jan 2009, 10:08

Loco wrote:

...may I wonder why you didn't suggest moving the XOR EAX, EAX debate to Heap?

Yes, you may.
http://board.flatassembler.net/topic.php?t=6339
Umm. Let's see, first of all, I didn't start that (in)famous thread. Secondly, the question of programming versus coding is so important to me, that it never occurred to me to ask that the thread be displaced from MAIN. Now that you bring up the topic, however, I agree with you, it probably does NOT belong in MAIN, because the thrust of the thread is on assembly language programming, rather than FASM, per se. Thirdly, I am quite often, ok, let's be honest, I am generally inconsistent, anyway; accordingly, it is not surprising that I should argue abc in one post, and xyz in another. Fourthly, I am not sure that back in those days, we were quite as focused, as we are today, on housekeeping chores, i.e. I think that there were not infrequently, in those days, a couple of years ago, i.e. before the big crash, topics which were misfiled on the forum. Maybe I am incorrect in offering such a solution to this particular conundrum...

bitRAKE wrote:

...Projects seems an applicable place for contests?

brilliant, as always...
Smile

31 Jan 2009, 10:08

tom tobias

Joined: 09 Sep 2003
Posts: 1320
Location: usa

tom tobias 31 Jan 2009, 10:17

Loco wrote:

...I though this contest, fully based on Assembly, belongs to Main.

You know what, Loco, maybe I err here. Maybe you are correct, and "MAIN" ought to represent, apparently exactly what it currently does, and always has, i.e. Assembly language programming in general, and FASM specific problems should, contrary to the opinion I have expressed, be displaced to "Compiler" issues, exactly as has been done, with great success to date, since the forum commenced... In other words, I am simply confused as usual.

31 Jan 2009, 10:17

bitRAKE

Joined: 21 Jul 2003
Posts: 4024
Location: vpcmpistri

bitRAKE 31 Jan 2009, 15:31

revolution wrote:

bitRAKE wrote:
revolution, these latest two routines T32/T64 have EBX/RCX undefined on entry - not until the end of the loop do the needed bits obtain a known value.
Yes, I know that, but the code is still correct. The fist pass through the loop is always with even parity so the undefined value is never used.

You are usually so verbose - I hardly expect such tricks from your code. Very Happy

Thanks for clarifying.

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

31 Jan 2009, 15:31

revolution
When all else fails, read the source

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

revolution 31 Jan 2009, 15:54

bitRAKE wrote:

You are usually so verbose - I hardly expect such tricks from your code. Thanks for clarifying.

The sets can be moved up to just below .loop:. Makes no difference though, same size and same result either way.

31 Jan 2009, 15:54

bitRAKE

Joined: 21 Jul 2003
Posts: 4024
Location: vpcmpistri

bitRAKE 19 Apr 2020, 03:06

Thue–Morse sequence, t_n can be defined as the least bit, of the sum, of one bits in the binary representation of (n) -- BT (POPCNT (n)),0.

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

19 Apr 2020, 03:06

Goto page Previous 1, 2, 3

< 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