# PureBasic Forum

 It is currently Thu Jan 21, 2021 2:09 am

 All times are UTC + 1 hour

 Page 1 of 1 [ 9 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: Thue–Morse sequencePosted: Sat May 16, 2015 11:34 am

Joined: Thu Jun 07, 2007 3:25 pm
Posts: 3967
Location: Berlin, Germany
In mathematics, the Thue–Morse sequence is the infinite sequence of 0s and 1s (or any other ordered pair of symbols) obtained by starting with 0 and successively appending the Boolean complement of the sequence obtained thus far. The first few steps of this procedure yield the strings 0 then 01, 0110, 01101001, 0110100110010110 [after Wikipedia].
This sequence has several interesting applications.

Here is one of them:
Say there are 8 tasty cookies, all of different sizes. Both Alice and Bob want to take the biggest available cookie at any moment. For an allegedly fair procedure, normally they would toss a coin in order to determine who may start, and then they would alternate with taking a cookie. When Alice starts, the sequence looks like this:
AB AB AB AB

But this is far apart from being fair!
The only fair thing here is tossing the coin. Then, simple alternation means a constant disadvantage of the second one. In each round, the one who selects first gets a bigger cookie than the other one. And when constantly alternating, this is unfairly always the same person!
In contrast, using the first 8 elements of the Thue-Morse sequence will lead to a much fairer procedure:
AB BA BA AB

Considerations like these play a role in various tournament competitions, such as the kicking sequence of a penalty shoot-out in soccer, the serving order in tennis, and the rotation of color of pieces in a chess match.

The Thue-Morse sequence appears in many other contexts.
For instance, it can also be used for controlling a Turtle graphics program in order to draw a Koch snowflake.

For more details and additional interesting information about the Thue-Morse sequence see e.g. http://blog.zacharyabel.com/tag/thue-morse-sequence/.

//edit:
See below for a fast ASM version of ThueMorse() by wilbert.

Code:
; PB 5.31

CompilerIf #PB_Compiler_OS = #PB_OS_Linux
Procedure.l PopCount32 (k.l)
; -- Population count:
; return number of bits that are set to 1 in 'k'
; (after code posted by idle, 2015-05-14:
;  http://www.purebasic.fr/english/viewtopic.php?p=465096#p465096
;  Thank you!)

;x - (x >> 1) &  \$55555555
!mov eax, [p.v_k]
!mov edx, eax
!shr edx, 1
!and edx, 0x55555555
!sub eax, edx
;x = (x & \$33333333) + ((x >> 2) & \$33333333)
!mov edx, eax
!and eax, 0x33333333
!shr edx, 2
!and edx, 0x33333333
;x = (x + (x >> 4)) & \$0f0f0f0f0f
!mov edx, eax
!shr edx, 4
!and eax, 0x0f0f0f0f
;x * 0x01010101 >> 24
!imul eax, 0x01010101
!shr eax, 24
ProcedureReturn              ; return the value of eax
EndProcedure

CompilerElse

Procedure.l PopCount32 (k.l)
; -- Population count:
; return number of bits that are set to 1 in 'k'
; (processor and used assembler must support the SSE 4.2 instruction set)

! popcnt eax, [p.v_k]
ProcedureReturn              ; return the value of eax
EndProcedure
CompilerEndIf

Procedure.i ThueMorse (k.i)
; -- return value of the Thue-Morse sequence at place 'k' (0 or 1)
;   [<http://mathworld.wolfram.com/Thue-MorseSequence.html>, 2015-05-01]

If k < 0
ProcedureReturn -1           ; error
EndIf

ProcedureReturn PopCount32(k) % 2
EndProcedure

Structure CharArray
char.c[0]
EndStructure

Procedure.s ThueMorse_Sequence (n.i, symbols\$="01")
; -- return a Thue-Morse sequence of lenght 'n'
Protected last.i, k.i, ret\$
Protected *p.Character, *s.CharArray=@symbols\$

If n < 1 Or Len(symbols\$) <> 2
ProcedureReturn ""           ; error
EndIf

ret\$ = Space(n)
*p = @ret\$
last = n - 1
For k = 0 To last
*p\c = *s\char[PopCount32(k) % 2]
*p + SizeOf(Character)
Next

ProcedureReturn ret\$
EndProcedure

; -- Demo
Debug ThueMorse(15)
Debug ThueMorse_Sequence(16)

; The Thue-Morse sequence even has a relationship to music: :D
Debug ThueMorse_Sequence(4, "AB")

_________________
Please excuse my flawed English. My native language is PureBasic.
Search
RSBasic's backups

Last edited by Little John on Sat May 16, 2015 9:20 pm, edited 1 time in total.

Top

 Post subject: Re: Thue–Morse sequencePosted: Sat May 16, 2015 11:42 am

Joined: Mon Feb 16, 2015 2:49 pm
Posts: 1907
Little John wrote:
when constantly alternating, this is unfairly always the same person!

Huh? When it's the second person's turn, they just select the biggest cookie on the plate at that time. What's unfair about that?

Top

 Post subject: Re: Thue–Morse sequencePosted: Sat May 16, 2015 12:02 pm

Joined: Thu Jun 07, 2007 3:25 pm
Posts: 3967
Location: Berlin, Germany
Dude wrote:
Little John wrote:
when constantly alternating, this is unfairly always the same person!

Huh? When it's the second person's turn, they just select the biggest cookie on the plate at that time. What's unfair about that?

Say the cookies have the sizes
8,7,6,5,4,3,2,1.

Choosing the "normal" way,
• Alice gets 8+6+4+2 = 20
• Bob gets 7+5+3+1 = 16.

Choosing according to the Thue-Morse sequence,
• Alice gets 8+5+3+2 = 18
• Bob gets 7+6+4+1 = 18.

_________________
Please excuse my flawed English. My native language is PureBasic.
Search
RSBasic's backups

Top

 Post subject: Re: Thue–Morse sequencePosted: Sat May 16, 2015 12:09 pm

Joined: Mon Feb 16, 2015 2:49 pm
Posts: 1907
Mind = blown. Now I feel like an idiot.

Top

 Post subject: Re: Thue–Morse sequencePosted: Sat May 16, 2015 1:47 pm
 PureBasic Expert

Joined: Sun Aug 08, 2004 5:21 am
Posts: 3710
Location: Netherlands
So that's what you needed pop count for

I don't know if you have to call this ThueMorse procedure often and if its speed is important but & 1 is much faster compared to % 2 .

_________________
macOS 10.15 Catalina, Windows 10

Top

 Post subject: Re: Thue–Morse sequencePosted: Sat May 16, 2015 2:36 pm

Joined: Tue Nov 09, 2010 10:15 pm
Posts: 1719
Dude wrote:
:o Mind = blown. Now I feel like an idiot.

...but now you know why it is still common practice--since nobody looks at it this way. And also now, we are going to have a lot of complainers from every team captain who was stuck choosing second in a "schoolyard pick".

Top

 Post subject: Re: Thue–Morse sequencePosted: Sat May 16, 2015 2:49 pm
 PureBasic Expert

Joined: Sun Aug 08, 2004 5:21 am
Posts: 3710
Location: Netherlands
Just for fun, here's another approach to your ThueMorse procedure.
It takes advantage of the parity flag since you only need to know if the number of bits is odd or even.
Code:
Procedure ThueMorse(k.l)
!mov eax, [p.v_k]
!mov edx, eax
!shr edx, 16
!xor eax, edx
!xor al, ah
!setnp al
!and eax, 1
ProcedureReturn
EndProcedure

_________________
macOS 10.15 Catalina, Windows 10

Top

 Post subject: Re: Thue–Morse sequencePosted: Sat May 16, 2015 9:41 pm

Joined: Thu Jun 07, 2007 3:25 pm
Posts: 3967
Location: Berlin, Germany
Dude wrote:
:o Mind = blown. Now I feel like an idiot.

I think the example that I posted actually makes the situation clearer.
But the example is only there because you asked, so thank you for your question.

wilbert wrote:
I don't know if you have to call this ThueMorse procedure often and if its speed is important but & 1 is much faster compared to % 2 .

Dooh! I knew that ... some time ago. Seems I had forgotten it in the meantime.

wilbert wrote:
Just for fun, here's another approach to your ThueMorse procedure.
It takes advantage of the parity flag since you only need to know if the number of bits is odd or even.

Cool! Thank you very much, wilbert! I'll definitely use this version in my private math library.
In the first post here I left the code as is for the record and for comparison, and I added a link to your code, which is considerably faster than mine. I think this gain in speed can be important e.g. when using the ThueMorse() function for drawing a Koch snowflake, because then it will be called pretty often, and it won't look good when drawing takes place too slow. Thanks again!

_________________
Please excuse my flawed English. My native language is PureBasic.
Search
RSBasic's backups

Top

 Post subject: Re: Thue–Morse sequencePosted: Sat May 16, 2015 10:59 pm

Joined: Wed Aug 31, 2005 11:09 pm
Posts: 3698
Location: Italy
Very interesting, thank you.

_________________

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 9 posts ]

 All times are UTC + 1 hour

#### Who is online

Users browsing this forum: No registered users and 22 guests

 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 forum

Search for:
 Jump to:  Select a forum ------------------ PureBasic    Coding Questions    Game Programming    3D Programming    Assembly Programming    The PureBasic Editor    The PureBasic Form Designer    General Discussion    Feature Requests and Wishlists    Tricks 'n' Tips Bug Reports    Bugs - Windows    Bugs - Linux    Bugs - Mac OSX    Bugs - IDE    Bugs - Documentation OS Specific    AmigaOS    Linux    Windows    Mac OSX Miscellaneous    Announcement    Off Topic Showcase    Applications - Feedback and Discussion    PureFORM & JaPBe    TailBite