冪運算是基礎練習題,但寫法有好壞之分。以下從最直白的版本開始,逐步改善。
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++ 實作。