5
\$\begingroup\$

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?

\$\endgroup\$
3
\$\begingroup\$

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).

\$\endgroup\$
  • \$\begingroup\$ Altrough code readability is important, during algorithmic competitions the speed is the main attribute of the code. Adding exception checking makes code slower and makes me to write less actual code in a given short period of time. And the input is piped from a file ad automatically run on the server, so it isn't really a problem. Evaluating (number % 10) + (base * toDecimal (base, number / 10)) is slower than number / 10 == 0, so it is more beneficial. However, thank you for the time you spent analyzing my code and figuring out my usage of Horner's Sheme. \$\endgroup\$ – enedil Feb 11 '15 at 18:01
  • \$\begingroup\$ @enedil - your points are valid, if you can trust your data inputs, then thevalidation will slow things down. As for the performance of the last check, a lot will depend on the number of digits in the numbers you are comparing. I have not done benchmarks, and I presume you have, but at some point, the number of digits in each number will outweigh the cost of the additional recursive call. Whether you hit that point yet, or not, is only possible to tell with profiling. Pleased to have been able to help in other ways, though. \$\endgroup\$ – rolfl Feb 11 '15 at 18:06
  • \$\begingroup\$ % operator is implemented with / so it must be slower. \$\endgroup\$ – enedil Feb 11 '15 at 21:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.