Exchange system of numbers

Question

I've got the following task:

Keeping in mind Horner's Scheme, write an application that converts a given number x in n-number system to m-number system where m, n <= 10. x is a natural number or zero, x <= unsigned(-1)

My code is as follows:

#include <iostream>

int toDecimal (int, int);
int fromDecimal (int, int);
int convert(int, int, int);

int main()
{
    int base, number, desiredBase;
    std::cin >> number >> base >> desiredBase;
    std::cout << convert(number, base, desiredBase) << std::endl;
}

int toDecimal (int base, int number)
{
    if (number / 10 == 0) {
        return number;
    }
    return (number % 10) + (base * toDecimal (base, number / 10));
}

int fromDecimal (int base, int number)
{
    if (number / base == 0) {
        return number;
    }
    return (number % base) + (10 * fromDecimal (base, number / base));
}

int convert(int number, int base, int desiredBase)
{
    int p = toDecimal(base, number);
    return fromDecimal(desiredBase, p);
}

What can I improve? What can be done better?

Answer 1

In general, the code is well presented, easy to read, but, it is hard to spot the 'Horner's Scheme' in the code.

When implementing a specific algorithm in code, it is useful to clearly comment where the elements of the algorithm are being used.

In this case, the depth-first recursion is processing the most significant digits first, and as a result, it computes the high-order values in the Horner's scheme first. Making that value available to be added to the next value in the system.

Note that this makes tail-recursion optimization impossible, but it does simplify the code.

So, I had to look up how Horner's scheme would help your code, and I had to figure out how your code is helped by it. This is not work that should be hard. You should make that easy for the person reading the code.

I would expect something like:

// based on Horner's scheme: http://en.wikipedia.org/wiki/Horner%27s_method
// The source base of the value can be considered to be Xo in the algorithm, and
// the digit value is the coefficient for that base.

As for your recursion, you can simplify it a little by recursing one level more, and returning 0 (eliminating a duplicated division on each level). Consider your code:

int toDecimal (int base, int number)
{
    if (number / 10 == 0) {
        return number;
    }
    return (number % 10) + (base * toDecimal (base, number / 10));
}

and replacing that code with:

int toDecimal (int base, int number)
{
    if (number == 0) {
        return 0;
    }
    return (number % 10) + (base * toDecimal (base, number / 10));
}

The difference is marginal, trading one division/comparison with a simple comparison and an extra level of recursion.

Regardless, I prefer the reduced code duplication, and it makes the recursion termination easier to see.

The other item I see missing is validation on the input. I would prefer to see some exceptions thrown if the input is in a base that does not support the supplied digits. For example, with the input:

12345 4 10

Putting this all together, I suggest the following:

#include <iostream>
#include <stdexcept>

int toDecimal (int, int);
int fromDecimal (int, int);
int convert(int, int, int);

int main()
{
    int base, number, desiredBase;
    std::cin >> number >> base >> desiredBase;
    try
    {  
        std::cout << convert(number, base, desiredBase) << std::endl;
    } catch (const std::invalid_argument& e)
    {  
        std::cerr << "Unable to convert " << number << " from base " << base << std::endl;
        return 1;
    }
}

int toDecimal (int base, int number)
{
    if (number == 0)
    {  
        return 0;
    }

    int digit = number % 10;
    if (digit >= base)
    {  
        throw std::invalid_argument( "received out-of-range digits in the input for the supplied base");
    }

    return digit + (base * toDecimal (base, number / 10));
}

int fromDecimal (int base, int number)
{
    if (number == 0) {
        return 0;
    }
    return (number % base) + (10 * fromDecimal (base, number / base));
}

int convert(int number, int base, int desiredBase)
{
    int p = toDecimal(base, number);
    return fromDecimal(desiredBase, p);
}

In addition to handling the exceptions from invalid input numbers, you should also handle requests to/from invalid bases as well (like negative or bases > 10).