Hỏi về thuật toán Tính lũy thừa của 1 số cực lớn

[kznguen (nguyen)]

Cho em hỏi về thuật toán tính số cực lớn, em đang làm về máy tính, và yêu cầu xử lý số cực lớn. Phần cộng trừ nhân e đã làm xong còn phần lũy thừa, hiện em có viết theo cách bình thường là
nhưng có vẻ k ổn lắm với phép tính 9999^9999,

private string TestPow(string str1, int b)
{
    if (b == 0)
    {
        return 1.ToString();
    }
    else
    {
        if (b % 2 == 0)
        {
            return Multi(TestPow(str1, b / 2), TestPow(str1, b / 2));
            //return Multi(str1, TestPow(str1, b - 1));
        }
        else
        {
            return Multi(Multi(TestPow(str1, b / 2), TestPow(str1, b / 2)), str1);
            //result = TestPow(str1, b/2);
            //return Multi(result, result);
        }
    }
}

vì đây là xử lý số lớn thế cho nên em có viết ra 1 hàm nhân như này, em có đợi nó chạy nhưng mà có vẻ lâu quá nên thôi, hình như chưa tối ưu lắm

public string Multi(string str1, string str2)
{
    string temp1 = str1;
    string temp2 = str2;
    string result="";
    string[] s1 = new string[100000000];
    string s10 = "";
    for (int i = temp1.Length - 1; i >= 0; i--)
    {
        s1[i] = MiniMultyply(temp1[i], temp2);
        s1[i] += s10;
        result = miniPlus(result, s1[i]);
        s10 = s10 + 0.ToString();
    }
    NormalResul(ref result);
    return result.ToString();
}

[Hoang2 (Hoang)]

Bạn thử dùng mảng xem. Như bài hướng dẫn này https://www.google.co.jp/amp/s/4fire.wordpress.com/2009/07/16/tính-giai-thừa-só-lớn-big-factorial/amp/
Mình mới dùng để tính giai thừa của 70000. Chắc cũng có thể tính được lũy thừa đấy

[rogp10]

Trước hết phải dùng cơ số lớn, và phải tách rời dạng hiển thị (chỉ làm vài lần) với dạng biểu diễn (chạy suốt luôn). Cứ phải vác dạng hiển thị đi muôn nơi thì nó nặng nề quá.

Rồi mới phân tích số mũ ra binary sau đó dùng Toom-3 là xong. BigInteger chỉ có 1 thuật toán nên chán lắm.

---

Cơ số lớn là để các phép tính O(1) chạy hết công suất. Toom-2 từ 4 còn 3, Toom-3 từ 8 còn 5 và overhead tăng tương ứng.