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

All times are UTC + 1 hour




Post new topic Reply to topic  [ 9 posts ] 
Author Message
 Post subject: Thue–Morse sequence
PostPosted: Sat May 16, 2015 11:34 am 
Offline
Addict
Addict

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
      !add eax, edx
      ;x = (x + (x >> 4)) & $0f0f0f0f0f
      !mov edx, eax
      !shr edx, 4
      !add eax, edx
      !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
 Profile  
Reply with quote  
 Post subject: Re: Thue–Morse sequence
PostPosted: Sat May 16, 2015 11:42 am 
Offline
Addict
Addict

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
 Profile  
Reply with quote  
 Post subject: Re: Thue–Morse sequence
PostPosted: Sat May 16, 2015 12:02 pm 
Offline
Addict
Addict

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
 Profile  
Reply with quote  
 Post subject: Re: Thue–Morse sequence
PostPosted: Sat May 16, 2015 12:09 pm 
Offline
Addict
Addict

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


Top
 Profile  
Reply with quote  
 Post subject: Re: Thue–Morse sequence
PostPosted: Sat May 16, 2015 1:47 pm 
Offline
PureBasic Expert
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
 Profile  
Reply with quote  
 Post subject: Re: Thue–Morse sequence
PostPosted: Sat May 16, 2015 2:36 pm 
Offline
Addict
Addict
User avatar

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".

(I read your first post asking why, and immediately opened excel to map it out for you, then saw LJ already had done it.)


Top
 Profile  
Reply with quote  
 Post subject: Re: Thue–Morse sequence
PostPosted: Sat May 16, 2015 2:49 pm 
Offline
PureBasic Expert
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
 Profile  
Reply with quote  
 Post subject: Re: Thue–Morse sequence
PostPosted: Sat May 16, 2015 9:41 pm 
Offline
Addict
Addict

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. :oops:

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
 Profile  
Reply with quote  
 Post subject: Re: Thue–Morse sequence
PostPosted: Sat May 16, 2015 10:59 pm 
Offline
Addict
Addict
User avatar

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

_________________
[ My little PureBasic review ]


Top
 Profile  
Reply with quote  
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 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 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

Search for:
Jump to:  

 


Powered by phpBB © 2008 phpBB Group
subSilver+ theme by Canver Software, sponsor Sanal Modifiye