ふるた技工所(てっこうしょ)

キーワードサーチ

▼キーワード検索

プロフィール

Aちゃん22

フリーページ

2020.08.20

筆算方式で uint32_t の平方根を求める処理 - MO メディアから発掘したコード

カテゴリ：ソフト開発日誌

MO メディアをサルベージしていたら、懐かしいコードが見つかる。筆算方式で uint32_t (32 bit で表した正の整数) の平方根を求めるコードだ。8086 Assembler のコードで記述してある。アルゴリズムの概要をコメントに書いてあるので他の言語やアセンブラでも容易に書き直せると思う。

model   small,c
codeseg

;in A
;
; X=0
; w=0
; Count=16
; @@l1:
; w<<=1
; X<<2bit<<A
; save X
; X-=(w+1)
; if cond CY
;       {recover X
;       }
;   else
;       {w|=2;
;       }
; LOOP @@l1;
; w>>1 -> ans

;in     dx:ax
;
proc    NOLANGUAGE sqrroot
xor     si,si   ;bl:si  X
xor     di,di   ;bh:di  w
mov     cx,10h
mov     bh,0c0h
jmp     @@l0in
even
@@l0:
dec     cx
jz      @@exit
shl     ax,1
rcl     dx,1
shl     ax,1
rcl     dx,1
@@l0in:
test    dh,bh
jz      @@l0
xor     bx,bx
even
@@l1:
shl     di,1
rcl     bh,1
shl     ax,1
rcl     dx,1
rcl     si,1
rcl     bl,1
shl     ax,1
rcl     dx,1
rcl     si,1
rcl     bl,1
push    si
push    bx
stc
sbb     si,di
sbb     bl,bh
jnb     @@j1
pop     bx
pop     si
loop    @@l1
shr     bh,1
rcr     di,1
mov     ax,di
ret
@@j1:
add     sp,4
inc     di
inc     di
loop    @@l1
shr     bh,1
rcr     di,1
mov     ax,di
@@exit:
ret
endp
even

public  ulsqrroot
proc    ulsqrroot
arg     @@a:dword
uses    si,di
mov     dx,[word high @@a]
mov     ax,[word low  @@a]
call    sqrroot
ret
endp
even
end

コメントのアルゴリズムに対し、実装は上位桁に 0 が続く場合、計算を少し速くする工夫がある。それ以上の変わった処理やアセンブラ独特の高速化は導入していない素朴な処理だ。

今時は浮動小数点計算がお手軽に使えるし、8 ～ 16 bit の組み込みマイクロプロセッサもメーカーが実装例を示しているので、開平処理を態々書くことも無いか。

これをテストするコードは C 言語で書いてあった。分かりやすく書き直してテストしてみる。

ビルドできて、実行すると期待通りの動作をした。Borland C++ 3.1 (TASM, BCC, MAKE, TLINK) でビルドできるソースコード一式を作る。ビット化け、重複、欠落を起こさずに MO から読み出せていた。

今でも懐かしく思えで、動かそうかなと思うコードってそんなに多くないのかな。

お気に入りの記事を「いいね！」で応援しよう