โปรแกรมหา Power ของ Complex Number ใน O(log n) ใน C++

ได้รับ Complex Number ในรูป x+yi และจำนวนเต็ม n งานคือคำนวณและพิมพ์ค่าของ Complex Number เมื่อยกกำลัง n

Complex Number คืออะไร?

Complex Number คือจำนวนที่เขียนในรูป a + bi โดย a และ b เป็นจำนวนจริง และ i เป็นคำตอบของสมการ (จำนวนจินตภาพ) กล่าวง่ายๆ Complex Number คือการรวมของจำนวนจริงและจำนวนจินตภาพ

การยกกำลัง Complex Number

ใช้สูตรด้านล่าง:

(a+bi)(c+di) = (ac - bd) + (ad + bc)i

เช่น Complex Number 2+3i ยกกำลัง 5 จะได้

(2+3i)^5 = (2+3i)(2+3i)(2+3i)(2+3i)(2+3i)

ใช้สูตรข้างต้นจะได้คำตอบ

ตัวอย่าง

Input: x[0] = 10, x[1] = 11 (x[0] = Real part, x[1] = Imaginary part)
n = 4
Output: -47959 + i(9240)

Input: x[0] = 2, x[1] = 3
n = 5
Output: 122 + i(597)

วิธีแก้ปัญหา:

แก้ได้ด้วย Iterative Method แต Complexity จะเป็น O(n) แต่เราต้องการ O(log n) ดังนั้น:

• รับ Input เป็น Array
• ในฟังก์ชัน Power คำนวณ x^n:
  • ถ้า n == 1 คืน x
  • เรียก Power(x, n/2) แบบ Recursive เก็บผลใน sq
  • ถ้า n หาร 2 ลงตัว คืน cmul(sq, sq)
  • ถ้า n หาร 2 ไม่ลงตัว คืน cmul(x, cmul(sq, sq))
• ในฟังก์ชัน cmul():
  • ถ้า x1 = a+bi และ x2 = c+di แล้ว x1*x2 = (ac - bd) + (bc + da)i
• คืนและพิมพ์ผลลัพธ์

อัลกอริทึม

Start
Step 1: ฟังก์ชันคำนวณผลคูณ Complex Numbers
  long long* complex(long long* part1, long long* part2)
  Declare long long* ans = new long long[2]
  Set ans[0] = (part1[0] * part2[0]) - (part1[1] * part2[1])
  Set ans[1] = (part1[1] * part2[0]) + part1[0] * part2[1]
  Return ans

Step 2: ฟังก์ชันคืน Complex Number ยกกำลัง n
  long long* power(long long* x, long long n)
  Declare long long* temp = new long long[2]
  IF n == 0: Set temp[0]=0, temp[1]=0, Return temp
  IF n == 1: Return x
  Declare long long* part = power(x, n / 2)
  IF n % 2 == 0: Return complex(part, part)
  Return complex(x, complex(part, part))

Step 3: ใน main()
  Declare int n
  Declare long long* x = new long long[2]
  Set x[0] = 10, x[1] = -11
  Set n = 4
  Call long long* a = power(x, n)
Stop

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

#include <bits/stdc++.h>
using namespace std;

long long* complex(long long* part1, long long* part2) {
    long long* ans = new long long[2];
    ans[0] = (part1[0] * part2[0]) - (part1[1] * part2[1]);
    ans[1] = (part1[1] * part2[0]) + part1[0] * part2[1];
    return ans;
}

long long* power(long long* x, long long n) {
    long long* temp = new long long[2];
    if (n == 0) {
        temp[0] = 0;
        temp[1] = 0;
        return temp;
    }
    if (n == 1)
        return x;
    long long* part = power(x, n / 2);
    if (n % 2 == 0)
        return complex(part, part);
    return complex(x, complex(part, part));
}

int main() {
    int n;
    long long* x = new long long[2];
    x[0] = 10;
    x[1] = -11;
    n = 4;
    long long* a = power(x, n);
    cout << a[0] << " + i ( " << a[1] << " )" << endl;
    return 0;
}

ผลลัพธ์

power of complex number in O(Log n) : -47959 + i ( 9240 )