JavaScriptで2の冪を高速に計算する

超高頻度で呼び出される関数の中で2の冪を計算する機会があったので、どのように計算すれば速いか調べてみました。

本記事では、numberの演算について考えます。bigintを使った2の冪については、特に言及する場合以外は扱いません。また、処理系としてはモダンブラウザーを中心に考えています（Node.jsでも適用できるとは思います）。

JavaScriptのnumber型の構造

以前の記事でまとめましたが、JavaScriptのnumber型はIEEE754の64ビット浮動小数点数です。ただし、JavaScriptにはビット操作用の演算子があり、これはオペランドを32ビット整数として処理を進める形となっています（小数や範囲をはみ出す数は適宜丸められます）。

手法の列挙

考えられる手法を、以下に挙げていきます。なお、利用可能な値域がnumber自体の値域のうち一部に限られるものは、その旨明示しています。

Math.pow

JavaScriptの標準関数です。

Math.pow(2, n)

べき乗演算子（**）

標準関数にあるのに演算子版も登場しましたが、こちらはbigintのべき乗にも使えるとのことです。

2 ** n

シフト演算子（<<）

符号付き32ビットの範囲内で表せる数（$2^0$～$2^{30}$）に限られますが、シフト演算で2の冪を算出することも可能です。

1 << n

表引き

必要とする値の範囲が決まっている（たとえば、2の0乗～63乗だけ必要）という場合には、事前にテーブルを作っておいて、それから結果を得る、というような最適化も可能です。

IEEE 754のデータ構造の操作

JavaScriptでも、DataViewを使うことで、あるビット列に対して、適宜の場所を適宜の型で読み書きする、ということが可能となります。2の冪の場合、仮数部は1のまま（ケチ表現なので、ビット列としてはすべて0）で、指数部だけ合わせれば値を作ることができます。ただし、正の正規化数の最小値が$2^{-1022}$なので、これより小さな非正規化数を結果として得たい場合には、それ相応の実装が必要となります。

// ビッグエンディアン版
const memsetBE = (() => {
    // 外部から不適当な書き換えが入るのを避けるため、クロージャに閉じ込める
    // 仮数部で書き換える以外の6バイトは、初期化時の0から永久に変わらない
	const buf = new ArrayBuffer(8);
	const view = new DataView(buf);
	return num => {
		view.setInt16(0, (1023+num) << 4);
		return view.getFloat64(0);
	};
})();

// リトルエンディアン版
const memsetLE = (() => {
	const buf = new ArrayBuffer(8);
	const view = new DataView(buf);
	return num => {
		view.setInt16(6, (1023+num) << 4, true);
		return view.getFloat64(0, true);
	};
})();

その他

「Float32のビットパターンを作る」、「bigintとしてべき乗を実行する」という方法も考えてはみたのですが、コード量や速度面で他の手法に対するメリットが見出し難い状況となったので、割愛いたします。

速度検証

jsBenchで実行するリンクを張りますので、ご自分のブラウザでも確認できます。

• 32ビットの範囲内
• 32ビットの範囲外

実際に走らせて確認した傾向をまとめておきます。

• 32ビットの範囲内では、シフト演算が最速。表引きにすら勝つ。
• 32ビットの範囲外では、表引きが最速だけど、それ以降は環境によって結果が違う
  • Firefoxでは2の冪だけ特別な最適化でもあるのか、Math.powや**演算子がかなり速い
  • ChromeではIEEE 754に沿ったデータ操作のほうが速い
• IEEE 754のデータ操作を行う場合、Windowsではリトルエンディアンのほうが速度が出て、iOS上では大差なし、という状況でした。ビッグエンディアンのマシンでWebを閲覧する可能性も低いので、リトルエンディアンで実装したほうがよさそう。