Na początku listopada zapowiedziałem, że przedstawię metaprogram, który policzy liczbę 100!. Wszystko oczywiście już na etapie kompilacji. W części 1 stworzony został zalążek biblioteki BigInteger, umożliwiającej dodawanie dużych liczb całkowitych. Dziś rozszerzę tę bibliotekę o możliwość mnożenia.
Zaczniemy od napisania metafunkcji, która mnoży dowolną dużą liczbę całkowitą przez dowolną liczbę jednocyfrową. Zostanie ona później wykorzystania do mnożenia dowolnych dwóch dużych liczb całkowitych.
Jak przemnożyć dowolną liczbę przez liczbę jednocyfrową (0-9)? Posłużymy się następującym algorytmem:
- Dodaj jedno zero z przodu dużej liczby.
- Dla każdej cyfry dużej cyfry (zaczynając od najmniej znaczącej) wykonaj:
- Pomnóż tę cyfrę przez zadaną liczbę jednocyfrową i dodaj przeniesienie z poprzedniej iteracji. Wynik oznacz jako x.
- Oblicz d = x / 10 oraz m = x % 10.
- Dopisz do wyniku obliczoną cyfrę d, natomiast m przekaż do kolejnej iteracji jako przeniesienie.
- Usuń zbędne zera z przodu uzyskanego wyniku.
Implementacja tego algorytmu wygląda następująco:
namespace BigInteger {
namespace aux {
template<int N, class SeqIter, class Digit, class Incr, class Result>
struct multiply_by_digit_impl {
private:
typedef typename boost::mpl::deref<SeqIter>::type Val;
typedef typename boost::mpl::times<Val, Digit>::type Product;
typedef typename boost::mpl::plus<Product, Incr>::type Sum;
typedef typename boost::mpl::divides<
Sum,
boost::mpl::int_<10>
>::type Div;
typedef typename boost::mpl::modulus<
Sum,
boost::mpl::int_<10>
>::type Mod;
typedef typename boost::mpl::push_back<Result, Mod>::type NextResult;
typedef Div NextIncr;
public:
typedef typename multiply_by_digit_impl<
N - 1,
typename boost::mpl::next<SeqIter>::type,
Digit,
NextIncr,
NextResult,
>::type type;
};
template<class SeqIter, class Digit, class Incr, class Result>
struct multiply_by_digit_impl<0, SeqIter, Digit, Incr, Result> {
typedef typename ::BigInteger::remove_from_end<
Result,
boost::mpl::int_<0>
>::type type;
};
} // namespace aux
template<class Seq, class Digit>
struct multiply_by_digit {
private:
typedef typename boost::mpl::push_back<
Seq,
boost::mpl::int_<0>
>::type ExtSeq;
public:
typedef typename aux::multiply_by_digit_impl<
boost::mpl::size<ExtSeq>::value,
typename boost::mpl::begin::type,
Digit,
boost::mpl::int_<0>,
typename boost::mpl::clear<Seq>::type
>::type type;
};
} // namespace BigInteger
Metafunkcja multiply_by_digit przyjmuje dwa szablonowe parametry: dwie duże liczby całkowite (pierwsza dowolna, Seq, a druga jednocyfrowa, Digit). Na początku tworzona jest liczba ExtSeq poprzez dołożenie jednego zera do Seq. Wynik tej operacji przekazywany jest do metafunkcji multiply_by_digit_impl.
Każde wywołanie metafunkcji multiply_by_digit_impl to jedna iteracja po cyfrach ExtSeq. Dla każdej z nich obliczane są omówione wczesniej wartości d (w kodzie Div) oraz m (w kodzie Mod) i odpowiednio dopisywane do wyniku (tworzonego w parametrze Result). Iterowanie zakończy specjalizacja struktury multiply_by_digit_impl, która usunie z wyniku (Result) znajdujące się na samym początku zbędne zera. W tym celu wykorzystywana jest metafunkcja remove_from_end, którą omówiłem przy okazji implementacji dodawania.
Mamy zatem gotowe mnożenie dowolnie dużych liczb przez liczby jednocyfrowe. W jaki sposób można teraz zaimplementować mnożenie dwóch dowolnych liczb? Wystarczy przemnożyć jedną z nich przez każdą cyfrę drugiej, pamiętając o tym, że z każdą kolejną cyfrą jej rząd rośnie o 1. Uzyskane liczby należy potem zsumować, co da nam oczekiwany wynik. Dokładnie tak uczy się dzieci mnożyć w szkole podstawowej. ;)
Omówioną procedurę mnożenia można zaimplementować tak:
namespace BigInteger {
namespace aux {
template<int N, class Seq1, class Seq2Iter, class Zeros>
struct multiply_impl {
private:
typedef typename boost::mpl::deref<Seq2Iter>::type Digit;
typedef typename multiply_by_digit<Seq1, Digit>::type MultipliedByDigit;
typedef typename boost::mpl::insert_range<
Zeros,
typename boost::mpl::end<Zeros>::type,
MultipliedByDigit
>::type Elem1;
typedef typename multiply_impl<
N - 1,
Seq1,
typename boost::mpl::next<Seq2Iter>::type,
typename boost::mpl::push_back<
Zeros,
boost::mpl::int_<0>
>::type
>::type Elem2;
public:
typedef typename ::BigInteger::add<Elem1, Elem2>::type type;
};
template<class Seq1, class Seq2Iter, class Zeros>
struct multiply_impl<0, Seq1, Seq2Iter, Zeros>
: boost::mpl::push_back<
typename boost::mpl::clear<Seq1>::typem
boost::mpl::int_<0>
>
{};
} // namespace aux
template<class Seq1, class Seq2>
struct multiply
: aux::multiply_impl<
boost::mpl::size<Seq2>::value,
Seq1,
typename boost::mpl::begin<Seq2>::type,
typename boost::mpl::clear<Seq1>::type
>
{};
} // namespace BigInteger
Metafunkcja multiply rozpoczyna iterację po cyfrach liczby Seq2 wywołując pomocniczą metafunkcję multiply_impl. Metafunkcja ta, używając multiply_by_digit, oblicza jedną składową wyniku. Rząd wielkości każdej cyfry uaktualniany jest wykorzystując parametr Zeros, do którego przy każdym rekurencyjnym wywołaniu multiply_impl dokładane jest jedno zero. Uzyskane w każdej iteracji wyniki sumowane są za pomocą metafunkcji add, realizującej dodawanie dużych liczb całkowitych. Częściowa specjalizacja struktury multiply_impl kończy iterowanie i zwraca wynik.
Mnożenie dużych liczb całkowitych w czasie kompilacji programu jest gotowe. Możemy je przetestować na przykład następująco:
using namespace boost::mpl; typedef vector_c<int, 1, 2, 3, 4, 5, 6, 7, 8, 9, 8, 7, 6, 5, 4, 3, 2, 1> X; typedef vector_c<int, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 9, 8, 7, 6, 5, 4, 3, 2, 1> Y; typedef BigInteger::multiply<X, Y>::type Product; BigInteger::print printer(std::cout); for_each<reverse<X>::type>(printer); std::cout << " * "; for_each<reverse<Y>::type>(printer); std::cout << " = "; for_each<reverse<Product>::type>(printer); std::cout << std::endl;
Po skompilowaniu program powinien wypisać:
12345678987654321 * 1234567890987654321 = 15241578870598994324188385789971041
W kolejnej części zaimplementuję liczenie silni. Zapraszam wkrótce. :)
Pliki do pobrania:
Brak komentarzy:
Prześlij komentarz