BFE.devでのAI解答例 - JavaScript コーディング問題
115. BigInt 割り算を実装する

解法:

BigIntの割り算では、通常の割り算と同様に、被除数を除数で何回割り切れるかを数えて、商を求めます。ただし、各桁の計算が通常の数値計算と異なるため、やや複雑な処理が必要です。

以下は、BigIntの割り算を実現するためのアルゴリズムです。

1. 被除数と除数が与えられたら、それらの絶対値を求めます。
2. 被除数と除数がともに正の数またはともに負の数であることを確認します。もし符号が異なる場合は、商の符号を負に変えて処理を行い、最後に符合を反転させた値を返します。
3. 被除数を除数の桁数ずつにまとめて、それぞれに与えられた除数を割ります。
4. 除数で割った商を答えの配列に追加し、余りを次の計算のために保存します。
5. 被除数の先頭から次の数字を取り出し、前の計算で保存していた余りと合わせて、もう一度除数で割ります。このとき、小数点以下の値を算出するために、割り算によって得られた商を小数点以下の桁数ずつ足し合わせます。
6. 計算結果が十進数制であるため、小数点以下の桁数は、商の小数点以下の桁数となります。小数点以下の桁数が必要な数だけ計算が終わったら、商の小数点を挿入します。
7. 商の配列を連結して、答えを返します。

ここで与えられた詳細を、 JavaScriptコードとしてまとめてみます。

function divide(a, b) {
  const result = [];

  // 変数 a, b の絶対値を取得
  a = nremoveLeadingZeroes(a);
  b = nremoveLeadingZeroes(b);
  
  const negative = (a[0] === '-' && b[0] !== '-') ||
                   (a[0] !== '-' && b[0] === '-');
  
  a = a.replace(/^-/, '');
  b = b.replace(/^-/, '');

  // 変数 a, b を数値型に変換
  const div1 = BigInt(nremoveLeadingZeroes(a));
  const div2 = BigInt(nremoveLeadingZeroes(b));
  
  if (div1 < div2) return '0';

  let i = 0;
  let len = a.length - b.length;
  let dividend = '';

  // 一桁ずつ割り算を行う
  while (i <= len) {
    dividend = dividend + a[i];
    if (BigInt(dividend) < div2) { // 割り切れない場合
      result.push('0');
    } else { // 割り切れる場合
      let count = BigInt(0);
      let left = dividend;
      while (BigInt(left) >= div2) {
        count = count + BigInt(1);
        left = (BigInt(left) - div2).toString();
      }
      result.push(count.toString());
      dividend = left;
    }
    i++;
  }

  // 小数点以下桁数
  const precision = 0;
  const dlen = precision + b.length;
  let decimal = '';
  
  if (len < 0) {
    decimal = '0';
  } else if (dividend.length > 0 && result.length < len + 1) {
    dividend = dividend + a[i];
    i++;
    let count = BigInt(0);
    while (BigInt(dividend) >= div2) {
      count = count + BigInt(1);
      dividend = (BigInt(dividend) - div2).toString();
    }
    result.push(count.toString());
  }

  if (!BigInt(dividend)) {
    decimal = decimal + '0'.repeat(precision);
  } else {
    let j = 0;
    while (j < precision && dividend.length > 0) {
      dividend = dividend + '0';
      let count = BigInt(0);
      while (BigInt(dividend) >= div2) {
        count = count + BigInt(1);
        dividend = (BigInt(dividend) - div2).toString();
      }
      decimal = decimal + count.toString();
      j++;
    }
  }

  const quotient = result.join('');
  if (negative && quotient !== '0') return '-' + quotient + '.' + decimal;
  if (negative) return '-' + quotient;
  if (quotient === '0' && decimal === '0') return '0';
  return quotient + '.' + decimal;
}

function nremoveLeadingZeroes(n) {
  let result = n.replace(/^[-+]?0+/, '');
  if (result === '') result = '0';
  return result;
}

このコードでは、BigInt型を利用して割り算を行っています。まず、被除数と除数の絶対値をnremoveLeadingZeroes()関数を使って取得し、そのほかの実装はアルゴリズムに従って行われています。

最初にwhileループで、被除数を除数の桁数ずつにまとめて、それぞれに与えられた除数を割って、商を答えの配列に追加します。余りは次の計算のために保存され、次に小数点以下の桁について計算を行います。余りと次の桁を足し合わせて再度割った商を小数点以下の桁に追加します。小数点以下の桁数が必要な数だけ計算が終わったら、商の小数点を挿入して、答えを返します。

以上がBigIntを使った割り算の実装方法です。