quyền hạn đếm (ví dụ 2^11) một cách nhanh chóng

Question

thể trùng lặp:
The most efficient way to implement an integer based power function pow(int, int)

Làm thế nào tôi có thể tính toán quyền hạn với thời gian chạy tốt hơn?

Ví dụ: 2^13.

Tôi nhớ nhìn thấy ở đâu đó rằng nó có cái gì để làm với việc tính toán sau:

2^13 = 2^8 * 2^4 * 2^1

Nhưng tôi không thể nhìn thấy cách tính toán mỗi thành phần của phía bên phải của phương trình và sau đó nhân chúng sẽ giúp tôi.

Bất kỳ ý tưởng nào?

Chỉnh sửa: Tôi đã có ý nghĩa với bất kỳ cơ sở nào. Làm thế nào để các thuật toán bạn đã đề cập dưới đây, đặc biệt là "Số mũ bằng cách bình phương", cải thiện thời gian chạy/phức tạp?

Answer 1

Có một thuật toán tổng quát cho điều này, nhưng bằng các ngôn ngữ có dịch chuyển bit, có cách nhanh hơn để tính toán quyền hạn 2. Bạn chỉ cần nhập 1 << exp (giả sử toán tử thay đổi bit của bạn là << vì nó có nhiều nhất ngôn ngữ hỗ trợ hoạt động).

Tôi giả sử bạn đang tìm kiếm thuật toán tổng quát và chỉ chọn một cơ sở không may làm ví dụ. Tôi sẽ cung cấp thuật toán này bằng Python.

def intpow(base, exp): 
    if exp == 0: 
     return 1 
    elif exp == 1: 
     return base 
    elif (exp & 1) != 0: 
     return base * intpow(base * base, exp // 2) 
    else: 
     return intpow(base * base, exp // 2) 

Điều này về cơ bản làm cho số mũ có thể được tính toán trong thời gian kết thúc log2. Đó là một thuật toán phân chia và chinh phục. :-) Là người khác đã nói exponentiation by squaring.

Nếu bạn cắm dụ của bạn vào đây, bạn có thể xem làm thế nào nó hoạt động và có liên quan đến phương trình bạn đưa ra:

intpow(2, 13) 
2 * intpow(4, 6) 
2 * intpow(16, 3) 
2 * 16 * intpow(256, 1) 
2 * 16 * 256 == 2^1 * 2^4 * 2^8 

Answer 2

Quyền hạn của hai là những người dễ dàng. Trong nhị phân 2^13 là một số tiếp theo là 13 số không.

Bạn muốn sử dụng tính năng dịch chuyển bit, được tích hợp sẵn bằng nhiều ngôn ngữ.

Answer 3

Bạn có thể sử dụng exponentiation by squaring. Điều này còn được gọi là "vuông-và-nhân" và hoạt động cho các cơ sở! = 2, quá.

Answer 4

Nếu bạn không giới hạn mình vào quyền hạn của hai, sau đó:

k^2n = (k^n)^2

Answer 5

Sử dụng bitwise chuyển. Ví dụ 1 < < 11 trả về 2^11.

Answer 6

Thuật toán miễn phí nhanh nhất mà tôi biết là bởi Phillip S. Pang, Ph.D và mã nguồn có thể được tìm thấy here. Nó sử dụng phân tách theo bảng, nhờ đó nó có thể làm cho hàm exp() nhanh hơn 2-10 lần, sau đó là exp() của bộ vi xử lý Pentium (R).