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

Ostatnio przypomniało mi się zadanie z pierwszego semestru studiów. Był to raczej klasyk dla uczących się języka C/C++: implementacja dużych liczb całkowitych. W moim przypadku chodziło konkretnie o policzenie liczby 100!. Prowadzący zaproponował nawet mały konkurs, polegający na jak najefektywniejszej implementacji arytmetyki (zwyciężyć miała osoba, której program najszybciej obliczy wynik), jednak jeśli mnie pamięć nie myli, to do niego nie doszło. ;)

Tak sobie pomyślałem, że można by się tu pokusić o małe oszustwo i policzyć wynik już na etapie kompilacji, a po uruchomieniu programu tylko go wyświetlić. Tego rodzaju programowanie nazywa się metaprogramowaniem.

Mając dziś trochę wolnego czasu, zacząłem pisać bibliotekę do obliczeń na dużych liczbach całkowitych wykonywanych w trakcie kompilacji programu. Ponieważ całość implementacji jest zbyt duża na pojedynczy wpis na blogu, podzielę ją na kilka części i omówię osobno. Końcowym efektem będzie obliczenie liczby 100! w trakcie kompilacji.

Dzisiaj zaimplementujemy dodawanie. Zastanówmy się jak powinno ono wyglądać. Po krótkiej chwili dochodzimy do następującego algorytmu:

1. Wyrównaj długości obu dodawanych liczb ("dokładając" z przodu zera).
2. Dodaj na wszelki wypadek jedno zero z przodu każdej liczby (na wypadek gdyby wynik działania powiększył się o jeden rząd w stosunku do dodawanych liczb).
3. Wykonaj dodawanie zgodnie z zasadami poznanymi w szkole podstawowej. ;)
4. Usuń niepotrzebne zera z przodu uzyskanego wyniku.

Jeżeli ktoś czytał mój ostatni wpis na blogu, to zapewne zauważył, że często wykorzystuję biblioteki Boost. Nie inaczej będzie tym razem i każdemu, kto poważnie myśli o programowaniu w C++ polecam zacząć programować "z Boostem". ;)

Zaczniemy od punktu pierwszego. Wyrównywanie długości obu liczb całkowitych zamkniemy w osobnym pliku BigIntegerExtend.hpp:

#ifndef BIGINTEGEREXTEND_HPP
#define BIGINTEGEREXTEND_HPP

#include <boost/mpl/push_back.hpp>
#include <boost/mpl/size.hpp>

namespace BigInteger
{

namespace aux
{

template<class Seq, class Size, class Elem, bool Equal>
struct extend_impl
{
private:
    typedef typename boost::mpl::push_back<Seq, Elem>::type NextSeq;

public:
    typedef typename extend_impl<
        NextSeq
      , Size
      , Elem
      , boost::mpl::size<NextSeq>::value == Size::value
    >::type type;
};

template<class Seq, class Size, class Elem>
struct extend_impl<Seq, Size, Elem, true>
{
    typedef Seq type;
};

} // namespace aux

template<class Seq, class Size, class Elem>
struct extend
  : aux::extend_impl<
        Seq
      , Size
      , Elem
      , boost::mpl::size<Seq>::value == Size::value
    >
{};

} // namespace BigInteger

#endif // BIGINTEGEREXTEND_HPP

Zaprojektowana struktura extend jest trochę ogólniejszego przeznaczenia. Jej szablonowymi parametrami są:

1. sekwencja kolejnych cyfr liczby z najmniej znaczącą cyfrą na pierwszym miejscu,
2. rozmiar do jakiego należy rozszerzyć liczbę,
3. wartość, którą należy wypełnić sekwencję aż do danego rozmiaru.

Przy każdym rekurencyjnym wywołaniu metafunkcji extend_impl dodawana jest jedna cyfra. Rekurencyjne wywołania kończą się, gdy rozmiar sekwencji zrówna się z przekazanym wcześniej parametrem Size.

Wygląda na to, że pierwszy punkt naszego algorytmu mamy z głowy i... drugi też. Wystarczy zauważyć, że "dołożenie" do każdej liczby jednego zera, to wywołanie napisanej już metafunkcji extend z wartością Size o 1 większą niż rozmiar liczby.

