Thue–Morse sequence

[Little John]

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:
Replaced "% 2" wth "& 1".
See below for a fast ASM version of ThueMorse() by wilbert.

Code: Select all

; 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) & 1
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) & 1]
      *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")

[Dude]

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?

[Little John]

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.

[Dude]

Mind = blown. Now I feel like an idiot.

[wilbert]

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 .

[Tenaja]

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

[wilbert]

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: Select all

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

[Little John]

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.

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.

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!

[luis]

Very interesting, thank you.