Edited at 2019-07-22

1000×0.1と1000÷10は同じ？割り算と割り算のアルゴリズム

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 の積である。