Z80での高速な乗算処理（その２）最適化

　Z80 での unsigned 8bit の新たな乗算方式を提案した前回の記事「Z80での高速な乗算処理」は予想以上に多くの閲覧があり、驚きました。

　前回の記事で書いたようにコードの最適化をあまりしていなかったので今回は最適化について書いてみたいと思います。Z80 アセンブラは直行性の要素が少ない反面、パズルを解くような面白さがあるので方式検討とコーディング（最適化）で二度楽しめます ^^

★追記　2023/02/19　{
　Z80 のアセンブラ経験者の方であれば前回の記事の最適化前のソースの高速化を少し考えてから本記事を読むと本記事の内容がより面白いものになるかと思います。
}

1. Twitter での反響
   　ブログの閲覧もそうですが地味なメッセージであったにもかかわらず Twitter でも予想以上の反響を頂きました。
   　具体的なコードを示された方もあり、私がタイムラインで確認できた中で最も高速だったのは、私のメッセージに対して最初（約４時間後）にコードを提示されたメッセージのものです。
   　下記にコードを引用させて頂きます（Twitter 上の実際のコードには判り易いコメントを付けられています）。
   　未検証とのことでしたが、当方で検証した結果、問題ありませんでした。平均ステート数は 141.5 でメチャ高速です。
   
   

   タイムライン上の最速コード（Z80アセンブラ）

   ; unsigned 8 bits fast multi(my method) 24lines ; fastest code in Twitter time line ; x*y = (x^2 + y^2 - (x-y)^2)/2 ; E <- data0 ; L <- data1 ; HL -> data0 * data1 0188 7B TwMul: LD A,E ; 4 0189 95 SUB L ; 4 018A 30 03 JR NC,TwMu10 ; 12/7 018C ED 44 NEG ; 8 018E EB EX DE,HL ; 4 018F 26 03 TwMu10: LD H,HIGH MULTBL+1 ; 7 0191 46 LD B,(HL) ; 7 0192 25 DEC H ; 4 0193 4E LD C,(HL) ; 7 0194 6F LD L,A ; 4 0195 54 LD D,H ; 4 0196 1A LD A,(DE) ; 7 0197 96 SUB (HL) ; 7 0198 14 INC D ; 4 0199 24 INC H ; 4 019A 66 LD H,(HL) ; 7 019B 6F LD L,A ; 4 019C 1A LD A,(DE) ; 7 019D 9C SBC A,H ; 4 019E 67 LD H,A ; 4 019F 09 ADD HL,BC ; 11 01A0 CB 1C RR H ; 8 01A2 CB 1D RR L ; 8 01A4 C9 RET ; 10 ; Max 145 = 4+4+(7+8+4)+7+7+4+7+4+4+7+7+4+4+7+4+7+4+4+11+8+8+10  ; Min 138 = 4+4+(12)+7+7+4+7+4+4+7+7+4+4+7+4+7+4+4+11+8+8+10 ; Ave 141.5

   
   
   　私も Z80 の最適化には自信を持ってはいるのですが、上記のコードは処理の流れに淀みが無く、洗練されたコードで流石だと思いました。僭越ではありますが、気になったのは次の２点です。
   
   
   • "NEG" 後の "EX DE,HL" は必要なのか？
     　最初に気になったのは DE と HL の交換は必要ないのではないかと言うことです。ディバッガで追ってみて交換が必要である理由が判りました。この交換の必要性を机上で判ったのであればすごいですね。
     
     
   • 最後の二つのシフト命令
     　A-reg 以外のシフト命令は遅い（ 8 ステート）ので使用をなるべく避けたいところです。しかし、処理の流れ上これより速い方法は思い付きませんでした。
     
   
   　もっと速いコードを模索しましたが、これ以上のものは難しいと思います（少なくとも私は諦めました）。短時間でこのコードを作られた作者の方には流石と言う他ありません。
   
   
   