Przed właściwym dodawaniem (trzeci punkt algorytmu) napiszmy najpierw usuwanie zbędnych zer z przodu liczby (punkt czwarty), gdyż wydaje się to bardzo podobne do "dokładania" zer, które już mamy. Usuwać będziemy po jednym zerze rekurencyjnie wywołując odpowiednią metafunkcję. Operację będziemy kontynuować, dopóki nie będzie spełniony przynajmniej jeden z następujących dwóch warunków:

• modyfikowana liczba jest jednocyfrowa,
• cyfra będąca kandydatem do usunięcia jest różna od zera.

Tak zdefiniowany warunek zakończenia wywołań rekurencyjnych prowadzi do napisania następującego kodu (plik BigIntegerRemoveFromEnd.hpp):

#ifndef BIGINTEGERREMOVEFROMEND_HPP
#define BIGINTEGERREMOVEFROMEND_HPP

#include <boost/mpl/back.hpp>
#include <boost/mpl/pop_back.hpp>
#include <boost/mpl/size.hpp>

namespace BigInteger
{

namespace aux
{

template<bool Terminate, class Seq, class Elem>
struct remove_from_end_impl
{
private:
    typedef typename boost::mpl::pop_back<Seq>::type NextSeq;
    typedef typename boost::mpl::back<NextSeq>::type LastInNextSeq;

public:
    typedef typename remove_from_end_impl<
        (boost::mpl::size<NextSeq>::value == 1) or (LastInNextSeq::value != Elem::value)
      , NextSeq
      , Elem
    >::type type;
};

template<class Seq, class Elem>
struct remove_from_end_impl<true, Seq, Elem>
{
    typedef Seq type;
};

} // namespace aux

template<class Seq, class Elem>
struct remove_from_end
  : aux::remove_from_end_impl<
        (boost::mpl::size<Seq>::value == 1)
        or (boost::mpl::back<Seq>::type::value != Elem::value)
      , Seq
      , Elem
    >
{};

} // namespace BigInteger

#endif // BIGINTEGERREMOVEFROMEND_HPP

Metafunkcja remove_from_end przyjmuje 2 szablonowe parametry:

1. sekwencję z cyframi liczby,
2. cyfrę, którą należy usuwać rekurencyjnie, aż spełniony zostanie ustalony przez nas wcześniej warunek.

Przejdźmy zatem do ostatniej fazy implementacji: implementacji właściwego dodawania. Zasady każdy powinien znać. :) Dodawanie wykonywać będzie metafunkcja add. Prawdę mówiąc może już ona wykonać pełne dodawanie wykorzystując extend i remove_from_end. Metafunkcję add zamknijmy w pliku BigIntegerAdd.hpp:

#ifndef BIGINTEGERADD_HPP
#define BIGINTEGERADD_HPP

#include "BigIntegerExtend.hpp"
#include "BigIntegerRemoveFromEnd.hpp"

#include <boost/mpl/arithmetic.hpp>
#include <boost/mpl/begin.hpp>
#include <boost/mpl/clear.hpp>
#include <boost/mpl/comparison.hpp>
#include <boost/mpl/deref.hpp>
#include <boost/mpl/int.hpp>
#include <boost/mpl/min_max.hpp>
#include <boost/mpl/next_prior.hpp>
#include <boost/mpl/push_back.hpp>
#include <boost/mpl/size.hpp>
#include <boost/mpl/transform.hpp>

namespace BigInteger
{

namespace aux
{

template<int N, class Iter1, class Iter2, class Incr, class Result>
struct add_impl
{
private:
    typedef typename boost::mpl::deref<Iter1>::type Val1;
    typedef typename boost::mpl::deref<Iter2>::type Val2;

    typedef typename boost::mpl::plus<Val1, Val2, 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 add_impl<
        N - 1
      , typename boost::mpl::next<Iter1>::type
      , typename boost::mpl::next<Iter2>::type
      , NextIncr
      , NextResult
    >::type type;
};

template<class Iter1, class Iter2, class Incr, class Result>
struct add_impl<0, Iter1, Iter2, Incr, Result>
{
    typedef Result type;
};

} // namespace aux

template<class Seq1, class Seq2>
struct add
{
private:
    typedef typename boost::mpl::max<
        typename boost::mpl::size<Seq1>::type
      , typename boost::mpl::size<Seq2>::type
    >::type Size;

