Thue-Morse: Difference between revisions
Add 8080 assembly
m (→using 2's complement: added whitespace.) |
Not a robot (talk | contribs) (Add 8080 assembly) |
||
Line 9:
* YouTube entry: [https://www.youtube.com/watch?v=Tt5TTid6YXk Math and OCD - My story with the Thue-Morse sequence]
<br><br>
=={{header|8080 Assembly}}==
The 8080 processor has an internal flag to keep track of the parity of the result of the
last operation. This is ideal for generating the Thue-Morse sequence, as one can just count up
by incrementing a register, and then check the parity each time. If the parity is even, the corresponding
element in the Thue-Morse sequence is 0, if it is odd it is 1. You can even use the same register
to iterate over the array where you're storing the elements, and get the parity calculation entirely for free.
Unfortunately, this flag was not deemed very useful otherwise, and in the Z80 support for it was
dropped and replaced with a signed overflow flag. This is one of the few places where the Z80
is not backwards compatible with the 8080. This does mean that the binary produced by assembling this
program will only run correctly on a real 8080 (or a proper 8080 emulator).
The following program prints the first 256 elements of the Thue-Morse sequence, since that fits neatly
in an 8-bit register, but the same principle could be used with a counter of arbitrary size, as
after all, XOR is commutative.
<lang 8080asm> org 100h
;;; Write 256 bytes of ASCII '0' starting at address 200h
lxi h,200h ; The array is page-aligned so L starts at 0
mvi a,'0' ; ASCII 0
zero: mov m,a ; Write it to memory at address HL
inr l ; Increment low byte of pointer,
jnz zero ; until it wraps to zero.
;;; Generate the first 256 elements of the Thue-Morse sequence.
gen: jpe $+4 ; If parity is even, skip next instruction
inr m ; (If parity is odd,) increment byte at HL (0->1)
inr l ; Increment low byte of pointer (and set parity),
jnz gen ; Until it wraps again.
;;; Output using CP/M call
inr h ; Increment high byte,
mvi m,'$' ; and write the CP/M string terminator there.
mvi c,9 ; Syscall 9 = print string
lxi d,200h ; The string is at 200h
jmp 5</lang>
{{out}}
The line breaks are added for clarity, the program does not actually print them.
<pre>0110100110010110100101100110100110010110011010010110100110010110
1001011001101001011010011001011001101001100101101001011001101001
1001011001101001011010011001011001101001100101101001011001101001
0110100110010110100101100110100110010110011010010110100110010110</pre>
=={{header|Ada}}==
| |||