2. 更なる高速化
   　今回使った乗算方式の発案者としてはこのままではあれなのでコーディング上の高速化が難しいことから方式に戻って検討を行いました。
   　具体的には前項で二つ目に書いたシフト命令部分について考えてみました。最後に 1/2 するのであれば、最初からテーブル内の値を 1/2 にすればいいのではないかと言う発想です。そのためには LSB 分の計算（桁上り）を別ロジックで計算する必要があります。
   
   　それでは LSB からの桁上りが発生する条件について見てみましょう。今回の乗算方式（マイナス二乗法）は乗算を求めるために下記の式を用いています。
   
   

   x*y = (x^2 + y^2 - (x - y)^2) / 2

   
   　x,y の偶数／奇数の組合せでの各項の偶数／奇数及び桁上りの発生有無は下表のようになります（０：偶数（桁上り無し））、１：奇数（桁上り有り））。
   　"(x-y)^2" はマイナス項なので x,y が両者とも奇数の場合のみ桁上り（＋１）すればいいことになります。
   
   

   No.	x	y	x^2	y^2	(x - y)^2	carry
   1	0	0	0	0	0	0
   2	0	1	0	1	1	0
   3	1	0	1	0	1	0
   4	1	1	1	1	0	1

   
   　また、前項の 1 番目の DE,HL の交換の必要性の確認で判ったことですが、15 ビットの計算になるので副次的な効果として計算の順番を気にする必要も無くなります。
   
   
   
