Addition of Letters

Addition of numbers is basic arithmetic operation which children learn in elementary schools. What if we’d like to add letters? In that case we must define what their addition means. For example, what’s the result of a + a? The easiest answer is 2a, but it includes a number…

Pros and Cons of Letters Addition

Addition of letters isn’t something new or groundbreaking. We have only 10 digits after all and creating numeral systems with base over 10, especially the ones which are a power of 2, is natural when we’re talking about computers’ arithmetic. Hexadecimal numbers are short and to the point.

If we were to use all letters of latin alphabet, including capital letters, we’d end up with base 52 numeral system with its main feature being a complete lack of clarity. We all know that 0xFF is decimal 255, but what’s the equivalent in base52? Let’s use a computer to calculate.

a+a

Before I move to C++ implementation, I’ll answer the question I asked in the first paragraph. a + a = a. Lower-case letter a is the first letter of our system, so it’s a neutral element for addition. b is thus a neutral element for multiplication. Knowing that, we can start writing our letter system.

To the Point

The analogy of learing addition in elementary schools wasn’t pointless. Computers are like children: they perform columnar additions but very, very fast. Sum of two digits x and y at position n is x + y +CARRY,, where CARRY is the extra digit carried from addition of digits at position n-1 over the base of numeral system. For any numeral system CARRY can only have a value of 0 or 1 (or the equivalent of these numbers), because you cannot two digits over numeral system’s base.

Let’s define Alphabet class with a method add which adds two strings. Inside the class we’ll also define a LETTERS member which defines the order of letters and NEUTRAL field which defines a neutral letter for addition.

std::string Alphabet::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();

    // ...
}

We also fined two iterators pointing to after-the-last element of strings. Each loop we’ll decrement these iterators to add more significant letters. Current letters are hold in chr and chl variables.

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);
}

In each step of the loop we add two letters and the carry bit from the previous step and check if the sum of these 3 components is is outside of the base of our system (depicted as l_length). Depending on it, we set or reset carry bit. We also must make sure that both addition components might be a different length.

At the end we remove all a (neutral elements) from the beginning of our number and return the result

while(new_result.at(0) == NEUTRAL)
    new_result.erase(new_result.begin());
return new_result;

But Why?

I wrote this program for fun to do a little excersise: create a Fibonacci sequence made of letters. You can see the source code in git repository.