DIV CSS 佈局教程網

用 JavaScript 實作冪函數:從迴圈到 Math.pow
編輯:關於JavaScript     

冪運算是基礎練習題,但寫法有好壞之分。以下從最直白的版本開始,逐步改善。

基本版本

function PowerCalculator(base, power) {
  var number = base;

  if (power == 1) return number;
  if (power == 0) return 1;

  for (var i = 2; i <= power; i++) {
    number = number * base;
  }

  return number;
}

邏輯很直白:從 2 開始累加乘到 power 為止,起始值已經是 base 本身,所以迴圈從 2 起算。

這版的邊界問題

仔細看會發現它處理不了負數次方。PowerCalculator(2, -1) 會因為迴圈條件不成立而直接回傳 2,但正确答案應該是 0.5。小數次方同樣無效。

另外它沒處理 power 為非整數或非數字的情況。

改良版

function power(base, exponent) {
  if (exponent === 0) return 1;
  if (exponent < 0) return 1 / power(base, -exponent);

  var result = 1;
  for (var i = 0; i < exponent; i++) {
    result *= base;
  }
  return result;
}

把負指數轉成正數後取倒數,就解決了這個漏洞。

更聰明的做法:快速冪

上面兩版都需要 n 次乘法。但其實可以更快——利用「平方反覆」的技巧,把時間複雜度降到 O(log n)。原理是:a^8 = (a^4)^2 = ((a^2)^2)^2,只需三次平方,而不是七次乘法。

function fastPower(base, exponent) {
  if (exponent < 0) return 1 / fastPower(base, -exponent);

  var result = 1;
  while (exponent > 0) {
    // 若目前的指數是奇數,就把目前的 base 乘進結果
    if (exponent % 2 === 1) {
      result *= base;
    }
    base *= base;          // base 自乘
    exponent = Math.floor(exponent / 2);   // 指數折半
  }
  return result;
}

fastPower(2, 10);   // 1024,只用了 4 次迭代

這個技巧在模冪運算((a^b) mod m)中更是標配,密碼學裡的 RSA 就靠它維持效能。

實務上請直接用內建方法

Math.pow(2, 10);        // 1024
2 ** 10;                // 1024,ES2016 的指數運算子

** 運算子讀起來最直觀,而且支援任意實數指數(2 ** 0.5 就是開根號)。相關的還有 Math.sqrt()(平方根)與 Math.cbrt()(立方根)。

自己實作的價值在於理解演算法——特別是快速冪那個「指數折半」的想法,它在處理大數運算時是必備觀念。但真正上 production 時,請交給引擎的 C++ 實作。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved