2019年7月22日追記
Javascriptの適正化により掛け算よりも割り算の方が早くなるケースもあります。
はじめに
私は大学で商学部に所属しています。今日は商品学の授業を受けていて、日本における電卓の歴史を学びました。
そこで出てきたのが足し算、引き算、掛け算はできるのに割り算で効率が悪く、製品の質が落ちるという映像がでてくることになりました。
今回はなぜこのようなことが起きるのか気になったので実際に検証して調べてみようと思い立ちました。
まず1000×0.1と1000÷10は本当に同じなのか。結論から言ってしまうと割り算ではなく掛け算の方が速度が早いです。
優先的に掛け算を使うようにしましょう。
今回はJavascriptでそれぞれの速度の測定を行い、どれくらい違いが出るのか調べてみました。また掛け算と割り算それぞれのアルゴリズムについて調べたのでその記録を残しておきます。
測定用のコード
今回書いたコードは以下のコードです。
以下のように掛け算と割り算で1000×0.1と1000/10をそれぞれ1000回繰り返すコードを書きました。
const test = (func, funcName) => {
const start = performance.now();
func();
const end = performance.now();
console.log(funcName, end - start);
};
const multiplication = () => {
const data = Array(1000);
for (let i = 0; i < 1000; i++) {
data.push(1000 * 0.1);
}
};
const division = () => {
const data = Array(1000);
for (let i = 0; i < 1000; i++) {
data.push(1000 / 10);
}
};
test(multiplication, "multiplication");
test(division, "division");
結果は以下のようになりました。
| 1000×0.1 | 1000÷10 | |
|---|---|---|
| かかった時間(ms) | 0.319999999646825 | 2.484999999978754 |
ブースのアルゴリズム
以下が掛け算(乗算)のアルゴリズムの実装要件です。いろいろと難しいことを書いていますが、よく考えてみると小学生で習う単なる筆算であることがわかります。
以下はWikipediaからの引用です。
ブースのアルゴリズムは、2つの事前に決定された値 A および S のうちの1つを積 P に繰り返し加算（通常の符号なし2進数の加算）し、P を右方向に算術シフトするという形で実装できる。ここで、m を被乗数、r を乗数とし、m のビット数を x、rのビット数を y とする。
- A と S の値を決定し、P を初期状態にする。いずれも長さは (x + y + 1) ビットとする。
- A: 最上位（左端）側のビット列に m の値を格納する。残る (y + 1) ビットは全て0にする。
- S: 最上位側のビット列に (−m) の2の補数表現を格納する。残る (y + 1) ビットは全て0にする。
- P: 最上位側の x ビットを全て0にする。その右のビット列に r の値を格納する。最下位（右端）ビットは0とする。
- P の最下位（右端）2ビットを調べる。
- その中身が 01 の場合、P + A を計算し、オーバーフローは無視する。
- その中身が 10 の場合、P + S を計算し、オーバーフローは無視する。
- その中身が 00 の場合、何もしない。現在の P をそのまま次ステップで使用する。
- その中身が 11 の場合、何もしない。現在の P をそのまま次ステップで使用する。
- 上のステップで得られた値を右に1ビット算術シフトする。その値を P の新たな値とする。 ステップ2と3を y 回反復する。
- Pの最下位（右端）ビットを除去する。これが m と r の積である。
復元法と非復元法
以下が割り算(除算)のアルゴリズムの実装要件です。以下は乗算と同様に割り算の筆算と全く同じです。
以下復元法と非復元法は除算アルゴリズムからの参照です。
復元法
- 被除数から除数を引く。
- 結果が正または0ならば、商にビット1を立てる。
- 引き算の結果が負ならば、商にビット0を立てる。
- このとき、実際には引き算を行ってはならないのだから、除数を加え戻す。
これをループして商と余りを導く方法を復元法という
非復元法
こちらの方が復元法よりも効率の良いアルゴリズム。
- 被除数(P)から除数(Q)を引く。
- 結果であるP-Qの符号を調べる。
- 負ならば除数(Q)を加え戻す。
- 次の繰り返しでは除数を半分にしたQ/2を被除数から引いた結果P-Q/2の符号を調べる。
ここまでは復元法と同じ。
- 被除数(P)から除数(Q)を引いた結果P-Qが負の場合に、除数(Q)の加え戻しを行わない。
- 次の繰り返しでは除数を半分にしたQ/2を被除数から引くのではなく加える。
このように(P-Q)+Q/2=P-Q/2を求めたことになり、加え戻し後にQ/2を引いた結果に等しくなります。
被除数と除数の間の演算を減算と加算で切替えることで、加え戻しのための演算を省略することができます。
まとめ
そこまで大きくない処理であれば割り算でも特に問題ないですし、誤差で割り算の方が早くなることも多少はありました。
ただ平均して掛け算の方が早くなるように感じたので、普段計算を行う処理をするプログラムを書くのであれば割り算ではなく掛け算で書くことをおすすめします。
