你好,
我的一位 friend 询问如何将整数平方根函数转换为元函数。这是原始函数:
unsigned isqrt(unsigned value)
{
unsigned sq = 1, dlt = 3;
while(sq<=value)
{
sq += dlt;
dlt += 2;
}
return (dlt>>1) - 1;
}
我用 constexpr
写了一个 meta 版本,但是他说因为某些原因他不能使用这个新特性:
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
谢谢大家
最佳答案
Unfortunately, this is causing infinite recursion (on GCC 4.6.1) and I am unable to figure out what is wrong with the code.
我没有看到 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;
};
关于c++ - 元整数平方根中的无限递归,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7795982/