除算を使わずに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進数で実装する場合でも、
>個々の演算は通常の加減乗除の組合せで実装するのが普通です。

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

回答No.5

Tasuke22

取合えず回答１

10のビットを反転して、掛けます。

回答No.4

jacta

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

ループで10を足し続けて、被除数を越える直前の値が商。

お礼

ウィットの利いた回答ありがとうございます。

回答No.3

ts3m-ickw

学生さんの宿題ですかねぇ。除算がダメなら0.1を乗算すればいいのでは、とか詭弁を使ってみたりして。

冗談はさておき、除算にはいくつかのアルゴリズムがありますが、復元法なら簡単だと思います。2で割る部分はシフトで求めます。
詳しいアルゴリズムはこんなところで。

参考URL：

http://www.elc.ees.saitama-u.ac.jp/ITO/Ex4/divide.html

お礼

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

恥ずかしながら理解するのに時間が掛かりました。
実のところ、ループも使わずに出来ないかと思うのですが
お手数ですが他の方法をご存知であればご教示ください。

今回の回答に不満があるというわけではありません。
実際プログラムを組んでみて、例えば数ｋBの数値を除算するのにどれほどの時間が掛かるか試して見る必要があります。
マルチバイトの比較やシフトなんかも組まないといけないので
今実際に試すことができません。

回答には大変感謝しております。
ありがとうございました。

また、他の回答も随時受け付けております。

回答No.2

saru1234

課題じゃないんですか？
だと、そのまま質問するのはルール違反なんですけど。

こういうのはヒントになるでしょうか。（全然役に立たないかも知れませんが。）

論理演算可能な数値らしいので、浮動小数点とかではないですよね。

・乗算せずに10倍する方法。
　・３bitシフトして８倍の値と、１bitシフトして２倍の値を得る。
　・それらを加算すると１０倍の値を得られる。

お礼

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

申し訳ありませんが、乗算に関しては自分でいろいろやって、お書きになった方法に関してもよく理解しているつもりです。
しかしながら、除算になると事が違ってきます。
単純に、2で割ったものと8で割ったものを引いても足しても意味がありません。
2進数では1/10が循環小数になってしまうのです。

いくつか近似値を求める方法は試したのですが、うまく誤差の修正がいきません。
200弱くらいまでしか正しい結果を得られませんでした。
これをマルチバイトに適応するとなるともっと効率のいい方法が必要になると感じています。

情報が少なくて申し訳ありませんでした。
ありがとうございました。

回答No.1

tatsu99

素直に除算を使用して１０で割るのが、自然だとおもうのですが、
どうして、除算を使用してはいけないのでしょうか。（コンパイラが除算をサポートしていないのでしょうか）
その辺の事情を書かれると、良い回答が得られるかもしれません。

補足

そうですね、いろいろ用途があります。

例えば、32ビットを超える多倍長のバイナリを10進数表記にしたり
それを使って、２進化１０進数への変換を行ったり
方法によっては多倍長演算にも使えそうですかね。

多倍長演算に関しては、数値を文字列に変換して行うのが基本だと思うのですが
バイナリで行いたいと常々感じていました。
言語によっては初めからサポートされてるものもあるようですが
実際に使った事は無いので結果がバイナリで出力されるのかどうかわかりません。
もちろんC言語ではサポートされていないので実装したいとも思っています。

多倍長のバイナリ16進数から10進数に変換する方法だけでもいいです。
たぶん、そのほうが手っ取り早いです。

うまく説明できているかどうかわかりませんが、問題解決に協力していただきたいです。
友人に説明したところ、何言ってるかわからないと言われました。すみません。