Hiệu quả của phương pháp nguồn Java của tôi?

Question

Vì vậy, tôi đã đi vào một cuộc phỏng vấn việc làm và họ yêu cầu tôi viết lên một phương pháp điện toán nhanh chóng trên một bảng trắng và đây là những gì tôi đưa lên có

public static double pow(double base, double power) { 
    double result = 1.0; 
    for(double x = 0; x < power; x++) { 
     result = result * base; 
    } 

    return result; 
} 

này đã làm việc và họ đã hài lòng với nó, nhưng sau đó tiến hành hỏi tôi làm thế nào tôi có thể làm cho nó hiệu quả hơn và tôi không có phản ứng. Vì vậy, câu hỏi của tôi là, bạn có thể nhận được hiệu quả hơn này hay chỉ là một câu hỏi để làm cho tôi đổ mồ hôi một chút? Tôi nghĩ rằng có thể có một số giải pháp chuyển bit trực tiếp nhưng tôi không chắc chắn chính xác, tôi nghĩ rằng sẽ chỉ áp dụng cho quyền hạn của 2? Bất kỳ ý tưởng?

* EDIT Xin lỗi tôi quên nói rằng chữ ký phương thức đã được trao cho tôi (số đầu vào gấp đôi) và tôi được thông báo rằng tôi không thể sử dụng bất kỳ thư viện toán học tích hợp nào.

Answer 1

http://en.wikipedia.org/wiki/Exponentiation_by_squaring "Phương thức cơ bản" là O (log n), trái ngược với thuật toán O (n) này. (Guava có triển khai không đệ quy.)

Ngoài ra, thông số công suất của bạn hầu như chắc chắn là int. (Nếu bạn thực sự là muốn để triển khai thuật toán tăng số lượng lên số nguyên không phải số nguyên, bạn sẽ cần nhiều toán hơn.)

Answer 2

Nhân câu trả lời với chính nó và bội số được xác định khác có thể mang lại cho bạn quyền hạn, có thể giúp bạn tiến gần hơn đến giải pháp nhanh hơn. Wiki Louis cung cấp là tốt. Nếu bạn muốn giải thích chung, hãy xem xét:

2^1 * 2^1 = 2^2 
2^2 * 2^2 = 2^4 
2^4 * 2^4 = 2^8 
... 

Điều này rất hữu ích cho hai quyền. Tuy nhiên tôi thấy nó vui vẻ để chơi với không quyền hạn của hai. Vì vậy, nếu tôi muốn 2^13 làm thế nào tôi có thể làm điều này?

2^1 * 2^1 = 2^2 
2^1 * 2^2 = 2^3 
2^3 * 2^3 = 2^6 
2^6 * 2^6 = 2^12 
2^12 * 2^1 = 2^13 

Ví dụ trên là để cho thấy rằng bạn không phải chỉ chơi với hình vuông. Nếu bạn chơi với điều này một số, với quyền hạn khác nhau, bạn sẽ thấy rằng đôi khi bạn có thể làm tốt hơn so với chỉ sử dụng quyền hạn của 2 ... một vấn đề toán học thú vị của nó để chơi với.

Answer 3

Suy nghĩ bên ngoài hộp một chút, thường có sự cân bằng giữa bộ nhớ và tốc độ. Có khái niệm về memoization.

Bạn có thể thêm bộ đệm đôi [] [] tĩnh lưu trữ kết quả cho bất kỳ giá trị cụ thể nào.

Cái gì như:

// look for the value in the cache, if it is there return it. 

for(double x = 0; x < power; x++) { 
    result = result * base; 
    // store result in the cache 
} 

này sẽ làm việc, nhưng sẽ sử dụng rất nhiều bộ nhớ.