การหาค่าเลขยกกำลังโดยวิธี Binary Exponentiation

Image by Caroline Kulczycky

การหาค่าเลขยกกำลัง(power) เช่น 5³ = 5*5*5 (ให้เอา 5 คูณกัน 3 ครั้ง) เรียก 5 ว่า ฐาน(base) , เรียก 3 ว่า เลขชี้กำลัง(exponent)

โดยทั่วไปแล้ว การเขียนโปรแกรมหาค่าเลขยกกำลังเราสามารถเขียนแบบตรงไปตรงมาได้ โดย

เขียนแบบ วน loop คูณเพิ่มไปเรื่อย ๆ จนถึงจำนวนครั้งที่ต้องการ

หรือเขียนแบบ recursive ได้ดังนี้

จากอัลกอริทึมของ code ด้านบน ถ้าหากว่าตัวเลขที่ต้องคำนวณมีค่าไม่มากก็สามารถคำนวณออกมาได้ แต่หากเลขชี้กำลังมีค่ามาก ๆ ก็จะทำให้จำนวนรอบการคำนวณมากตามไปด้วย เช่น เลขชี้กำลัง 1000 ก็ต้องทำ 1000 รอบ ซึ่งก็คือ O(n)

ในบทความนี้จะกล่าวถึง เทคนิคการหาค่าเลขยกกำลังให้ได้อย่างรวดเร็ว เป็น O(log(n)) เช่น เลขชี้กำลัง 1000 จะคำนวณประมาณ 10 รอบ
โดยวิธี Binary Exponentiation (หรือรู้จักกันในชื่อ Exponentiation by Squaring)
มีอัลกอริทึมดังนี้
1. ถ้าเลขชี้กำลังเป็น 0 ให้ค่ายกกำลังเท่ากับ 1
2. ถ้าเลขชี้กำลังเป็นเลขคู่ : a²ⁿ ให้เขียนเป็น (aⁿ)²
3. ถ้าเลขชี้กำลังเป็นเลขคี่ : a²ⁿ+¹ ให้เขียนเป็น (aⁿ)² * a

ตัวอย่าง 5¹²

5¹² = (5⁶)²
5⁶ = (5³)²
5³ = (5¹)² * 5
5¹ = (5⁰)² * 5
5⁰ = 1

จะเห็นว่าอัลกอริทึมจะมีการวนซ้ำค่าก่อนหน้า สามารถเขียนโปรแกรมได้ ดังนี้

นอกจากนี้เราสามารถประยุกต์ใช้เลขฐานสองช่วยในการคำนวณได้ ซึ่งจะมีประสิทธิภาพมากกว่า โดยจะสามารถทำได้ 2 แบบคือ

1. right to left

- ไล่จากหลักขวาสุด ของเลขฐานสองของเลขชี้กำลัง หากเป็น 1 ก็ให้คูณค่าประจำหลักนั้น

ตัวอย่าง 5¹²
เลขชี้กำลัง = 12 จะแปลงเป็นฐานสอง = 1100₂

12 = 1100₂ = 1*(2³) + 1*(2²) + 0*(2¹) + 0*(2⁰)

5¹² = 5^(1*(2³) + 1*(2²)) = 5^(8+4) = 5⁸ * 5⁴

สามารถเขียนโปรแกรมคำนวณได้ดังนี้

2. left to right

- แปลงเลขชี้กำลังเป็นฐานสอง
- ไล่ดูจากหลัก ซ้ายสุดมาที่หลักขวาสุด ให้นำ เลขฐานคูณเลขฐาน และ หากพบว่าเป็นเลข 1 ก็ให้คูณเลขฐานเพิ่มอีกครั้ง
เขียนโปรแกรมคำนวณได้ ดังนี้

สามารถปรับปรุงอัลกอริทึมให้กระชับขึ้นอีกหน่อยโดยการเริ่มคำนวณที่หลักที่ 2 ของฐานสองของเลขชี้กำลัง(เพราะหลักแรกเป็น 1 เสมอ) จะทำให้ลดจำนวนการคำนวณได้อีก 1 รอบ เขียนโปรแกรมได้ดังนี้

หมายเหตุ code ข้างต้นนี้เขียนให้รองรับเฉพาะกรณีที่ ฐานและเลขชี้กำลังเป็นจำนวนเต็มและไม่เป็นลบเท่านั้น

นอกจากนี้สำหรับในภาษา Python เองก็จะมีฟังก์ชันที่ถูกเขียนเพื่อหาค่าเลขยกกำลังไว้แล้วต่าง ๆ ดังตัวอย่าง code ด้านล่าง

ความแตกต่างและวิธีไหนจะดีกว่ากันจะยังไม่ได้กล่าวถึงในบทความนี้