Wtam po nieco dłuższej przerwie.
Powracamy do tematu metaprogrogramowania, a konkretnie do biblioteki manipulującej dużymi liczbami całkowitymi. Dziś ostatnia część - policzymy silnię liczby 100. Do obliczenia wyniku rozszerzymy naszą bibliotekę BigInteger, która potrafi już dodawać i mnożyć dowolnie duże liczby.
Dla przypomnienia, silnię możemy rekurencyjnie zdefiniować następująco:
n! = 0 | , dla n = 0 |
n! = n * (n - 1)! | , dla n > 0 |
Definicję tę wprost wykorzystamy implementując silnię w naszej bibliotece.
template<class Seq> struct factorial { private: typedef boost::mpl::vector_c<int, 0> Zero; typedef boost::mpl::vector_c<int, 1> One; public: typedef typename aux::factorial_impl< One, One, Seq, boost::mpl::or_< boost::mpl::equal< Seq, Zero, boost::mpl::equal_to<boost::mpl::_1, boost::mpl::_2> >, boost::mpl::equal< Seq, One, boost::mpl::equal_to<boost::mpl::_1, boost::mpl::_2> > >::value >::type type; };
Dla użytkowników przygotowana została metafunkcja factorial. Jej jedynym szablonowym argumentem jest dowolnie duża liczba całkowita. Obliczony wynik zdefiniowany zostanie jako factorial
Właściwe liczenie silni wykonywane jest w pomocniczej metafunkcji factorial_impl
namespace aux { template<class Result, class Factor, class LastFactor, bool Finish> struct factorial_impl { private: typedef boost::mpl::vector_c<int, 1> One; typedef typename BigInteger::multiply<Result, Factor>::type NextResult; typedef typename BigInteger::add<Factor, One>::type NextFactor; public: typedef typename factorial_impl< NextResult, NextFactor, LastFactor, boost::mpl::equal< Factor, LastFactor, boost::mpl::equal_to<boost::mpl::_1, boost::mpl::_2> >::value >::type type; }; template<class Result, class Factor, class LastFactor> struct factorial_impl<Result, Factor, LastFactor, true> { typedef Result type; }; } // namespace aux
Metafunkcja factorial_impl posiada cztery szablonowe argumenty. Są to kolejno:
- Result - dotychczas obliczony rezultat,
- Factor - czynnik, przez który należy przemnożyć Result,
- LastFactor - ostatni czynnik, przez który będziemy mnożyć Result (musimy wiedzieć, kiedy się zatrzymać),
- Finish - wartość logiczna determinująca, czy wynik jest już obliczony.
Dotychczas obliczony rezultat Result przemnażany jest przez czynnik Factor, dając NextFactor. Następnie Factor powiększamy o 1, otrzymując NextFactor. Obie te liczby przekazujemy do kolejnego rekurencyjnego wywołania metafunkcji factorial_impl.
Kiedy kończymy rekurencyjne wywołania? Wtedy, gdy właśnie przemnożyliśmy Result przez ostatni czynnik tzn. wtedy gdy Factor jest równy LastFactor. Rekurencyjne wywołanie "przechwytywane" jest wówczas przez specjalizację metafunkcji factorial_impl, która definiuje Result jako type, co jest standardową nazwą na zwracane typy w przypadku bibliotek np. Boost. Warto również przestrzegać podobnej konwencji przy pisaniu własnego kodu, gdyż pozwala to wówczas na łatwe współgranie naszego kodu z algorytmami wchodzącymi w skład biblioteki Boost MPL.
Biblioteka jest gotowa. Jesteśmy w stanie ją przetestować. Rozszerzymy w tym celu nasz program BigIntegerTest.
typedef vector_c<int, 0, 0, 1> Z; typedef BigInteger::factorial<Z>::type Factorial; for_each<reverse<Z>::type>(printer); std::cout << "! = "; for_each<reverse<Factorial>::type>(printer); std::cout << std::endl;
Kompilujemy (trzeba uzbroić się w cierpliwość) i uruchamiamy. Powyższy fragment kodu powinien wyświetlić na ekranie:
100! = 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
Problem rozwiązany. Liczba 100! obliczona została na etapie kompilacji, a podczas uruchomienia programu po prostu wyświetlona. Czas działania programu krótszy od mrugnięcia okiem. ;)
Pliki do pobrania:
Brak komentarzy:
Prześlij komentarz