7月初的時候挑戰了一下LeetCode的 第29題 （中等難度，似乎沒什麼值得誇耀的），題目要求在不使用除、乘，以及模運算的情況下，實現整數相除的函數。

既然被除數和除數都是整數，那麼用減法就可以實現除除法了（多麼naive的想法）。一個trivial的、用JavaScript編寫的函數可以是下面這樣的（爲了簡單起見，只考慮兩個參數皆爲正整數的情況）

function divide(n, m) {
  let acc = 0;
  while (n >= m) {
    n -= m;
    acc += 1;
  }
  return acc;
}

如此樸素的 divide 函數提交給LeetCode是不會被接受的的——它會在像2147483648除以2這樣的測試用例上超時。可以在本地運行一下感受下究竟有多慢 

➜  nodejs time node divide.js
2147483648/2=1073741824
node divide.js  1.14s user 0.01s system 99% cpu 1.161 total

那麼有沒有更快的計算兩個整數的商的算法呢？答案當然是肯定的。

嘗試優化

一眼就可以看出，運行次數最多的是其中的 while 循環。以2147483648除以2爲例， while 循環中的語句要被執行1073741824次。爲了提升運行速度，必須減少循環的次數。

既然每次從 n 中減去 m 需要執行 n/m 次，那麼如果改爲每次從中減去 2m ，不就只需要執行 (n/m)/2 次了麼？循環的次數一下子就減少了一半，想想都覺得興奮啊。每次減 2m ，並且自增2的算法的代碼及其運行效果如下 

➜  nodejs cat divide2.js
function divide(n, m) {
  let acc = 0;
  let m2 = m << 1; // 因爲題目要求不能用乘法，所以用左移來代替乘以2。
  while (n >= m2) {
    n -= m2;
    acc += 2;
  }
  while (n >= m) {
    n -= m;
    acc += 1;
  }
  return acc;
}

console.log(`2147483648/2=${divide(2147483648, 2)}`);
➜  nodejs time node divide2.js
2147483648/2=1073741824
node divide2.js  2.65s user 0.01s system 99% cpu 2.674 total

儘管耗時不降反升，令場面一度十分尷尬，但根據理論分析可知，第一個循環的運行次數僅爲原來的一半，而第二個循環的運行次數最多爲1次，可以知道這個優化的方向是沒問題的。

如果計算 m2 的時候左移的次數爲2，那麼 acc 的自增步長需要相應地調整爲4，第一個循環的次數將大幅下降至268435456，第二個循環的次數不會超過4；如果左移次數爲3，那麼 acc 的步長增至8，第一個循環的次數降至134217728，第二個循環的次數不會超過8。

顯然，左移不能無限地進行下去，因爲 m2 的值早晚會超過 n 。很容易算出左移次數的一個上限爲

對數符號意味着即便對於很大的 n 和很小的 m ，上述公式的結果也不會很大，因此可以顯著地提升整數除法的計算效率。

在開始寫代碼前，讓我先來簡單地證明一下這個方法算出來的商與直接計算 n/m 是相等的。

一個簡單的證明

記被減數爲 n ，減數爲 m 。顯然，存在一個正整數 N ，使得

令

，再令

，那麼 n 除以 m 等價於

證明完畢。

從上面的公式還可以知道，新算法將原本規模爲 n 的問題轉換爲了一個規模爲 r 的相同問題，這意味着可以用遞歸的方式來優雅地編寫最終的代碼。

完整的代碼

最終的 divide 函數的代碼如下 

function divide(n, m) {
  if (n < m) {
    return 0;
  }

  let n2 = n;
  let N = 0;
  // 用右移代替左移，避免溢出。
  while ((n2 >> 1) > m) {
    N += 1;
    n2 = n2 >> 1;
  }

  // `power`表示公式中2的N次冪
  // `product`代表`power`與被除數`m`的乘積
  let power = 1;
  let product = m;
  for (let i = 0; i < N; i++) {
    power = power << 1;
    product = product << 1;
  }
  return power + divide(n - product, m);
}

這個可比最開始的 divide 要快得多了，有圖有真相 

➜  nodejs time node divide3.js
2147483648/2=1073741824
node divide3.js  0.03s user 0.01s system 95% cpu 0.044 total

後記

如果以 T(n, m) 表示被除數爲 n ，除數爲 m 時的算法時間複雜度，那麼它的遞推公式可以寫成下列的形式

但這玩意兒看起來並不能用主定理直接求出解析式，所以很遺憾，我也不知道這個算法的時間複雜度究竟如何——儘管我猜測就是 N 的計算公式。

如果有哪位好心的讀者朋友知道的話，還望不吝賜教。

相關文章