Kiểm tra xem số có chính trong quá trình biên dịch trong C++

Question

Tôi có một lớp mẫu có số nguyên không dấu như tham số mẫu, nhưng tôi phải đảm bảo rằng số đó là số nguyên tố. Tôi có thể kiểm tra nó trong constructor, ví dụ, nhưng nó sẽ là tốt hơn để làm điều đó trong quá trình biên dịch.

Dưới đây là các mẫu Khẳng định Tôi đang sử dụng:

template <bool statement> 
class Assert; 

template <> 
struct Assert<true> {}; 

tôi chỉ đơn giản có thể tạo ra một đối tượng kiểu này trong bất kỳ đoạn mã đó sẽ được thu thập, sử dụng tình trạng của tôi như tham số, và nó đã giành không biên dịch nếu điều kiện đó là sai. Vấn đề là tôi phải kiểm tra xem một số có phải là số nguyên tố hay không. Để nó là n.

Tôi đã đưa ra ý tưởng bao gồm một tệp riêng biệt "PrimeTest.h" và cố gắng chia n cho mỗi số từ n-1 đến 1 bằng cách bao gồm cùng một tệp từ bên trong tệp đó. Đó là cách tôi sử dụng nó:

#define SUSPECT n 
#include "PrimeTest.h" 

Đây là "PrimeTest.h":

#ifdef SUSPECT 

    #ifndef CURRENT 
     #define CURRENT (SUSPECT-1) 
    #endif // CURRENT 

    #ifndef FINISHED 

    #if CURRENT>100 
     #define IS_PRIME 
     #define FINISHED 
    #else 
     #if SUSPECT%CURRENT==0 
      #define IS_NOT_PRIME 
      #define FINISHED 
     #else 
      #define CURRENT (CURRENT-1) // THAT DOES NOT WORK!!! 
      #include "PrimeTest.h" 
     #endif // SUSPECT % CURRENT != 0 
    #endif 

    #endif // FINISHED 

#endif // SUSPECT 

Nhưng đây là vấn đề: Tôi không thể giảm giá trị hiện tại trong bất kỳ cách nào tôi có thể đưa ra, bao gồm các giá trị tạm thời và chỉ thị #pragma push_macro. Bất kỳ ý tưởng nào về cách thực hiện điều đó?

Answer 1

Bạn không cần preprocessor để tính toán một cái gì đó tại thời gian biên dịch. Thông thường, khi tính toán là cần thiết, bạn sử dụng mẫu Lập trình meta (hoặc constexpr chức năng theo đề nghị của chris trong câu trả lời của ông)

Via mẫu Lập trình meta bạn có thể giải quyết các nhiệm vụ như sau:

Trước tiên, bạn xác định một mẫu mà có thể kiểm tra tại thời gian biên dịch nếu giá trị cho N là divisble bởi D hoặc bất kỳ giá trị thấp hơn D lớn hơn 1.

template <int N, int D> 
struct tmp { 
    static const bool result = (N%D) && tmp<N,D-1>::result; 
}; 

template <int N> 
struct tmp<N,1> { 
    static const bool result = true; 
}; 

giá trị tmp<N,D>::result là true chỉ khi các số 2, 3, ... D không chia N.

Với công cụ trên tay, tạo is_prime thời gian biên dịch kiểm tra là khá dễ dàng:

template <int N> 
struct is_prime { 
    static const bool result = tmp<N,N-1>::result; 
}; 

Bây giờ thời gian biên dịch giá trị is_prime<N>::result là true khi N là số nguyên tố, và false khác. Giá trị có thể được cung cấp cho các mẫu khác, chẳng hạn như Assert của bạn.

Answer 2

Đây là giải pháp nghiệp dư dành cho số dương và được thực hiện tại thời gian biên dịch, nhưng không thể đi quá xa trước khi nó bị hỏng do giới hạn đệ quy. Tôi cho rằng bạn có thể thêm một tham số gốc hình vuông mà bạn tính toán theo cách thủ công để cho phép nó đi đến những gì nó hiện bình phương. Tuy nhiên, nó tận dụng các hàm constexpr của C++ 11 để làm cho cú pháp đẹp hơn một chút để sử dụng mà không cần thêm công việc. Trong mọi trường hợp, nó có thể là một khởi đầu tốt và tôi mong được nhìn thấy câu trả lời hoạt động tốt hơn.

