大數相加與相乘

蠻有挑戰性的一題

簡述

這題是來自程式導師計畫 week2 的超級超級挑戰題。

解題的邏輯能用「直式算數」來思考，也就是把大問題拆成小問題的一種思考模式。

大數相加

建議先把大數相加弄懂再去解相乘會比較好理解，因為在做相乘時也需要用到相加的概念：

function add(a, b){
  let result = '';
  // 有沒有進位（flag）
  let hasCarryBit = false;
  // 看誰比較長
  const lengthA = a.length;
  const lengthB = b.length;
  let totalDigits = undefined;

  // 比較短的數字要補 0 
  if (lengthA > lengthB) {
    totalDigits = lengthA;
    for (let i=0; i<lengthA - lengthB; i++) {
      b = '0' + b; 
    }
  } else if (lengthA < lengthB) {
    totalDigits = lengthB;
    for (let i=0; i<lengthB - lengthA; i++) {
      a = '0' + a; 
    }
  } else {
    totalDigits = lengthA;
  }

  // 把每一位數相加
  for (let i=totalDigits-1; i>=0; i--) {
    let value = Number(a[i]) + Number(b[i]);
    // 上一位有進位就加 1 
    if (hasCarryBit) {
      value += 1;
      hasCarryBit = false;
    }
    // >= 10 更新 flag
    if (value >= 10) {
      hasCarryBit = true;
    }
    /*
      取出最後一位數
      19 => 9 + '' => '9'
      5 => 5 + '' => '69'
      13 => 3 + '' => '369'
      ...
    */
    result = value%10 + result;

    // 剩一個數字 but 有進位數要再補 1（因為不跑下一圈）
    if (i===0 && hasCarryBit) {
      result = '1' + result;
    }
  }
  // 答案
  return result;
}

const TESTNUMBER = '124902814902890825902840917490127902791247902479027210970941724092174091274902749012740921759037590347438758957283947234273942304239403274093275902375902374092410937290371093719023729103790123';
const ANSWER = BigInt(add(TESTNUMBER, TESTNUMBER));
const BIGINT = BigInt(TESTNUMBER) + BigInt(TESTNUMBER);
console.log(ANSWER === BIGINT); // true

解釋一下為什麼一定要加這段：

// 剩一個數字 but 有進位數要再補 1（因為不跑下一圈）
if (i===0 && hasCarryBit) {
  result = '1' + result;
}

假設數字是 95 + 40，算到 9 + 4 = 13 的時候，前面的 1 理應要在下圈加上去，但要注意迴圈只會跑到數字長度，所以如果沒有加上這段答案會是 35 不是 135。

所以該怎麼辦？沒有怎麼辦，既然迴圈不會跑下一圈，那你只能在最後一圈的時候判斷有沒有進位數，有的話就要自己補 1 到前面，這就是為什麼這段很重要。

大數相乘

相乘的邏輯大致上跟相加差不多，但有幾點要注意：

1. 每一層要根據位數在尾巴補上 0（就跟做加法的時候一樣）
2. 進位值要用除以 10 的方式來算（範圍變成 0 ~ 9）
3. 要用累加器來紀錄上一次的值（算直式的時候要一層一層加總，所以得紀錄上一層的值）

這邊我都寫註解了，仔細看的話應該可以理解：

function multiply(a, b) {
  let result = '';
  // 紀錄目前的位數
  let currentDigit = 0;
  // 累加器
  let accumulator = '0';
  // 把 b 乘上 a 的每一位求出 sum
  for (let i=b.length-1; i>=0; i--) {
    let sum = '';
    // 進位的值
    let carryBit = 0;
    // 有沒有進位（flag）
    let hasCarryBit = false;
    // a 的部分
    for(let j=a.length-1; j>=0; j--) {
      // b x a 的值
      let value = Number(b[i]) * Number(a[j]);
      // 有進位就把數字加上去
      if (hasCarryBit) {
        value += carryBit;
        carryBit = 0;
        hasCarryBit = false;
      }
      // 大於 10，算出進位值，更新 flag 
      if (value >= 10) {
        hasCarryBit = true;
        carryBit = Math.floor(value/10);
      }
      /*
        5 + '' => '5'
        9 + '5' => '95'
        7 + '95' => '795'
        ...
      */
      sum = value%10 + sum;

      // 剩一個數字 but 有進位數
      if (j===0 && hasCarryBit) {
        sum = carryBit + sum;
      }
    }
    /*
      十位數補一個 0
      百位數補兩個 0
      ...
    */
    for (let i=0; i<currentDigit; i++) {
      sum = sum + '0';
    }
    // 做大數相加（拿上面寫好的來用）
    result = add(sum, accumulator);
    // 加完後更新累加器
    accumulator = result;
    // 更新目前是幾位數
    currentDigit++;
  }
  // 答案
  return result;
}

// 這段是前面寫好的 function 不用看
function add(a, b){
  let result = '';
  // 有沒有進位（flag）
  let hasCarryBit = false;
  // 看誰比較長
  const lengthA = a.length;
  const lengthB = b.length;
  let totalDigits = undefined;

  // 比較短的數字要補 0 
  if (lengthA > lengthB) {
    totalDigits = lengthA;
    for (let i=0; i<lengthA - lengthB; i++) {
      b = '0' + b; 
    }
  } else if (lengthA < lengthB) {
    totalDigits = lengthB;
    for (let i=0; i<lengthB - lengthA; i++) {
      a = '0' + a; 
    }
  } else {
    totalDigits = lengthA;
  }

  // 把每一位數相加
  for (let i=totalDigits-1; i>=0; i--) {
    let value = Number(a[i]) + Number(b[i]);
    // 上一位有進位就加 1 
    if (hasCarryBit) {
      value += 1;
      hasCarryBit = false;
    }
    // >= 10 更新 flag
    if (value >= 10) {
      hasCarryBit = true;
    }
    /*
      取出最後一位數
      19 => 9 + '' => '9'
      5 => 5 + '' => '69'
      13 => 3 + '' => '369'
      ...
    */
    result = value%10 + result;

    // 剩一個數字 but 有進位數要再補 1（因為不跑下一圈）
    if (i===0 && hasCarryBit) {
      result = '1' + result;
    }
  }
  // 答案
  return result;
}

const TESTNUMBER = '124902814902890825902840917490127902791247902479027210970941724092174091274902749012740921759037590347438758957283947234273942304239403274093275902375902374092410937290371093719023729103790123';
const ANSWER = BigInt(multiply(TESTNUMBER, TESTNUMBER));
const BIGINT = BigInt(TESTNUMBER) * BigInt(TESTNUMBER);
console.log(ANSWER === BIGINT); // true