3
\$\begingroup\$

Since the FizzBuzz challenge is about developing ideas, I've added

  • 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)
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
; --------------------------------------

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 ()
AdjustCounters:
        sub     bl,(ROWS-1) mod 3
        ja      .3a
        add     bl,3
.3a:    sub     bh,(ROWS-1) mod 5
        ja      .5a
        add     bh,5
.5a:    sub     cl,(ROWS-1) mod 7
        ja      .7a
        add     cl,7
.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)
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
; --------------------------------------

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!

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.