Бесконечная рекурсия в квадратном корне Meta Integer - PullRequest
Новая
       20

Бесконечная рекурсия в квадратном корне Meta Integer

6 голосов
/ 17 октября 2011

Добрый день,

Мой друг спрашивает о преобразовании целочисленной функции квадратного корня в мета-функцию.Вот оригинальная функция: 

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

Спасибо всем,

Ответы [ 2 ]

7 голосов
/ 17 октября 2011

К сожалению, это вызывает бесконечную рекурсию (в 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;
};
4 голосов
/ 17 октября 2011

Оценка шаблонов не ленивая по умолчанию. 

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.

Я бы на самом деле предпочел код, который использует некоторую форму ленивых вычислений, а не частичной специализации, потому что я чувствую, что его легче понять и сохраняет шум, который приходит с шаблонами ниже.

...