2006/08/09(水)シフトと加減算命令による乗除算と平方根

よく学校の課題で出されそうな、RISC系CPUなどでかけ算命令を使わずにかけ算やわり算を作れーとかいうやつです。

内部表現は、32bit整数による固定小数点(整数部16bit+小数部16bit)であるとします。

C言語版

#define ulong unsigned int
// 乗算
ulong fmul(ulong x, ulong y) {
	ulong ans=0;
	ulong i,t;

	for(i=0;i<16;i++) {
		if (y & 1)  ans += x;
		y   >>= 1;
		ans >>= 1;
	}

	for(i=0;i<16;i++) {
		if (y & 1)  ans += x;
		y   >>= 1;
		x   <<= 1;
	}

	return ans;
}

// 除算
ulong fdiv(ulong x, ulong y) {
	ulong mask = 0x80000000;
	ulong ans, temp;
	ulong loop = 48;
	ans = temp = 0;

	while(1) {
		if (x & mask) temp++;
		if (temp >= y) {	// can div
			temp -= y;
			ans++;
		}

		if (--loop == 0) break;

		mask >>= 1;
		temp <<= 1;
		ans  <<= 1;
	}
	return ans;
}

x86アセンブラ版

VCならコンパイルできると思います。

#define Shift 16
#define Keisu (1<<Shift)

int __fastcall fsqr(int x)
{
  __asm {
	push ebx
	push esi
	push edi

	mov  esi, ecx
	mov   bl, 20
	mov  eax, 10000h
	align 4
fsqr_loop:
	mov  ecx, esi
	mov  edx, eax
	mov  edi, eax
	call fdiv
	add  eax, edi
	shr  eax, 1

	dec  bl
	jnz  fsqr_loop

	pop  edi
	pop  esi
	pop  ebx
  }
}

int __fastcall fmul(int a, int b)
{
  __asm {
	push ebx
	push esi
	push edi
	push ebp

	mov  edi, ecx
	mov  ebx, edx
	xor	 eax, eax
	xor  esi, esi
	mov  ebp, 16
	shr  edx, 16
	align 4
fmul_loop:
	shr  ebx, 1
	jnc  fmul_L1
	add  eax, ecx
fmul_L1:
	shr  edx, 1
	jnc  fmul_L2
	add  esi, edi
fmul_L2:
	shr	 eax,1
	shl	 edi,1

	dec  ebp
	jnz  fmul_loop

	add  eax, esi
	pop  ebp
	pop  edi
	pop  esi
	pop  ebx
  }
}

int __fastcall fdiv(int a, int b)
{
  __asm {
	push ebx
	push esi

	xor	 eax,eax
	xor  esi,esi
	mov  bl,49
	align 4
fdiv_loop:
	dec  bl
	jz   fdiv_exit

	shl  eax,1
	shl  ecx,1
	rcl  esi,1
	cmp  esi, edx
	jb   fdiv_loop
	inc  eax
	sub  esi, edx
	jmp  short fdiv_loop
fdiv_exit:
	pop esi
	pop ebx
  }
}

//////////////////////////////////////////////////////////////////////
// main
//////////////////////////////////////////////////////////////////////
int main() {
	float a,b;
	int r;
	printf("mul/div 1 : x=",&a);
	scanf("%f",&a);
	printf("mul/div 2 : y=",&a);
	scanf("%f",&b);
	r = fmul((int)(a*Keisu), (int)(b*Keisu));
	printf("x*y = %f (%08x)\n", (float)r/(float)Keisu ,r);
	r = fdiv((int)(a*Keisu), (int)(b*Keisu));
	printf("x/y = %f (%08x)\n", (float)r/(float)Keisu ,r);
	
	printf("\nsquare : x^2=",&a);
	scanf("%f",&a);
	r = fsqr((int)(a*Keisu));
	printf("x = %f (%08x)\n", (float)r/(float)Keisu ,r);
	return 0;
}

誰もがほしがるMIPS版

……データ失踪中(笑 トラックバック参照。