JavaScript で割り算の商と余りを求める

JavaScript で整数同士の割り算をして商と余りを求める方法について解説します。

まず2つの整数 m, n を受け取って商と余りの組を返す関数 div を定義しましょう。

const div = (f=>(u=>u(u))(x=>f(y=>x(x)(y))))(g=>m=>n=>m>=n?(b=>b?1+g(m-n)(n)(1):g(m-n)(n)(0)):(b=>b?0:m));

はい、書けました。

試しに 14 ÷ 3 = 4 ... 2 を計算してみます。

私からは以上です。

解説 (蛇足)

上記のコードをどのように錬成したか分かりたい人向けです。

まず再帰を使って普通に div を書きます。

/**
 * @param {number} m 割られる数
 * @param {number} n 割る数
 * @returns {[number, number]} 商と余りの組
 */
const div = (m, n) => {
  if (m >= n) {
    const [q, r] = div(m - n, n);
    return [1 + q, r];
  } else {
    return [0, m];
  }
}

div を実行すると div(14, 3) → [4, 2] のように2要素のタプル (配列) が返ってきます。
0番目の要素が商で、1番目の要素が余りです。

分割代入は Internet Explorer で動かないので愚直なブラケット記法に書き換えます。

const div = (m, n) => {
  if (m >= n) {
    return [1 + div(m - n, n)[0], div(m - n, n)[1]];
  } else {
    return [0, m];
  }
}

ブレース {} が美しくないので if 文を三項演算子で書き換えます。

const div = (m, n) => m >= n
  ? [1 + div(m - n, n)[0], div(m - n, n)[1]]
  : [0, m];

ブラケット [] も美しくないのでタプルを三項演算子で書き換えます。

const div = (m, n) => m >= n
  ? (b => b ? 1 + div(m - n, n)(1) : div(m - n, n)(0))
  : (b => b ? 0 : m);

カリー化 🍛 します。

const div = m => n => m >= n
  ? (b => b ? 1 + div(m - n)(n)(1) : div(m - n)(n)(0))
  : (b => b ? 0 : m);

div 関数に引数 g を追加して div_ 関数に書き換えます。

const div_ = g => m => n => m >= n
  ? (b => b ? 1 + g(m - n)(n)(1) : g(m - n)(n)(0))
  : (b => b ? 0 : m);

おもむろに Z コンビネータを持ち出します。

const z = f => (u => u(u))(x => f(y => x(x)(y)));

z と div_ をがっちゃんこします。

const div = z(div_);

これだけでは味気ないので z と div_ をそれぞれ展開します。

const div = (f => (u => u(u))(x => f(y => x(x)(y))))(
  g => m => n => m >= n
    ? (b => b ? 1 + g(m - n)(n)(1) : g(m - n)(n)(0))
    : (b => b ? 0 : m)
);

余分なスペースや改行を取り除いてあげれば完成！

const div = (f=>(u=>u(u))(x=>f(y=>x(x)(y))))(g=>m=>n=>m>=n?(b=>b?1+g(m-n)(n)(1):g(m-n)(n)(0)):(b=>b?0:m);

いい感じですね (？)

解説の解説 (蛇足の蛇足)

「タプルを三項演算子で書き換える」とは？

タプルとは複数の値の組を保持しておけるデータ構造です。キーに名前が付いていない構造体 (キーを連番で管理している構造体) と見ることもできます。
(そもそも JavaScript にはタプルが無いので ['foo', 'bar'] のように配列を使っていましたが)

さて、ここで三項演算子を思い出して以下のような関数を書いてみましょう。

const f = b => b : 'foo', 'bar';

この関数 f は以下のような振る舞いをします。

f(true)   // → 'foo'
f(false)  // → 'bar'

引数に応じて 'foo' または 'bar' を返しています。
引数によって 'foo', 'bar' のどちらも返せると云うことは、関数 f は内部的に ('foo', 'bar') の組を保持しているということです。これって2要素のタプルと実質的に同じことですよね？

というわけで一般化すると、2要素 (x, y) を保持するタプルは三項演算子を使って b => b ? x : y と書けます。
要素を取り出すときは引数に true, false を渡してもいいのですが、1, 0 を渡しても同じように動作します。

const f = b => b : 'foo', 'bar';
f(1)  // → 'foo'
f(0)  // → 'bar'

無駄と文化

実用的ブログ

JavaScript で割り算の商と余りを求める

解説 (蛇足)

解説の解説 (蛇足の蛇足)