FizzBuzz - A quartet of solutions

• a third test case for which I chose divisibility by 7 and its accompanying tag "Go". This tag was purposely given a length other than 4 to resist writing an optimization that would otherwise impair adaptability.
• outputting in a redirection friendly manner. Ideal for console output, printing, and why not mention tape storage, but it complicates matters when using 'decrementing counters' as you'll see below.

I've explored a number of techniques, all equally valuable:

1. An elimination process
2. A binary decision tree
3. Decrementing counters
4. A lookup table

Everywhere a division was needed I chose to replace the usual div instruction by an aam instruction. This can only work if neither dividend nor divider exceed 255. It proved to be a winning move as it:

• conserves (a lot of) space
• avoids using an extra register for the divider
• delivers flags on the remainder (in AL!)

The output can easily be customized by changing the 3 compile-time variables (number of )COLS, (number of )ROWS, and WIDTH( of one column).
The only restrictions are that the product ROWSxCOLS must fall in [1,255] and that WIDTH must allow displaying the 3 digit number, a separator, and any combination of tags.

Elimination process.

The order in which the eliminations take place is crucial. Not only for obtaining correct results but also because choosing an optimal ordering reduces the number of divisions by 5 to 6 percent, as next table shows.

Processing     FizzBuzz   FizzBuzzGo   FizzBuzzGo+
255 numbers    (3,5)      (3,5,7)      (3,5,7,11)
--------------------------------------------------
poor ordering     697        1596         3199
best ordering     663        1498         2986


Eliminating the most numbers as early as possible is achieved by using the smaller dividers first. On FizzBuzzGo poor means 105, 35, 21, 15, 7, 5, 3 and best means 105, 15, 21, 35, 3, 5, 7.

