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