FizzBuzz問題（独自解法）

　今回は Twitter（X) のタイムラインで見かけた Fizz Buzz 問題の解法について書いてみたいと思います。ウィキペディアにも書いてあるように Fizz Buzz 問題とは１から１００までを言い合う遊びで３の倍数の場合は数字の代わりに Fizz と言い、５の倍数の場合は Buzz、両者の倍数の場合は Fizz Buzz と言うゲームです。

　FizzBuzz 問題を解くプログラムを作ること自体は容易なのですが、面白くするために高速化という観点から剰余算を使わないという制約を設けます。また、FizzBuzz の間にはスペースを入れず、それぞれの数字や 単語の後にはスペースを１個入れることとします。

　素数を求める時によく使われる「エラトステネスの篩（ふるい）」でのフラグ設定のように３周期のカウンタと５周期のカウンタを持つことでそれぞれの倍数であることを判断できます。
　最初に考えたＣ言語のソースは次のようなものでした。

FizzBuzz 問題の解答プログラム（Ｃ言語）

/* * FizzBuzz Solver Ver 0.01 2023/09/21 by skyriver */ #include <stdio.h> int main( void ) { for( int i=1, f=3, b=5; i <= 100; i++ ) { if( --f == 0 ) { f = 3; printf( "Fizz" ); } if( --b == 0 ) { b = 5; printf( "Buzz" ); } else if( f != 3 ) { printf( "%d", i ); } putchar( ' ' ); } return 0; }

　ネット上のコンパイラ環境サービスで実行結果を確かめることもできます（便利な世の中になったものですね）。

　上述のように３と５のカウンタを持っているので全体は１５周期の繰り返しになり、４ビットでカウントできます。ならば１５周期のカウンタだけを使って処理できないものでしょうか？

　ここで１５以内の３と５の倍数について考えてみます。両者の倍数である１５を除外して列挙すると

• ３の倍数
  　0011，0110，1100，1001
  
• ５の倍数
  　0101，1010
  

となり、いずれも１が２個で巡回ローテートしたものを同一視すると２つのパターン（0011，0101）に縮退されます。かつ、１が２個のパターンを網羅しています。
　更に面白いことに相互を XOR してみると他のパターンに推移するので、これらの３の倍数と５の倍数は２進数の観点で見ると密接な関係があるかのように思えてきます。
　この特徴を利用して Z80 のアセンブリ言語で FizzBuzz 問題を解くプログラムを作ってみることにしました。上記は独自の解析なので恐らくこの手法による FizzBuzz プログラムは世界初だと思いますｗ

　１のビットの数が２個だった場合、上述のように３か５の倍数ということになるのですが、どちらに属するかの判断方法は簡単そうに見えて中々思いつきませんでした。
　最も単純なのは

　　　CP 5
　　　JR Z,Buzz
　　　CP 10
　　　JR Z,Buzz

のような８バイトものコードになってしまいます。漸く思い付いたのが次の方法です。

　　　SUB 5
　　　OR A
　　　JP PE,Buzz

如何でしょう。引き算後のビット１の総数（パリティ）で判断できました（ほかに良い方法があればコメント下さい）。

★追記　2023/09/23　｛
　もっと判り易く、簡潔な判定方法を思い付きました^^
　　　AND 5
　　　JP PE,Buzz
}

★追記　2023/09/23　{
　ビット数の判定をループ処理方式

　　L1: LD BC,4 * 256 + 0
　　　　XOR A ; clear bit counter
　　　　LD L,D
　　L2: RRC L
　　　　ADC A,C
　　　　DJNZ L2
　　　　CP 2
　　　　JR NZ,DspNum

　から下記のループ処理無しの方式に改善してみました。

　　　　LD A,D
　　　　OR A
　　　　JP PO,DspNum
　　　　CP 0FH
　　　　JR Z,Both
}

　できたソースを下記に示します。ＣＰ／Ｍ用に作成していますがＤＯＳコールしているのは１文字出力サービスのみですので他の環境にも移植は容易だと思います。メインループ処理の簡潔さを堪能してください。

FizzBuzz 問題の解答プログラム（Ｚ８０アセンブリ）

