Pow(x, n) ใน Python - คำนวณกำลังโดยไม่ใช้ Library

สมมติว่าเรามีอินพุตสองค่า x และ n x เป็นตัวเลขในช่วง -100.0 ถึง 100.0 และ n เป็น signed 32-bit integer เราต้องหา x^n โดยไม่ใช้ library functions

ตัวอย่าง x = 12.1, n = -2 ผลลัพธ์ 0.00683

ขั้นตอนการทำงาน (Binary Exponentiation / Fast Power)

1. power := |n| และ res := 1.0
2. วนลูป while power != 0:
   • ถ้าบิตสุดท้ายของ power เป็น 1 ให้ res := res * x
   • x := x * x
   • power >>= 1 (หาร 2 / ขยับบิตขวา)
3. ถ้า n < 0 ให้คืน 1 / res
4. คืนค่า res

ตัวอย่างโค้ด (Python)

class Solution(object):
    def myPow(self, x, n):
        power = abs(n)
        res = 1.0
        while power:
            if power & 1:
                res *= x
            x *= x
            power >>= 1
        if n < 0:
            return 1 / res
        return res

ob1 = Solution()
print(ob1.myPow(45, -2))
print(ob1.myPow(21, 3))

อินพุต

45 -2 21 3

เอาต์พุต

0.0004938271604938272
9261.0