Luỹ thừa với số nguyên dài

[nam402MTH0389]

Cho mình hỏi có cách nào tính luỹ thừa của hai số nguyên dài nhanh ko?
Mình sử dụng cách nhân liên tục thấy không được hiệu quả lắm

[kidkid]

không rõ câu hỏi lắm.
Ý cậu là 2 số nguyên kiểu int hay kiểu list.

Vấn đề này thì cũng chỉ giải quyết bằng cách nhân liên tục thôi.

[nam402MTH0389]

2 số nguyên dài này được ghi trên mảng. Cách nhân liên tục không hiệu quả trong trường hợp số mũ quá lớn

[bete]

Thân gửi bạn Nam,

x^234

Thay vì làm 234 phép nhân; tui nghĩ bạn thử làm như vầy coi sao:

x^234 = (x^23)^10 * (x^4) = [(x^2)^10 * (x^3)]^10 * (x^4)

=> mình sẽ làm các phép tính:
A = x^2
B = A^10 (= x^20)
C = x^3
D = B*C (= x^23)
E = D^10 (= x^230)
F = x^4
G = E*F (= x^234)

(hiểu biết nông cạn; có gì sai mong được góp ý; xin cám ơn)

-thân

[kidkid]

Bete cậu có thể giải thích rõ hơn chút nữa được ko ?
Tớ không thấy rõ nó tối ưu hơn nhân liên tiếp như thế nào ?

[bete]

Thân gửi bạn kidkid,

Khi tính x^n; nếu n đủ lớn (ví dụ như n=234):
- nếu xài nhân liên tiếp thì tốn 234=n phép nhân
- còn nếu làm như trên thì tốn khá ít hơn n phép tính

Để ý thêm, mình có thể tính, ví dụ là x^6, như sau:

A = x^2
B = A^2 (= x^4)
C = A*B (= x^6)
=> tốn chỉ có 3 phép nhân thay vì 6 phép nhân (cách làm là tương tự như trên; nhưng phân tích số mũ ra cơ số 2 thay vì để nguyên ở cơ số 10)

(hiểu biết nông cạn; có gì sai sót mong được góp ý; xin cám ơn)

-thân