yasuokaの日記： Z80における「手抜き」回転行列の改良

一昨日・昨日の日記を読み返していて、これ、今の私(安岡孝一)だったら、sinθ≒1/8じゃなくて、sinθ≒511/4096にしちゃうんだろうな、と思えてきた。その方がcosθ=127/128に近いからだ。

　┌　cosθ -sinθ　┐　　┌　x　┐
　└　sinθ  cosθ　┘　　└　y　┘

ただ、sinθ≒1/8に比べると、sinθ≒511/4096はインパクトが弱いし、何よりプログラムが長くなる。HLレジスタのHレジスタに符号付整数、Lレジスタに256を分母とする分数が入っているとすると、511/4096の乗算は

7C      LD A,H
2F     CPL
5F      LD E,A
CB 2B  SRA E
07    RLCA
9F     SBC A,A
57      LD D,A
19     ADD HL,DE
7D      LD A,L
CB 2C  SRA H
1F     RRA
CB 2C  SRA H
1F     RRA
CB 2C  SRA H
1F     RRA
6F      LD L,A

となってしまって、かなり長いし読みにくい。うーん、もうちょっと何とかならないかな…。

sinθ=1/16とすると

[minet (45149)]

sinθ=1/x のとき cosθ≒1-1/(2x²) [srad.jp]
から、
cosθ≒511/512
sinθ=1/16
はどうでしょう？

Re:sinθ=1/16とすると

[yasuoka (21275)]

k=9の場合 [srad.jp]ですね。これ、4ビットシフトを無理矢理

7C         LD A,H
07       RLCA
9F        SBC A,A
E5       PUSH HL
21 01 00   LD HL,1
39        ADD HL,SP
ED 67     RRD
2B        DEC HL
ED 67     RRD
E1        POP HL

でやってみようとしたり、結構たのしく考えたんですけど、ちょっと回転量が小さすぎて、結局k=7の方を採用した覚えがあるのです。

Re:sinθ=1/16とすると

[minet (45149)]

> ちょっと回転量が小さすぎて、

ああ、これは重要ですね。
今どきなら微小な回転を高速にやって「ぬるぬる」動かすところでしょうけど

sinθ＝1/128 はどうでしょうか?

[Kita_WH (48578)]

16ビットなら sinθ＝1/128＝1/(2^7)、cosθ＝32767/32768＝(2^15-1)/(2^15) 32ビットなら sinθ＝1/(2^15)、cosθ＝(2^31-1)/(2^31) などとするといかがでしょうか？ 機械語の演算は余りよくわからないのですが、構造が同じなので基本的に8ビットと同じ方法が使えそうです。 16ビットの場合800回ほど演算すると一回転で、10回転しても2%ぐらいの誤差なので、 精度はこちらの方が上がると思います。

--
Kitawaki

Re:sinθ＝1/128 はどうでしょうか?

[yasuoka (21275)]

えっと、イマイチ良くわからないのですけど、32767/32768って、16ビットじゃほとんど計算できない気がするのです。すみません、整数部と分数部に何ビットずつ使う実装を想定してるんでしょうか？

結果保持の桁数

[taka2 (14791)]

ここまでいくと、計算結果の精度(固定小数点で、小数点以下8bit)が足りなくなるんじゃないですかね。

昔(といっても、MS-DOS、V30、コプロなしぐらいのころ)いろいろ遊んで思い出としては、
回転行列が小数点以下8bitだと、ぐるぐる回してると目に見えて誤差がたまってきます。
で、積算する回転行列は整数部6bit小数部10bitにして、最後に一回だけ移動も含めた座標計算を行う、という形に落ち着きました。

#当初は特に最終目的もなく回転させたくて回転させてたんですが、最終的に出来たのはHOSの起動画面。記憶に頼ったコピーなので、本物とはだいぶかけ離れてましたが、リアルタイムにグルグル回すのはそれなりに楽しかった。

Z80における「手抜き」回転行列の改良の計算誤差

[yasuoka (21275)]

以下のプログラムを作ってみて、IX=6400H,IY=0000Hから回したところ、434回よびだしたところでIX=BF73H,IY=B251Hとなって、誤差が1%を超えました。sinθ≒1/8が190回 [srad.jp]だったので、まあまあ良くなってるんですけど、分数部8ビットだと「もう一声」かなぁ…。

DD E5 PUSH IX
FD E5 PUSH IY
06 02   LD B,2
E1     POP HL
7C      LD A,H
2F     CPL
5F      LD E,A
CB 2B  SRA E
07    RLCA
4F      LD C,A
9F     SBC A,A
57      LD D,A
19     ADD HL,DE
59      LD E,C
78      LD A,B
06 03   LD B,3
CB 2C  SRA H
CB 1D   RR L
10 FA DJNZ -4
D9     EXX
47      LD B,A
10 E7 DJNZ -23
FD 19  ADD IY,DE
E5    PUSH HL
D9     EXX
EB      EX DE,HL
FD 19  ADD IY,DE
D1     POP DE
B7      OR A
ED 52  SBC HL,DE
EB      EX DE,HL
DD 19  ADD IX,DE
C9     RET

回転行列と三角行列

[Tellur52 (36331)]

Z80の最盛期に微妙に間に合わなかった手法として、
回転行列を上三角行列と下三角行列の積に分解するやり方があります。

R=UDU (三角行列の非対角成分はu_12=-tan(θ/2), d_21=sinθ)

Wikipediaの記事 [wikipedia.org]によれば1986年に論文で発表されたものらしいので、
実際には使われた例は無さそうですが。

これの良い所は係数の精度が悪くてもdet(R)=1が保証される点や、
可逆的に逆回転を行える点。
動径方向の累積誤差は殆ど無いとみられます。

恐らくsinθ≒1/8, tan(θ/2)≒1/16なんて粗い値を使っても、
遠目にはなんちゃって円運動に見えてくれるのではないでしょうか。

Paethの回転アルゴリズム

[yasuoka (21275)]

このアルゴリズム、かなりの優れモノのようです。私(安岡孝一)の今日の日記 [srad.jp]にちょっとだけ書いてみたので、よければどうぞ。