    typedef typename ::BigInteger::extend<
        Seq1
      , typename boost::mpl::next<Size>::type
      , boost::mpl::int_<0>
    >::type ExtSeq1;

    typedef typename ::BigInteger::extend<
        Seq2
      , typename boost::mpl::next<Size>::type
      , boost::mpl::int_<0>
    >::type ExtSeq2;

    typedef typename aux::add_impl<
        boost::mpl::size<ExtSeq1>::value
      , typename boost::mpl::begin<ExtSeq1>::type
      , typename boost::mpl::begin<ExtSeq2>::type
      , boost::mpl::int_<0>
      , typename boost::mpl::clear<Seq1>::type
    >::type Sum;

public:
    typedef typename ::BigInteger::remove_from_end<
        Sum
      , boost::mpl::int_<0>
    >::type type;
};

} // namespace BigInteger

#endif // BIGINTEGERADD_HPP

Uff... Wygląda nieco bardziej skomplikowanie. Rzućmy jednak okiem: metafunkcja add wykonuje dokładnie taki algorytm, jaki wymyśliliśmy na samym początku:

1. oblicza maksimum z rozmiarów obu liczb: Size,
2. "rozszerza" obie liczby do rozmiaru Size+1 "dostawiając" zera za najbardziej znaczącą cyfrą,
3. wykonuje szkolne dodawanie skonstruowanych wcześniej liczb,
4. usuwa z wyniku zbędne zera.

Właściwe dodawanie wykonane zostało w metafunkcji add_impl. Iteruje ona po cyfrach obu liczb jednocześnie i w każdym kroku wyzacza jedną cyfrę wyniku: Mod.

Mamy już wszystko gotowe. Stwórzmy jeszcze możliwość "wypisywania" liczby do strumieni wyjściowych (plik BigIntegerPrint.hpp):

#ifndef BIGINTEGERPRINT_HPP
#define BIGINTEGERPRINT_HPP

#include <ostream>

namespace BigInteger
{

class print
{
public:
    print(std::ostream& out_) : out(out_) {}

    template<class T>
    void operator()(const T x)
    {
        out << x;
    }

private:
    std::ostream& out;
};

} // namespace BigInteger

#endif // BIGINTEGERPRINT_HPP

Szablonowa metoda operator() wypisuje po prostu do strumienia przekazany obiekt (w naszym przypadku cyfry liczby).

Aby ułatwić korzystanie z bilioteki zamieśćmy dołączanie poszczególnych metafunkcji w osobnym pliku BigInteger.hpp, który będziemy rozszerzać, gdy zaimplementujemy mnożenie i liczenie silni:

#ifndef BIGINTEGER_HPP
#define BIGINTEGER_HPP

#include "BigIntegerAdd.hpp"
#include "BigIntegerPrint.hpp"

#endif // BIGINTEGER_HPP

Przetestujmy teraz dodawanie naszych liczb:

#include "BigInteger.hpp"

#include <boost/mpl/for_each.hpp>
#include <boost/mpl/reverse.hpp>
#include <boost/mpl/vector_c.hpp>

#include <iostream>

int main()
{
    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::add<X, Y>::type Sum;

    BigInteger::print printer(std::cout);
    for_each<reverse<X>::type>(printer);
    std::cout << " + ";
    for_each<reverse<Y>::type>(printer);
    std::cout << " = ";
    for_each<reverse<Sum>::type>(printer);
    std::cout << std::endl;
}

Kompilujemy (czyt. liczymy wynik) i uruchamiamy. Powinniśmy zobaczyć:

12345678987654321 + 1234567890987654321 = 1246913569975308642

Dodawanie dużych liczb całkowitych w trakcie kompilacji programu mamy skończone. Już wkrótce mnożenie, więc zapraszam za jakiś czas. :)

PS. Chyba muszę pomyśleć nad jakimś serwerem, gdzie mógłbym umieszczać tworzone pliki.

Pliki do pobrania:

• BigInteger.hpp
• BigIntegerAdd.hpp
• BigIntegerExtend.hpp
• BigIntegerPrint.hpp
• BigIntegerRemoveFromEnd.hpp
• BigIntegerTest.cpp