Ricorsione infinita a Meta intero radice quadrata

Question

Buon giorno,

Un mio amico sta chiedendo di trasformare una funzione di radice quadrata intero in una meta-funzioni. Ecco la funzione originale:

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

ho scritto una versione meta utilizzando constexpr, ma ha detto che non è possibile utilizzare la nuova funzionalità per qualche motivo:

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

così ho pensato che non dovrebbe essere difficile per trasformarla in modello struct che chiama è di per sé in modo ricorsivo:

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

Purtroppo, questo sta causando una ricorsione infinita (il GCC 4.6.1) e sono in grado di capire ciò che è sbagliato w con il codice. Ecco l'errore:

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 

Grazie tutti,

Answer 1

La valutazione del modello non è pigro per impostazione predefinita.

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

crea sempre un'istanza del modello, indipendentemente dalle condizioni. Hai bisogno di boost::mpl::eval_if o qualcosa di equivalente per far funzionare quella soluzione.

In alternativa è possibile avere una specializzazione del modello parziale del caso base che arresta la ricorsione se la condizione è soddisfatta, come nella risposta K-ballos.

Preferisco il codice che utilizza una qualche forma di valutazione pigra rispetto alla specializzazione parziale perché ritengo che sia più facile da comprendere e mantiene il rumore associato ai modelli inferiori.

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.

non vedo un caso base specializzazione per isqrt_impl. È necessario disporre di una specializzazione di modello per il caso base per interrompere questa ricorsione. Ecco un semplice tentativo:

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