Truy cập vô hạn trong Meta Integer Square Root

Question

Ngày tốt,

Một người bạn của tôi đang hỏi về việc chuyển một hàm số nguyên vuông thành một hàm meta. Dưới đây là những chức năng ban đầu:

unsigned isqrt(unsigned value) 
{ 
    unsigned sq = 1, dlt = 3; 
    while(sq<=value) 
    { 
     sq += dlt; 
     dlt += 2; 
    } 
    return (dlt>>1) - 1; 
} 

Tôi đã viết một phiên bản sử dụng meta constexpr, nhưng ông nói rằng ông không thể sử dụng tính năng mới đối với một số lý do:

constexpr std::size_t isqrt_impl 
    (std::size_t sq, std::size_t dlt, std::size_t value){ 
    return sq <= value ? 
     isqrt_impl(sq+dlt, dlt+2, value) : (dlt >> 1) - 1; 
} 

constexpr std::size_t isqrt(std::size_t value){ 
    return isqrt_impl(1, 3, value); 
} 

Vì vậy, tôi nghĩ rằng nó không nên được rằng khó có thể thay đổi đó vào template struct mà gọi đó là tự đệ quy:

template <std::size_t value, std::size_t sq, std::size_t dlt> 
struct isqrt_impl{ 
    static const std::size_t square_root = 
     sq <= value ? 
     isqrt_impl<value, sq+dlt, dlt+2>::square_root : 
     (dlt >> 1) - 1; 
}; 

template <std::size_t value> 
struct isqrt{ 
    static const std::size_t square_root = 
     isqrt_impl<value, 1, 3>::square_root; 
}; 

Thật không may, điều này đang gây ra đệ quy vô hạn (trên GCC 4.6.1) và tôi không thể tìm ra những gì là sai w ith mã. Dưới đây là các lỗi:

C:\test>g++ -Wall test.cpp 
test.cpp:6:119: error: template instantiation depth exceeds maximum of 1024 (use 
-ftemplate-depth= to increase the maximum) instantiating 'struct isqrt_impl<25u 
, 1048576u, 2049u>' 
test.cpp:6:119: recursively instantiated from 'const size_t isqrt_impl<25u, 4u 
, 5u>::square_root' 
test.cpp:6:119: instantiated from 'const size_t isqrt_impl<25u, 1u, 3u>::squar 
e_root' 
test.cpp:11:69: instantiated from 'const size_t isqrt<25u>::square_root' 
test.cpp:15:29: instantiated from here 

test.cpp:6:119: error: incomplete type 'isqrt_impl<25u, 1048576u, 2049u>' used i 
n nested name specifier 

Cảm ơn tất cả,

Answer 1

Đánh giá mẫu không phải là theo mặc định.

static const std::size_t square_root = 
    sq <= value ? 
    isqrt_impl<value, sq+dlt, dlt+2>::square_root : 
    (dlt >> 1) - 1; 

sẽ luôn khởi tạo mẫu, bất kể điều kiện là gì. Bạn cần boost::mpl::eval_if hoặc thứ gì đó tương đương để giải pháp đó hoạt động.

Hoặc bạn có thể có chuyên môn mẫu một phần cơ bản của trường hợp dừng việc đệ quy nếu điều kiện được đáp ứng, như trong câu trả lời K-ballos.

Tôi thực sự thích mã sử dụng một số hình thức đánh giá lười biếng hơn một phần chuyên môn vì tôi cảm thấy dễ hiểu hơn và giữ tiếng ồn đi kèm với mẫu thấp hơn.

Answer 2

Unfortunately, this is causing infinite recursion (on GCC 4.6.1) and I am unable to figure out what is wrong with the code.

tôi không thấy một sự chuyên môn trường hợp cơ sở cho isqrt_impl. Bạn cần phải có một chuyên môn mẫu cho trường hợp cơ sở để phá vỡ đệ quy này. Đây là một nỗ lực đơn giản tại đó:

template <std::size_t value, std::size_t sq, std::size_t dlt, bool less_or_equal = sq <= value > 
struct isqrt_impl; 

template <std::size_t value, std::size_t sq, std::size_t dlt> 
struct isqrt_impl< value, sq, dlt, true >{ 
    static const std::size_t square_root = 
     isqrt_impl<value, sq+dlt, dlt+2>::square_root; 
}; 

template <std::size_t value, std::size_t sq, std::size_t dlt> 
struct isqrt_impl< value, sq, dlt, false >{ 
    static const std::size_t square_root = 
     (dlt >> 1) - 1; 
};