Hofstadter Q sequence: Difference between revisions

=={{header|8086 Assembly}}==

<lang asm>puts: equ 9 ; MS-DOS syscall to print a string

cpu 8086

org 100h

section .text

;;; Generate first 1000 elements of Q sequence

mov cx,3 ; CX = N

mov di,Q+4 ; DI = place to store elements

mov dx,998 ; Generate 998 more terms

genq: mov si,cx ; SI = N

mov bp,cx ; BP = N

mov bx,cx ; BX = N

dec bx ; BX = N-1

dec bx ; BX = 2*(BX-1) (0-indexed, 2 bytes wide)

shl bx,1

add bx,Q

sub si,[bx] ; SI = N-Q(N-1)

dec bx ; previous element

dec bx

sub bp,[bx] ; BP = N-Q(N-2)

dec si ; SI = 2*(SI-1)

shl si,1

dec bp ; BP = 2*(BP-1)

shl bp,1

mov ax,[si+Q] ; Add the two terms together

add ax,[bp+Q] ; SS = DS in a .COM file, so this is OK

stosw ; Store

inc cx ; Generate next term

dec dx ; Decrement counter

jnz genq

;;; Print first 10 elements

mov ah,puts

mov dx,m10

int 21h

mov cx,10

mov bx,1

p10: call prterm

inc bx

loop p10

;;; Print 1000th element

mov ah,puts

mov dx,m1000

int 21h

mov bx,1000

;;; Print the term in BX

prterm: push bx ; Save term

dec bx

shl bx,1

mov ax,[bx+Q] ; Load term into AX

mov bp,10 ; Divisor

mov bx,num ; Number buffer pointer

.dgt: xor dx,dx

div bp ; Divide number by 10

dec bx

add dl,'0' ; DX = remainder, add '0'

mov [bx],dl ; Store digit

test ax,ax ; Done yet?

jnz .dgt ; If not, find next digit

mov dx,bx ; Print the number

mov ah,puts

int 21h

pop bx ; Restore term

ret

section .data

m10: db 'First 10 terms are: $'

m1000: db 13,10,'1000th term is: $'

db '*****' ; Number placeholder

num: db ' $'

Q: dw 1,1</lang>

{{out}}

<pre>First 10 terms are: 1 1 2 3 3 4 5 5 6 6

1000th term is: 502</pre>