Tính toán giai thừa của một số nguyên nhỏ tại thời gian biên dịch

Question

Tôi chỉ thực hiện (một lần nữa) một mẫu đệ quy để tính toán giai thừa của một số nguyên tại thời gian biên dịch (người đã nghĩ rằng một ngày nào đó tôi thực sự cần nó!). Tuy nhiên, thay vì lăn của riêng tôi, tôi đã đi đến Boost tìm kiếm câu trả lời. Tuy nhiên, chức năng giai thừa trong toán học đặc biệt đặc biệt cấm sử dụng nó với các loại số nguyên, vì vậy tôi chỉ viết của riêng tôi.

Tuy nhiên, có chức năng nào khác trong Boost mà tôi nên sử dụng không? Tôi có nên truyền số nguyên của mình sang double và sử dụng chức năng boost::factorial không? Tính toán có được thực hiện tại thời gian biên dịch không?

Answer 1

Bạn không cần Boost, đây chỉ là 1-liner nếu bạn có C++ 11:

constexpr uint64_t factorial(uint64_t n) { 
    return n == 0 ? 1 : n * factorial(n-1); 
} 

Và nó sẽ làm việc ngay cả khi arg của bạn không biên dịch hằng số thời gian quá. uint64_t sẽ hoạt động với n < 21.

Nếu bạn đang thực hiện nó trong thời gian biên dịch và nhân với giá trị dấu phẩy động - sẽ không có phí chuyển đổi (chuyển đổi cũng sẽ ở thời gian biên dịch).

Answer 2

Vì có một số giới hạn giai thừa có thể vừa với một số nguyên, bạn chỉ cần tính toán trước 20 giá trị đầu tiên bằng tay và lưu trữ chúng trong một mảng toàn cục hoặc tĩnh. Sau đó sử dụng một chức năng toàn cầu hoặc tĩnh để tra cứu giai thừa trong mảng:

#include <iostream> 

const int factorials[] = 
{ 
    1, 
    1, 
    2, 
    6, 
    24, 
    // etc... 
}; 

inline const int factorial(int n) {return factorials[n];} 

int main() 
{ 
    static const int fourFactorial = factorial(4); 
    std::cout << "4! = " << fourFactorial << "\n"; 
} 

Nếu bạn sử dụng một chữ như một cuộc tranh cãi để factorial, sau đó trình biên dịch chỉ đơn giản là nên thay lời gọi hàm với kết quả (khi tối ưu hóa được kích hoạt). Tôi đã thử ví dụ trên trong XCode 4.4 (trên máy Mac) và tôi nhìn thấy trong lắp ráp mà nó khởi fourFactorial với hằng số 24:

.loc 1 20 38 ## /Users/emile/Dev/sandbox/sandbox/main.cpp:20:38 
movl $24, __ZZ4mainE13fourFactorial(%rip) 

Phương pháp này có thể dẫn đến biên soạn nhanh hơn bằng cách sử dụng đệ quy thời gian biên dịch thủ thuật.