除算を使わずに10で割りたい。

質問

加算、減算、シフト、論理演算、ループ、等を使って
除算を使わずに10で割る方法は無いものでしょうか？
また、近似値を求めてから誤差を修正する方法でも構いません。

ただし、ループで10を引き続けてカウントする方法は除外させてください。

言語はCでお願いします。

回答No.16

mtaka2 · ベストアンサー

ANo.15 は「引き戻し法」ですね。いわゆる普通の「割り算の筆算」をそのまま2進数ベースで実装したものです。
(10進の割り算の場合は、各桁で「1倍～9倍のどこまで引けるか」を計算しますが、2進数なので、「引ける(その桁は1)か引けない(その桁は0)か」の2択の判定になります。

それをもうちょっと進めた(計算量を減らした)方法に「引き放し法」というのもあります。「引けるかどうか」チェックしてから「引く」のは二度手間なので、「引いてしまってから、結果によって次の処理を変える(負になったら、次のステップでは足すようにする)」というものです。

でも、この手の処理は「CPUの内部でハードウェアで実装されている」機能ですから、それをソフトウェアで実装するのは遅いだけでメリットはありません。
多倍長演算が例に挙げられてますけど、多倍長の2進数で実装する場合でも、
個々の演算は通常の加減乗除の組合せで実装するのが普通です。
例えば、32bitCPUで256bitの数値演算をしたいのであれば、
「4294967296進数で8桁の数値」を扱うようにすればいいんです。

簡単な例ですが、以下、64bitの数値を16bit×4桁と考えて10で割るコードです。除数の方も多倍長になるとやることは格段に複雑になりますが、演算の基本方針は同じです。

#include <stdio.h>
int main(int argc, char *argv[])
{
union {
unsigned long long ulonglong;
unsigned short ushort[4];
} x, y;
unsigned int div, mod;

x.ulonglong = 9876543210LL;
printf("%lld = %d * (1<<48) + %d * (1<<32) + %d * (1<<16) + %d\n", x.ulonglong, x.ushort[3], x.ushort[2], x.ushort[1], x.ushort[0]);
/* x86 CPUは Little Endian なので、ushort[3]が上位でushort[0]が下位 */

div = x.ushort[3] / 10;
mod = x.ushort[3] % 10;
y.ushort[3] = div;

div = (mod * 65536 + x.ushort[2]) / 10;
mod = (mod * 65536 + x.ushort[2]) % 10;
y.ushort[2] = div;

div = (mod * 65536 + x.ushort[1]) / 10;
mod = (mod * 65536 + x.ushort[1]) % 10;
y.ushort[1] = div;

div = (mod * 65536 + x.ushort[0]) / 10;
mod = (mod * 65536 + x.ushort[0]) % 10;
y.ushort[0] = div;

printf("%lld / 10 = %lld mod %d\n", x.ulonglong, y.ulonglong, mod);

}

お礼

回答ありがとうございます。

「引き戻し法」「引き放し法」覚えておきます。

>多倍長演算が例に挙げられてますけど、多倍長の2進数で実装する場合でも、
>個々の演算は通常の加減乗除の組合せで実装するのが普通です。

なるほど、私は初めから多倍長演算になると普通の乗除算は使えないと勝手に考えてしまい、このような質問をすることになっていました。
このような考え方があったのですね。
教えていただき、ありがとうございました。