Dodawanie liter

Dodawanie liczb jest elementarną operacją matematyczną, której dzieci uczą się już na pierwszym etapie swej przygody ze szkolnictwem. Co jednak, jeśli chcielibyśmy dodawać litery? Wówczas trzeba by zdefiniować sobie pojęcie dodawania. Na przykład, ile to powinno być a + a? Najprostszą odpowiedzią jest 2a, lecz wówczas w nasz zbiór liter wchodzą również liczby…

Plusy i minusy liter dodawania

Dodawanie do siebie liter nie jest właściwie zadaniem ani nowym, ani odkrywczym. Wszak ludzkość określiła jedynie 10 znaków dla zapisu liczb, a tworzenie systemów liczbowych o podstawie wyższej niż 10 (w szczególności będących potęgą dwójki) jest wręcz naturalne jeśli mówimy o zapisie arytmetyki komputerów - jest on krótki, zwięzły i rzeczowy. Można się wprawdzie kłócić o to, czy istnieje praktyczny sens zapisywania liczb w systemie o podstawie wyższej niż 16, ale przyjmijmy motywację, że robimy to “bo możemy”.

Zatem jeśli by użyć kolejnych liter alfabetu łacińskiego, a następnie dokleić do nich ich wielkie odpowiedniki, powstałby system liczbowy o bazie 52, którego główną cechą byłby całkowity brak czytelności. Wszak wszyscy wiemy, że 0xFF to 255 w systemie dziesiętnym, ale ile to by było w base52? Niech nas to nie interesuje, przecież powinien to liczyć za nas komputer.

a+a

Zanim przejdę do definiowania odpowiednich klas w języku C++ (wszak nie zdziwiłbym się, gdybym w Pythonie miał już odpowiednie funkcje w STL-u… ;)), odpowiem na pytanie, które zadałem na początku tego wpisu. Otóż a + a = a. Przy zapisie systemu liczbowego jak wcześniej go określiłem, mała litera a stoi na zerowym miejscu, a zatem jest elementem neutralnym dla dodawania (b z kolei jest elementem neutralnym dla mnożenia). Będąc tego świadomym, można rozpocząć pisanie naszego systemu liczbo… literowego.

Do rzeczy

Analogia do nauki dodawania przez dzieci, którą poczyniłem na początku nie jest bezpodstawna. Komputery bowiem, tak jak małe dzieci, dodają liczby w słupkach, tyle że bardzo, bardzo szybko. Suma dodawania dwóch cyfr na pozycji n, dajmy na to x i y wynosi x + y +CARRY, gdzie CARRY jest przeniesieniem wynikającym z dodawania cyfr na pozycji n-1. Dla dodawania dwóch cyfr w danym systemie liczbowym CARRY może przyjmować jedynie wartości “odpowiedników” 0 lub 1.

Możemy sobie zatem zdefiniować klasę Alphabeth, a w niej metodę add, która doda do siebie dwa łańcuchy znakowe. W naszej klasie znajduje się również prywatne pole LETTERS, które jest łańcuchem znakowym i definiuje kolejność występowania liter, a także NEUTRAL określające element neutralny.

std::string Alphabeth::add( std::string left, std::string right ) {
    std::string new_result = "";
    char chl, chr, res;
    int sum, CARRY = 0;
    std::string::iterator itl = left.end();
    std::string::iterator itr = right.end();

Powyższa definicja uwzględnia również określenie dwóch iteratorów wskazujących domyślnie na elementy ZA składnikami dodawania. Iteratory te dekrementujemy z każdym przebiegiem pętli i dodajemy coraz to starsze litery - w końcu zwyczajowo przyjęło się zapisywać liczby od lewej do prawej. Litery aktualnie do siebie dodawane są określone przy pomocy zmiennych chr i chl.

while( itl > left.begin() || itr > right.begin() || CARRY == 1) {
    --itl; --itr;
    /* Neutral character */
    chl = chr = NEUTRAL;
    if( !(itl < left.begin()) ) chl = *itl;
    if( !(itr < right.begin()) ) chr = *itr;
    sum = LETTERS.find(chl) + LETTERS.find(chr);
    res = LETTERS.at( (sum + CARRY) % l_length );
    sum >= l_length ? CARRY = 1 : CARRY = 0;
    new_result.insert(new_result.begin(), res );
}

W każdym kroku pętli aktualnie dodawanym literom zostaje przypisany element neutralny lub odpowiednia litera, jeśli nie wyszliśmy poza zakres. Zapewnia to prawidłowe wykonanie operacji gdy składniki są różnej długości.

Samo dodawanie jest zwykłym dodawaniem modulo z uwzględnieniem bitu przeniesienia, gdzie l_length jest podstawą naszego systemu literowego. W celu określenia wyniku dodawania stosowane są standardowe funkcje biblioteki STL C++.

Na sam koniec usuwamy wszystkie a, które jakimś cudem znalazły się na początku naszej liczby i zwracamy rezultat.

/* Remove a's from the beginning */
while( new_result.at(0) == NEUTRAL )
    new_result.erase(new_result.begin());
return new_result;

Po co to wszystko?

Cały ten kod powstał w celu łatwego umożliwienia wykonania prostego ćwiczenia, które przyszło mi ostatnio do głowy: stworzenia ciągu Fibonacciego złożonego z liter. Całość kodu dostępna jest na Githubie. W wolnym czasie postaram się rozwijać dalej opisaną klasę, więc można zerknąć czasem do zlinkowanego powyżej repozytorium w celu sprawdzenia zmian.