piątek, 6 stycznia 2012

Metaprogramowanie - implementacja dużych liczb całkowitych (część 3)

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::type.

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