COLS=3
ROWS=85
WIDTH=16
ORG     256
cld
mov     bp,1                    ;BP is current number [1,255]
Row:    push    bp                      ;(1)
mov     di,String
Col:    call    AddNumberToString       ; -> DI (AX)
call    ClassifyNumber          ; -> AL (AH)
call    AddTagsToString         ; -> DI (AL BX CX)
add     bp,ROWS                 ;Step to next column
cmp     bp,ROWS*COLS
jbe     Col
call    PrintString             ; -> (AX DX DI)
pop     bp                      ;(1)
inc     bp                      ;Step to next row
cmp     bp,ROWS
jbe     Row
int     20h                     ;DOS.Terminate
; --------------------------------------
ALIGN   16
; Sets bit 0 of AL if number in BP is divisible by 3
; Sets bit 1 of AL if number in BP is divisible by 5
; Sets bit 2 of AL if number in BP is divisible by 7
; IN (bp) OUT (al) MOD (ah)
ClassifyNumber:
mov     ax,bp
aam     3*5*7
jz      .111
mov     ax,bp
aam     3*5
jz      .011
mov     ax,bp
aam     3*7
jz      .101
mov     ax,bp
aam     5*7
jz      .110
mov     ax,bp
aam     3
jz      .001
mov     ax,bp
aam     5
jz      .010
mov     ax,bp
aam     7
jz      .100
.000:   mov     al,000b                 ;None
ret
.111:   mov     al,111b                 ;FizzBuzzGo
ret
.011:   mov     al,011b                 ;FizzBuzz
ret
.101:   mov     al,101b                 ;FizzGo
ret
.110:   mov     al,110b                 ;BuzzGo
ret
.001:   mov     al,001b                 ;Fizz
ret
.010:   mov     al,010b                 ;Buzz
ret
.100:   mov     al,100b                 ;Go
ret
; --------------------------------------
ALIGN   16
; IN (di,bp) OUT (di) MOD (ax)
mov     ax,"  "                 ;Right justify 3 digits
stosw
mov     ax,bp                   ;BP=[0,255]
aam
stosb
test    ah,ah
jz      .RET
mov     al,ah
aam
mov     [di-2],al
test    ah,ah
jz      .RET
mov     [di-3],ah
.RET:   ret
; --------------------------------------
ALIGN   16
; IN (al,di) OUT (di) MOD (al,bx,cx)
lea     bx,[di-3+WIDTH]         ;Start of next column
test    al,al
jz      .Align                  ;No tags needed
mov     byte [di]," "           ;Separator
inc     di
mov     si,Tags                 ;Show one or more tags
.Tag:   movzx   cx,[si]                 ;Length of current tag
inc     si
shr     al,1
jnc     .Skip
rep movsb
test    al,al
jnz     .Tag
jmp     .Align
.Space: mov     byte [di]," "           ;Align to start of next column
inc     di
.Align: cmp     di,bx
jb      .Space
ret
; --------------------------------------
ALIGN   16
; IN (di) OUT () MOD (ax,dx,di)
PrintString:
inc     di                      ;Remove trailing spaces (if any)
.Trim:  dec     di
cmp     byte [di-1]," "
je      .Trim
mov     ax,0A0Dh                ;Append carriage return and linefeed
stosw
mov     byte [di],"$" ;StringTerminator for DOS mov dx,String mov ah,09h ;DOS.PrintString int 21h ret ; -------------------------------------- Tags: db 4,'Fizz',4,'Buzz',2,'Go' String: rb WIDTH*COLS+3 ; --------------------------------------  Binary decision tree. Next table shows that using a binary tree reduces the number of divisions enormously. Moreover it gains importance as the number of test cases rises. Processing FizzBuzz FizzBuzzGo FizzBuzzGo+ 255 numbers (3,5) (3,5,7) (3,5,7,11) -------------------------------------------------- Elimination 663 1498 2986 Binary tree 510 765 1020  On FizzBuzzGo the number of divisions was reduced by 49 percent. It is very easy to turn this binary tree into something shorter that doesn't use any conditional jumps. I decided however to not keep it because I feel there's at least some contradiction in branchless binary tree. Moreover it was a bit slower. COLS=3 ROWS=85 WIDTH=16 ORG 256 cld mov bp,1 ;BP is current number [1,255] Row: push bp ;(1) mov di,String Col: call AddNumberToString ; -> DI (AX) call ClassifyNumber ; -> AL (AH) call AddTagsToString ; -> DI (AL BX CX) add bp,ROWS ;Step to next column cmp bp,ROWS*COLS jbe Col call PrintString ; -> (AX DX DI) pop bp ;(1) inc bp ;Step to next row cmp bp,ROWS jbe Row int 20h ;DOS.Terminate ; -------------------------------------- ALIGN 16 ; Sets bit 0 of AL if number in BP is divisible by 3 ; Sets bit 1 of AL if number in BP is divisible by 5 ; Sets bit 2 of AL if number in BP is divisible by 7 ; IN (bp) OUT (al) MOD (ah) ClassifyNumber: mov ax,bp aam 7 mov ax,bp jz .7y .7n: aam 5 mov ax,bp jz .7n5y .7n5n: aam 3 setz al ret ;0=None 1=Fizz .7n5y: aam 3 setz al add al,010b ret ;2=Buzz 3=FizzBuzz .7y: aam 5 mov ax,bp jz .7y5y .7y5n: aam 3 setz al add al,100b ret ;4=Go 5=FizzGo .7y5y: aam 3 setz al add al,110b ret ;6=BuzzGo 7=FizzBuzzGo ; -------------------------------------- ALIGN 16 ; IN (di,bp) OUT (di) MOD (ax) AddNumberToString: mov ax," " ;Right justify 3 digits stosw mov ax,bp ;BP=[0,255] aam add al,"0" stosb test ah,ah jz .RET mov al,ah aam add al,"0" mov [di-2],al test ah,ah jz .RET add ah,"0" mov [di-3],ah .RET: ret ; -------------------------------------- ALIGN 16 ; IN (al,di) OUT (di) MOD (al,bx,cx) AddTagsToString: lea bx,[di-3+WIDTH] ;Start of next column test al,al jz .Align ;No tags needed mov byte [di]," " ;Separator inc di mov si,Tags ;Show one or more tags .Tag: movzx cx,[si] ;Length of current tag inc si shr al,1 jnc .Skip rep movsb .Skip: add si,cx test al,al jnz .Tag jmp .Align .Space: mov byte [di]," " ;Align to start of next column inc di .Align: cmp di,bx jb .Space ret ; -------------------------------------- ALIGN 16 ; IN (di) OUT () MOD (ax,dx,di) PrintString: inc di ;Remove trailing spaces (if any) .Trim: dec di cmp byte [di-1]," " je .Trim mov ax,0A0Dh ;Append carriage return and linefeed stosw mov byte [di],"$"           ;StringTerminator for DOS
mov     dx,String
mov     ah,09h                  ;DOS.PrintString
int     21h
ret
; --------------------------------------
Tags:   db      4,'Fizz',4,'Buzz',2,'Go'
String: rb      WIDTH*COLS+3
; --------------------------------------