; FizzBuzz solver by skyriver ; Ver 0.02 2023/09/22 ; Ver 0.03 2023/09/23 ; Ver 0.04 2023/09/23 ; Ver 0.05 2023/09/23 ; Ver 0.05 2023/09/23 ; Ver 0.06 2023/09/24(95 bytes) ; Ver 0.07 2023/09/27 improve DspNum(93 bytes) 0005 DosSrv EQU 5 ; DOS Service 0002 FnCout EQU 2 ; console out(E:data) 0064 MaxNum EQU 100 ; repeat until this number 0000' ASEG ORG 0100H 0100 01 64F1 Start: LD BC,256 * MaxNum + 0F1H ; B:loop counter, C:15 counter 0103 79 Loop: LD A,C 0104 21 0153 LD HL,MsgFiz 0107 0C INC C 0108 28 17 JR Z,Both ; if 15 010A B7 OR A 010B E2 0128 JP PO,DspNum ; if 1,2,4,7,8,11,13,14 010E E6 05 AND 5 0110 E2 0116 JP PO,Dsp ; if x3 0113 21 0158 DspBuz: LD HL,MsgBuz 0116 CD 013D Dsp: CALL Puts 0119 3E 20 Next: LD A,' ' 011B CD 0148 CALL Putch 011E 10 E3 DJNZ Loop 0120 C9 RET 0121 0E F1 Both: LD C,0F1H ; restart 15 counter 0123 CD 013D CALL Puts 0126 18 EB JR DspBuz 0128 3E 65 DspNum: LD A,MaxNum + 1 012A 90 SUB B 012B 11 FF0A LD DE,256 * (-1) + 10 012E 6F DspN10: LD L,A 012F 93 SUB E 0130 14 INC D ; not affect to Cy 0131 30 FB JR NC,DspN10 0133 7A LD A,D ; get 10s digit 0134 C4 0146 CALL NZ,PutNum 0137 7D LD A,L 0138 CD 0146 CALL PutNum 013B 18 DC JR Next ; put string ; HL <- string addr ; 013D 7E Puts: LD A,(HL) 013E B7 OR A 013F C8 RET Z 0140 CD 0148 CALL Putch 0143 23 INC HL 0144 18 F7 JR Puts ; put number with ascii ; A <- data 0146 C6 30 PutNum: ADD A,'0' ; put char ; A <- data 0148 C5 Putch: PUSH BC 0149 E5 PUSH HL 014A 5F LD E,A 014B 0E 02 LD C,FnCout 014D CD 0005 CALL DosSrv 0150 E1 POP HL 0151 C1 POP BC 0152 C9 RET 0153 46 69 7A 7A MsgFiz: DB "Fizz", 0 0157 00 0158 42 75 7A 7A MsgBuz: DB "Buzz", 0 015C 00 END Start Macros: Symbols: 0121 BOTH 0005 DOSSRV 0116 DSP 0113 DSPBUZ 012E DSPN10 0128 DSPNUM 0002 FNCOUT 0103 LOOP 0064 MAXNUM 0158 MSGBUZ 0153 MSGFIZ 0119 NEXT 0148 PUTCH 0146 PUTNUM 013D PUTS 0100 START No Fatal error(s)

　上のプログラムの出力結果は次のようになります。

1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz 16 17 Fizz 19 Buzz Fizz 22 23 Fizz Buzz 26 Fizz 28 29 FizzBuzz 31 32 Fizz 34 Buzz Fizz 37 38 Fizz Buzz 41 Fizz 43 44 FizzBuzz 46 47 Fizz 49 Buzz Fizz 52 53 Fizz Buzz 56 Fizz 58 59 FizzBuzz 61 62 Fizz 64 Buzz Fizz 67 68 Fizz Buzz 71 Fizz 73 74 FizzBuzz 76 77 Fizz 79 Buzz Fizz 82 83 Fizz Buzz 86 Fizz 88 89 FizzBuzz 91 92 Fizz 94 Buzz Fizz 97 98 Fizz Buzz

　上記のソースよりは少し前のバージョンですが、ネット上のサービスとして公開されている MSX のエミュ環境である ＭＳＸＰｅｎでも実行できました（重ねて便利な世の中に・・）。

タグ：C言語 Z80アセンブリ tio MSXPen FizzBuzz