constexpr bool IsPrime(std::size_t N, std::size_t I = 2) { 
    return (N != 2 ? N%I : true) //make 2 prime and check divisibility if not 2 
     && (N >= 2) //0 and 1 are not prime 
     && (I >= N-1 ? true : IsPrime(N, I+1)); //stop when I is too big 
} 

Bạn thậm chí có thể làm cho căn bậc hai đó được thực hiện cho bạn. Trong ví dụ này, tôi sẽ làm cho IsPrime thành một helper để IsPrime chỉ có thể được gọi với N:

//basically does ceil(sqrt(N)) 
constexpr std::size_t Sqrt(std::size_t N, std::size_t I = 2) { 
    return I*I >= N ? I : Sqrt(N, I+1); 
} 

//our old IsPrime function with no default arguments; works with sqrt now 
constexpr bool IsPrimeHelper(std::size_t N, std::size_t sqrt, std::size_t I) { 
    return (N != 2 ? N%I : true) 
     && (N >= 2) 
     && (I >= sqrt ? true : IsPrimeHelper(N, sqrt, I+1)); 
} 

//our new prime function: this is the interface for the user 
constexpr bool IsPrime(std::size_t N) { 
    return IsPrimeHelper(N, Sqrt(N), 2); 
} 

Đối với tôi, phiên bản mới này làm việc với số lượng 521 nơi khác thất bại. Nó thậm chí hoạt động với 9973. Mức cao dự kiến ​​mới sẽ là về hình vuông của cái cũ. Nếu bạn muốn đi xa hơn, bạn thậm chí có thể sửa đổi IsPrimeHelper để tăng thêm 1 khi I là 2 và 2 khi I không phải là 2. Điều đó sẽ dẫn đến mức cao mới gấp đôi lần này.

Answer 3

C++ 11 constexpr phiên bản đó sẽ có thể kiểm tra số lên đến khoảng 1500 trên bất kỳ trình biên dịch mà thực hiện giới hạn độ sâu đệ quy gợi ý:

constexpr bool is_prime_helper(std::size_t target, std::size_t check) { 
    return (check*check > target) || 
    (
     (target%(check+1) != 0) 
     && (target%(check+5) != 0) 
     && is_prime_helper(target, check+6) 
    ); 
} 
constexpr bool is_prime(std::size_t target) { 
    return (target != 0) && (target !=1) && 
    ((target == 2 || target == 3 || target == 5) 
    || ((target%2 != 0) && (target%3 != 0) && (target%5)!=0 && 
    is_prime_helper(target, 6))); 
} 

để cải thiện điều này, chúng tôi làm một số vui vẻ với một nhị phân cây tìm kiếm:

#include <cstddef> 

constexpr bool any_factors(std::size_t target, std::size_t start, std::size_t step) { 
    return 
     !(start*start*36 > target) 
    && 
    (
    ((step==1) 
     && (
     (target%(start*6+1) == 0) 
     || (target%(start*6+5) == 0) 
    ) 
    ) 
    || 
    ((step > 1) 
     && 
     (
     any_factors(target, start, step/2) 
     || any_factors(target, start+step/2, step/2) 
    ) 
    ) 
); 
} 

mà chúng tôi sau đó sử dụng như thế này:

constexpr bool is_prime(std::size_t target) { 
    // handle 2, 3 and 5 explicitly: 
    return 
    (target == 2 || target == 3 || target == 5) 
    || 
    (
     target != 0 
     && target != 1 
     && target%2 != 0 
     && target%3 != 0 
     && target%5 != 0 
     && !any_factors(target, 1, target/6 + 1) // can make that upper bound a bit tighter, but I don't care 
    ); 
} 
#include <iostream> 
int main() { 
    std::cout << "97:" << is_prime(97) << "\n"; 
    std::cout << "91:" << is_prime(91) << "\n"; 
} 

mà sẽ recurse ~ log_2(target/6) lần, có nghĩa là giới hạn đệ quy của constexpr biểu thức của 512 rằng C++ 11 tiêu chuẩn yêu cầu trình biên dịch thực hiện như là một tối thiểu không còn là một vấn đề.

Live example, khi gỡ lỗi được nhúng.

Điều này sẽ làm việc về cơ bản các giới hạn của std::size_t trên hệ thống của bạn. Tôi đã thử nghiệm nó với 111111113.