Decrementing counters.

Given that the output is to be redirection friendly and that the matrix on the screen shows up filled column wise, adjustments to these decrementing counters are necessary. These adjustments account for the missing decrements due to the GT 1 step when going to the next column. The numbers aren't processed in natural order. Hence.

Instead of decrementing I could have used incrementing on the counters. Usually (1) doing so requires an extra cmp instruction that will certainly add to the code size but not necessarily slow things down.
(1) It's possible to avoid the additional cmp while still incrementing when we start from negative numbers and move towards zero.

COLS=3
ROWS=85
WIDTH=16
ORG     256
cld
mov     bp,1                    ;BP is current number [1,255]
mov     cl,7                    ;CL is Go-counter
mov     bx,0503h                ;BH is Buzz-counter, BL is Fizz-counter
Row:    push    bx cx bp                ;(1)
mov     di,String
jmp     First
Col:    call    AdjustCounters          ; -> BX CL
First:  call    AddNumberToString       ; -> DI (AX)
call    DecrementCounters       ; -> AL BX CL
push    bx cx                   ;(2)
call    AddTagsToString         ; -> DI (AL BX CX)
pop     cx bx                   ;(2)
add     bp,ROWS                 ;Step to next column
cmp     bp,ROWS*COLS
jbe     Col
call    PrintString             ; -> (AX DX DI)
pop     bp cx bx                ;(1)
call    DecrementCounters       ; -> AL BX CL
inc     bp                      ;Step to next row
cmp     bp,ROWS
jbe     Row
int     20h                     ;DOS.Terminate
; --------------------------------------
ALIGN   16
; IN (bx,cl) OUT (bx,cl) MOD ()
sub     bl,(ROWS-1) mod 3
ja      .3a
.3a:    sub     bh,(ROWS-1) mod 5
ja      .5a
.5a:    sub     cl,(ROWS-1) mod 7
ja      .7a
.7a:    ret
; --------------------------------------
ALIGN   16
; IN (bx,cl) OUT (al,bx,cl) MOD ()
DecrementCounters:
dec     bl
jnz     .3nz
mov     bl,3                    ;Reset Fizz
.3nz:   setz    al
dec     bh
jnz     .5nz
mov     bh,5                    ;Reset Buzz
or      al,2
.5nz:   dec     cl
jnz     .7nz
mov     cl,7                    ;Reset Go
or      al,4
.7nz:   ret                             ;Classification in AL=[0,7]
; --------------------------------------
ALIGN   16
; IN (di,bp) OUT (di) MOD (ax)
mov     ax,"  "                 ;Right justify 3 digits
stosw
mov     ax,bp                   ;BP=[0,255]
aam
stosb
test    ah,ah
jz      .RET
mov     al,ah
aam
mov     [di-2],al
test    ah,ah
jz      .RET
mov     [di-3],ah
.RET:   ret
; --------------------------------------
ALIGN   16
; IN (al,di) OUT (di) MOD (al,bx,cx)
lea     bx,[di-3+WIDTH]         ;Start of next column
test    al,al
jz      .Align                  ;No tags needed
mov     byte [di]," "           ;Separator
inc     di
mov     si,Tags                 ;Show one or more tags
.Tag:   movzx   cx,[si]                 ;Length of current tag
inc     si
shr     al,1
jnc     .Skip
rep movsb
test    al,al
jnz     .Tag
jmp     .Align
.Space: mov     byte [di]," "           ;Align to start of next column
inc     di
.Align: cmp     di,bx
jb      .Space
ret
; --------------------------------------
ALIGN   16
; IN (di) OUT () MOD (ax,dx,di)
PrintString:
inc     di                      ;Remove trailing spaces (if any)
.Trim:  dec     di
cmp     byte [di-1]," "
je      .Trim
mov     ax,0A0Dh                ;Append carriage return and linefeed
stosw
mov     byte [di],"$" ;StringTerminator for DOS mov dx,String mov ah,09h ;DOS.PrintString int 21h ret ; -------------------------------------- Tags: db 4,'Fizz',4,'Buzz',2,'Go' String: rb WIDTH*COLS+3 ; --------------------------------------  Lookup table. The lookup table (LUT) is filled with classification bytes. No need to have the data in this table repeat itself. There's more to gain from re-using the same lookup data (caching) than that there's to loose on the additional instructions to fetch it. The LUT can either be created at run-time with an initialization routine or at compile-time. It's easy to fill the LUT by hand. For the simple FizzBuzz a mere 15 bytes. I chose to let the assembler do the work. Lookup tables are powerful instruments. I wonder if ever any applicant when confronted with the original FizzBuzz task has used this approach. Not sure about what the recruiter would have said either! COLS=3 ROWS=85 WIDTH=16 COUNT=ROWS*COLS if 3*5*7 < COUNT ;Avoid superfluous data COUNT=3*5*7 end if ORG 256 cld mov bp,1 ;BP is current number [1,255] Row: push bp ;(1) mov di,String Col: call AddNumberToString ; -> DI (AX) lea ax,[bp-1] aam COUNT ;Remainder will index the LUT movzx si,al mov al,[Lut+si] call AddTagsToString ; -> DI (AL BX CX) add bp,ROWS ;Step to next column cmp bp,ROWS*COLS jbe Col call PrintString ; -> (AX DX DI) pop bp ;(1) inc bp ;Step to next row cmp bp,ROWS jbe Row int 20h ;DOS.Terminate ; -------------------------------------- ALIGN 16 ; IN (di,bp) OUT (di) MOD (ax) AddNumberToString: mov ax," " ;Right justify 3 digits stosw mov ax,bp ;BP=[0,255] aam add al,"0" stosb test ah,ah jz .RET mov al,ah aam add al,"0" mov [di-2],al test ah,ah jz .RET add ah,"0" mov [di-3],ah .RET: ret ; -------------------------------------- ALIGN 16 ; IN (al,di) OUT (di) MOD (al,bx,cx) AddTagsToString: lea bx,[di-3+WIDTH] ;Start of next column test al,al jz .Align ;No tags needed mov byte [di]," " ;Separator inc di mov si,Tags ;Show one or more tags .Tag: movzx cx,[si] ;Length of current tag inc si shr al,1 jnc .Skip rep movsb .Skip: add si,cx test al,al jnz .Tag jmp .Align .Space: mov byte [di]," " ;Align to start of next column inc di .Align: cmp di,bx jb .Space ret ; -------------------------------------- ALIGN 16 ; IN (di) OUT () MOD (ax,dx,di) PrintString: inc di ;Remove trailing spaces (if any) .Trim: dec di cmp byte [di-1]," " je .Trim mov ax,0A0Dh ;Append carriage return and linefeed stosw mov byte [di],"$"           ;StringTerminator for DOS
mov     dx,String
mov     ah,09h                  ;DOS.PrintString
int     21h
ret
; --------------------------------------
ALIGN   16
Lut:    times COUNT db -4*(((% mod 7)-7)/7)-2*(((% mod 5)-5)/5)-(((% mod 3)-3)/3)
Tags:   db      4,'Fizz',4,'Buzz',2,'Go'
String: rb      WIDTH*COLS+3
; --------------------------------------


