Metafunkcja pierwiastka kwadratowego?

Question

Czy to możliwe, aby obliczyć pierwiastek kwadratowy z liczby całkowitej z metafunkcji z następującym podpisem:

template<unsigned int N> inline double sqrt(); 

(lub być może za pomocą słowa kluczowego constexpr, nie wiem co jest najlepsze). Tym razem sqrt<2>() zostanie zastąpione przez 1.414... podczas kompilacji.

Jakie byłoby najlepsze wdrożenie dla takiej funkcji?

Answer 1

To może nie być czego szukasz, ale chciałem się upewnić, że zorientowałeś się, że zazwyczaj przy optymalizacji kompilator i tak obliczy wynik w czasie kompilacji. Na przykład, jeśli masz ten kod:

void g() 
{ 
    f(sqrt(42)); 
} 

Z g ++ 4.6.3 z optymalizacji -O2, otrzymany kod montaż jest:

9 0000 83EC1C    subl $28, %esp 
    11 0003 DD050000    fldl .LC0 
    12 0009 DD1C24    fstpl (%esp) 
    13 000c E8FCFFFF    call _Z1fd 
    14 0011 83C41C    addl $28, %esp 
    16 0014 C3     ret 
    73     .LC0: 
    74 0000 6412264A    .long 1244009060 
    75 0004 47EC1940    .long 1075440711 

Funkcja sqrt nigdy nie jest faktycznie nazywa, a wartość jest właśnie przechowywany jako część programu.

Dlatego, aby utworzyć funkcję, która technicznie spełnia wymagań, po prostu musiałyby:

template<unsigned int N> inline double meta_sqrt() { return sqrt(N); } 

Answer 2

Problem, który widzę, polega na tym, że metaP skutecznie nadużywa wyliczenia zmiennych. Problem polega na tym, że wyliczenia są traktowane wewnętrznie jako liczby całkowite, co wyklucza próbę uzyskania z nich wartości zmiennoprzecinkowej. Możliwe jest jednak utworzenie własnego formatu zmiennoprzecinkowego, który tworzy dwa wyniki, część całkowitą i wykładnik. Nadal będziesz musiał przetworzyć to w float, jako Out = Sqrt<42>::mantissa * pow(10,Sqrt<42>::exponent);. Właściwie to ustalenie wartości jest pozostawione ćwiczeniu dla czytelnika, ale prawdopodobnie będziesz musiał skalować wejście do góry (przez równomierną moc 10), obliczając root i przechowując opcję -power/2, której użyłeś wcześniej.

Aby obliczyć sqrt < 42>, należy najpierw ustawić wyliczenie wykładnika na odpowiednią moc, na przykład "-4" (im niższa, tym więcej miejsca po przecinku, ale uważaj na przepełnienie). Następnie pomnóż wejście przez '10^(- 2 * wykładnik) '. W tym przypadku otrzymasz 42 * 10^8 = 4200000000. Następnie pobierasz katalog główny tej wartości, uzyskując "64807" jako wartość końcową. W czasie wykonywania obliczysz "wartość * wykładnika 10" = "64807 * 10^-4" = 64807 * 0,0001 = 6,4807m i zachowasz wartość float.

Dodatkowa praca przeliczeniowa jest słabsza od celu, ale możesz ją nieco zmniejszyć, przechowując wykładnik jako 10^k (tj. 10^4), a następnie wykonując out=sqrt<x>::mantissa/sqrt<x>::exponent.

edit Właśnie zauważyłem, że przy metodzie mantysa/wykładnik, wybór wykładnikiem jest dowolna tak długo, jak to jest większy niż część całkowitej ostatecznej korzenia. Może nawet być stałą, która ułatwia projektowanie twoich funkcji meta. W przypadku 42 na przykład można wybrać "wykładnik", aby zawsze był 6000. Następnie pomnożyć dane wejściowe przez 6000^2, wziąć całkowity katalog główny produktu, a następnie w czasie wykonywania podzielić wynik przez 6000, aby uzyskać katalog główny . Zamiast traktować wynik jako * 10^b, używa relacji sqr (x * b^2) = sqr (x) * b. Matematyka wyewidencjonuje:

• 42 * 6000 * 6000 = 1512000000
• sqr (1512000000) = 38884
• 38884/6000 = 6,4806 (do kwadratu jest 41,999)

Answer 3

Eigen zawiera ten meta_sqrt który wykorzystuje wyszukiwanie binarne:

template<int Y, 
     int InfX = 0, 
     int SupX = ((Y==1) ? 1 : Y/2), 
     bool Done = ((SupX-InfX)<=1 ? true : ((SupX*SupX <= Y) && ((SupX+1)*(SupX+1) > Y))) > 
           // use ?: instead of || just to shut up a stupid gcc 4.3 warning 
class meta_sqrt 
{ 
    enum { 
    MidX = (InfX+SupX)/2, 
    TakeInf = MidX*MidX > Y ? 1 : 0, 
    NewInf = int(TakeInf) ? InfX : int(MidX), 
    NewSup = int(TakeInf) ? int(MidX) : SupX 
}; 
    public: 
    enum { ret = meta_sqrt<Y,NewInf,NewSup>::ret }; 
}; 

template<int Y, int InfX, int SupX> 
class meta_sqrt<Y, InfX, SupX, true> 
{ 
    public: enum { ret = (SupX*SupX <= Y) ? SupX : InfX }; 
};