โจทย์
สร้างฟังก์ชันคำนวณ xy แบบ Iterative ที่ทำงานใน O(log y)
ตัวอย่าง
Input: x = 7, y = 3
Output: 343
อัลกอริทึม: Exponentiation by Squaring (Iterative)
หลักการ: แยก y เป็น binary representation แล้วคูณสะสมเฉพาะบิตที่เป็น 1
y = 13 = 11012 x^13 = x^8 * x^4 * x^1 (บิตที่เป็น 1)
โค้ดตัวอย่าง
#include <iostream>
using namespace std;
long long calcPower(long long x, unsigned long long y) {
long long result = 1;
while (y > 0) {
if (y & 1) { // ถ้าบิต LSB เป็น 1
result *= x; // คูณ x เข้า result
}
y >>= 1; // เลื่อน y ขวา 1 บิต (หาร 2)
x *= x; // ยกกำลัง x เป็นสองเท่า (x^2, x^4, x^8...)
}
return result;
}
int main() {
long long x = 7;
unsigned long long y = 3;
cout << x << " raised to " << y << " is " << calcPower(x, y);
return 0;
}
ผลลัพธ์
7 raised to 3 is 343
การวิเคราะห์ขั้นตอน (Trace)
x=7, y=3 (binary 11), result=1 Iteration 1: y=3 (11) y&1=1 → result=1*7=7 y>>=1 → y=1 x*=x → x=49 Iteration 2: y=1 (1) y&1=1 → result=7*49=343 y>>=1 → y=0 x*=x → x=2401 Loop ends. Return 343. ✓
การจัดการ Negative Exponent
double calcPowerDouble(double x, long long y) {
if (y == 0) return 1.0;
bool negative = y < 0;
if (negative) y = -y;
double result = 1.0;
while (y > 0) {
if (y & 1) result *= x;
x *= x;
y >>= 1;
}
return negative ? 1.0 / result : result;
}
Modular Exponentiation (สำหรับ competitive programming)
long long modPow(long long base, long long exp, long long mod) {
long long result = 1;
base %= mod;
while (exp > 0) {
if (exp & 1) result = (result * base) % mod;
base = (base * base) % mod;
exp >>= 1;
}
return result;
}
Complexity
- Time: O(log y) - จำนวนบิตของ y
- Space: O(1) - iterative, ไม่ใช้ stack
สรุป
Iterative Exponentiation by Squaring เป็นวิธีมาตรฐานสำหรับ fast power O(log n) ใช้ bitwise operations (&, >>, <<) ทำให้เร็วและไม่ต้องการ recursion เหมาะสำหรับ production code และ competitive programming