Execution time

All testing was done on a Pentium 166MHz running in real address mode.

                complete      w/o api call   w/o routines
---------------------------------------------------------
Elimination    172133 µsec      693 µsec       200 µsec
Binary tree    171928 µsec      474 µsec       105 µsec
Counters       171916 µsec      420 µsec        52 µsec
Lookup table   171747 µsec      299 µsec        43 µsec


There's not much that can be said when looking at the total execution time.
Removing the DOS api call shows how predominant it really is.
Striking all of the common routines finally establishes a ranking of some kind.

Code size

                complete                     w/o routines
---------------------------------------------------------
Elimination     260 bytes                       98 bytes
Binary tree     244 bytes                       82 bytes
Counters        260 bytes                      122 bytes
Lookup table    294 bytes                      153 bytes


After striking all of the common routines it becomes clear(er) that - as is often the case - there's a price to pay for the increased speed.

Extensibility

I wrote these programs with extensibility in mind. If the number of test cases increases, the versions that use an elimination process or a binary tree, rapidly become more complex. The version that uses decrementing counters can be modified easily. But the version that uses a lookup table needs very little change indeed.

See how I gracefully didn't use the CH, DL, and DH registers so they could easily be used for the 4th, 5th, and 6th test cases?
Why then not try your hand at FizzBuzzGoYesWeCan (dividers 3, 5, 7, 11, 13, and 17)? Using prime numbers guarantees every tag will show up by itself at least once.

! Hint: Given the numbers range from 1 to 255, it's useless to test with dividers greater than 255. The aam instruction wouldn't digest it anyway.

Have fun!

• Why doesn't >!  work for a spoiler? – Sep Roland Feb 12 '17 at 15:41