3. 最適化の結果
   　上記の処理をコーディングした結果を末尾に示します。平均ステート数は 140.5 となり、前項の最速コードより辛うじて速くなりました。
   　前回の最適化前のものも含めたステート数の一覧が下表になります。
   
   

   No.	Method	Max	Min	Average	ratio
   1	Normal method	363	315	339.0	1.00
   2	Minus square method	154	151	152.5	2.22
   3	Minus square method   (optimized)	142	139	140.5	2.41

   
   　コードは下記の通りで二乗計算のためのテーブル内の値を 1/2 にしています。
   
   

   最適化したコード（Z80アセンブラ）

   ; unsigned 8 bits fast multi(Minus square method) 27 lines ; x*y = (x^2 + y^2 - (x-y)^2)/2 ; E <- data0 ; L <- data1 ; HL -> data0 * data1 016A 7B FFMu8: LD A,E ; 4 016B A5 AND L ; 4 016C 1F RRA ; 4 016D 26 04 LD H,HIGH(MULTB2) ; 7 016F 54 LD D,H ; 4 0170 1A LD A,(DE) ; 7 0171 8E ADC A,(HL) ; 7 0172 4F LD C,A ; 4 0173 14 INC D ; 4 0174 24 INC H ; 4 0175 1A LD A,(DE) ; 7 0176 8E ADC A,(HL) ; 7 0177 57 LD D,A ; 4 0178 7B LD A,E ; 4 0179 95 SUB L ; 4 017A 30 02 JR NC,FFMu10 ; 12/7 017C ED 44 NEG ; 8 017E 6F FFMU10: LD L,A ; 4 017F 5E LD E,(HL) ; 7 0180 25 DEC H ; 4 0181 79 LD A,C ; 4 0182 96 SUB (HL) ; 7 0183 6F LD L,A ; 4 0184 7A LD A,D ; 4 0185 9B SBC A,E ; 4 0186 67 LD H,A ; 4 0187 C9 RET ; 10 ; Max 142 = 4+4+4+7+4+7+7+4+4+4+7+7+4+4+4+(7+8)+4+7+4+4+7+4+4+4+4+10  ; Min 139 = 4+4+4+7+4+7+7+4+4+4+7+7+4+4+4+(12)+4+7+4+4+7+4+4+4+4+10 ; Ave 140.5 ORG ($ + 255) AND 0FF00H ; (8bit ^ 2) / 2 table 0400 00 00 02 04 MULTB2: DB 000H,000H,002H,004H,008H,00CH,012H,018H ; low byte 0404 08 0C 12 18 0408 20 28 32 3C DB 020H,028H,032H,03CH,048H,054H,062H,070H 040C 48 54 62 70 0410 80 90 A2 B4 DB 080H,090H,0A2H,0B4H,0C8H,0DCH,0F2H,008H 0414 C8 DC F2 08 0418 20 38 52 6C DB 020H,038H,052H,06CH,088H,0A4H,0C2H,0E0H 041C 88 A4 C2 E0 0420 00 20 42 64 DB 000H,020H,042H,064H,088H,0ACH,0D2H,0F8H 0424 88 AC D2 F8 0428 20 48 72 9C DB 020H,048H,072H,09CH,0C8H,0F4H,022H,050H 042C C8 F4 22 50 0430 80 B0 E2 14 DB 080H,0B0H,0E2H,014H,048H,07CH,0B2H,0E8H 0434 48 7C B2 E8 0438 20 58 92 CC DB 020H,058H,092H,0CCH,008H,044H,082H,0C0H 043C 08 44 82 C0 0440 00 40 82 C4 DB 000H,040H,082H,0C4H,008H,04CH,092H,0D8H 0444 08 4C 92 D8 0448 20 68 B2 FC DB 020H,068H,0B2H,0FCH,048H,094H,0E2H,030H 044C 48 94 E2 30 0450 80 D0 22 74 DB 080H,0D0H,022H,074H,0C8H,01CH,072H,0C8H 0454 C8 1C 72 C8 0458 20 78 D2 2C DB 020H,078H,0D2H,02CH,088H,0E4H,042H,0A0H 045C 88 E4 42 A0 0460 00 60 C2 24 DB 000H,060H,0C2H,024H,088H,0ECH,052H,0B8H 0464 88 EC 52 B8 0468 20 88 F2 5C DB 020H,088H,0F2H,05CH,0C8H,034H,0A2H,010H 046C C8 34 A2 10 0470 80 F0 62 D4 DB 080H,0F0H,062H,0D4H,048H,0BCH,032H,0A8H 0474 48 BC 32 A8 0478 20 98 12 8C DB 020H,098H,012H,08CH,008H,084H,002H,080H 047C 08 84 02 80 0480 00 80 02 84 DB 000H,080H,002H,084H,008H,08CH,012H,098H 0484 08 8C 12 98 0488 20 A8 32 BC DB 020H,0A8H,032H,0BCH,048H,0D4H,062H,0F0H 048C 48 D4 62 F0 0490 80 10 A2 34 DB 080H,010H,0A2H,034H,0C8H,05CH,0F2H,088H 0494 C8 5C F2 88 0498 20 B8 52 EC DB 020H,0B8H,052H,0ECH,088H,024H,0C2H,060H 049C 88 24 C2 60 04A0 00 A0 42 E4 DB 000H,0A0H,042H,0E4H,088H,02CH,0D2H,078H 04A4 88 2C D2 78 04A8 20 C8 72 1C DB 020H,0C8H,072H,01CH,0C8H,074H,022H,0D0H 04AC C8 74 22 D0 04B0 80 30 E2 94 DB 080H,030H,0E2H,094H,048H,0FCH,0B2H,068H 04B4 48 FC B2 68 04B8 20 D8 92 4C DB 020H,0D8H,092H,04CH,008H,0C4H,082H,040H 04BC 08 C4 82 40 04C0 00 C0 82 44 DB 000H,0C0H,082H,044H,008H,0CCH,092H,058H 04C4 08 CC 92 58 04C8 20 E8 B2 7C DB 020H,0E8H,0B2H,07CH,048H,014H,0E2H,0B0H 04CC 48 14 E2 B0 04D0 80 50 22 F4 DB 080H,050H,022H,0F4H,0C8H,09CH,072H,048H 04D4 C8 9C 72 48 04D8 20 F8 D2 AC DB 020H,0F8H,0D2H,0ACH,088H,064H,042H,020H 04DC 88 64 42 20 04E0 00 E0 C2 A4 DB 000H,0E0H,0C2H,0A4H,088H,06CH,052H,038H 04E4 88 6C 52 38 04E8 20 08 F2 DC DB 020H,008H,0F2H,0DCH,0C8H,0B4H,0A2H,090H 04EC C8 B4 A2 90 04F0 80 70 62 54 DB 080H,070H,062H,054H,048H,03CH,032H,028H 04F4 48 3C 32 28 04F8 20 18 12 0C DB 020H,018H,012H,00CH,008H,004H,002H,000H 04FC 08 04 02 00 0500 00 00 00 00 DB 000H,000H,000H,000H,000H,000H,000H,000H ; high byte 0504 00 00 00 00 0508 00 00 00 00 DB 000H,000H,000H,000H,000H,000H,000H,000H 050C 00 00 00 00 0510 00 00 00 00 DB 000H,000H,000H,000H,000H,000H,000H,001H 0514 00 00 00 01 0518 01 01 01 01 DB 001H,001H,001H,001H,001H,001H,001H,001H 051C 01 01 01 01 0520 02 02 02 02 DB 002H,002H,002H,002H,002H,002H,002H,002H 0524 02 02 02 02 0528 03 03 03 03 DB 003H,003H,003H,003H,003H,003H,004H,004H 052C 03 03 04 04 0530 04 04 04 05 DB 004H,004H,004H,005H,005H,005H,005H,005H 0534 05 05 05 05 0538 06 06 06 06 DB 006H,006H,006H,006H,007H,007H,007H,007H 053C 07 07 07 07 0540 08 08 08 08 DB 008H,008H,008H,008H,009H,009H,009H,009H 0544 09 09 09 09 0548 0A 0A 0A 0A DB 00AH,00AH,00AH,00AH,00BH,00BH,00BH,00CH 054C 0B 0B 0B 0C 0550 0C 0C 0D 0D DB 00CH,00CH,00DH,00DH,00DH,00EH,00EH,00EH 0554 0D 0E 0E 0E 0558 0F 0F 0F 10 DB 00FH,00FH,00FH,010H,010H,010H,011H,011H 055C 10 10 11 11 0560 12 12 12 13 DB 012H,012H,012H,013H,013H,013H,014H,014H 0564 13 13 14 14 0568 15 15 15 16 DB 015H,015H,015H,016H,016H,017H,017H,018H 056C 16 17 17 18 0570 18 18 19 19 DB 018H,018H,019H,019H,01AH,01AH,01BH,01BH 0574 1A 1A 1B 1B 0578 1C 1C 1D 1D DB 01CH,01CH,01DH,01DH,01EH,01EH,01FH,01FH 057C 1E 1E 1F 1F 0580 20 20 21 21 DB 020H,020H,021H,021H,022H,022H,023H,023H 0584 22 22 23 23 0588 24 24 25 25 DB 024H,024H,025H,025H,026H,026H,027H,027H 058C 26 26 27 27 0590 28 29 29 2A DB 028H,029H,029H,02AH,02AH,02BH,02BH,02CH 0594 2A 2B 2B 2C 0598 2D 2D 2E 2E DB 02DH,02DH,02EH,02EH,02FH,030H,030H,031H 059C 2F 30 30 31 05A0 32 32 33 33 DB 032H,032H,033H,033H,034H,035H,035H,036H 05A4 34 35 35 36 05A8 37 37 38 39 DB 037H,037H,038H,039H,039H,03AH,03BH,03BH 05AC 39 3A 3B 3B 05B0 3C 3D 3D 3E DB 03CH,03DH,03DH,03EH,03FH,03FH,040H,041H 05B4 3F 3F 40 41 05B8 42 42 43 44 DB 042H,042H,043H,044H,045H,045H,046H,047H 05BC 45 45 46 47 05C0 48 48 49 4A DB 048H,048H,049H,04AH,04BH,04BH,04CH,04DH 05C4 4B 4B 4C 4D 05C8 4E 4E 4F 50 DB 04EH,04EH,04FH,050H,051H,052H,052H,053H 05CC 51 52 52 53 05D0 54 55 56 56 DB 054H,055H,056H,056H,057H,058H,059H,05AH 05D4 57 58 59 5A 05D8 5B 5B 5C 5D DB 05BH,05BH,05CH,05DH,05EH,05FH,060H,061H 05DC 5E 5F 60 61 05E0 62 62 63 64 DB 062H,062H,063H,064H,065H,066H,067H,068H 05E4 65 66 67 68 05E8 69 6A 6A 6B DB 069H,06AH,06AH,06BH,06CH,06DH,06EH,06FH 05EC 6C 6D 6E 6F 05F0 70 71 72 73 DB 070H,071H,072H,073H,074H,075H,076H,077H 05F4 74 75 76 77 05F8 78 79 7A 7B DB 078H,079H,07AH,07BH,07CH,07DH,07EH,07FH 05FC 7C 7D 7E 7F

　以上、最適化について書きましたが個人的には中々面白い結果になったのではないかと思います。


★追記　2023/06/23
　「Z80での高速な乗算処理（その３）２バイト乗算への適用検討」の記事に２バイト乗算への適用検討について記載しました。


[TOP] [ 前へ ] 連載記事一覧 [ 次へ ]

タグ：Minus square method マイナス二乗法 高速乗算 符号なし8ビット Multiplication 乗算 Z80