元整数平方根的无限递归

Question

你好，

我的一个朋友正在询问如何将整数平方根函数转换为元函数。这是原始函数：

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

我使用 constexpr 编写了一个元版本，但他说由于某种原因他不能使用新功能：

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);
}

所以我认为将其转换为应该不难递归地调用它自身的模板结构：

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;
};

不幸的是，这会导致无限递归（在 GCC 4.6.1 上），我无法弄清楚代码出了什么问题。错误如下：

 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

谢谢大家，

Answer 1

不幸的是，这会导致无限递归（在 GCC 4.6.1 上），并且我无法弄清楚代码出了什么问题。

我没有看到 isqrt_impl 的基本案例专门化。您需要针对基本情况有一个模板专门化才能打破这种递归。这是一个简单的尝试：

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;
};

Answer 2

默认情况下，模板评估不是惰性的。

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

无论条件如何，都将始终实例化模板。您需要 boost::mpl::eval_if 或等效的东西才能使该解决方案发挥作用。

或者，您可以有一个基本案例部分模板专业化，如果满足条件，则停止递归，就像 K-ballos 答案中一样。

实际上，我更喜欢使用某种形式的惰性求值而不是部分专业化的代码，因为我觉得它更容易理解，并且可以降低模板带来的噪音。