355 - The Bases Are Loaded (math numbers conversion)

Recently I found this task, which is to convert numbers between arbitrary bases.

My code is working fine, but time limit exceeded.

#include <cstring>
#include <cstdio>

int broj, n;
char uzorak[] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'};

long long ToDec(char a[], long long base)
{
long long dec = 0, b = 1;
int l = strlen(a);
for(int i = l-1; i >= 0; i--)
{
if(a[i] >= '0' && a[i] <= '9')
dec += (a[i]-'0') * b;
else
dec += (a[i] - 'A' + 10) * b;
b *= base;
}

return dec;
}

void ToB2(long long a, int b2)
{
n = 0;
while(a > 0)
{
broj[n] = a%b2;
a = (a-broj[n])/b2;
n++;
}
for(int i = n-1; i>=0; i--)
printf("%c", uzorak[broj[i]]);
}

int main()
{
char a;
int b1, b2, l;
while(scanf("%i %i %s", &b1, &b2, &a))
{
int base = 1;
l = strlen(a);
for(int i = 0; i < l; ++i)
{
if(a[i] >= '0' && a[i] <= '9')
base = (base > a[i]-'0') ? base : a[i]-'0';
else if(a[i] >= 'A' && a[i] <= 'Z')
base = (base > a[i]-'A'+10) ? base : a[i]-'A'+10;
else
{
base = -1;
goto Break;
}
}
base++;
Break:
if((base <= b1)&&(base != -1))
{
printf("%s base %i = ", a, b1);
ToB2(ToDec(a, b1), b2);
printf(" base %i\n", b2);
}
else
printf("%s is an illegal base %i number\n", a, b1);
}
return 0;
}

I would appreciate any suggestions on optimizing my code, thanks!

Is there any faster methods to convert numbers from one base to another or you have to go over base 10?

• #include <cstring> #include <cstdio> --> Is your code compiled using C? – chux Sep 12 '17 at 18:53
• "time limit exceeded." is curious as there is no gross waste of time unless input values are causing UB due to range. Add inputs used, seen, expected and time noted vs. time limit for an even better review. – chux Sep 12 '17 at 19:35
• I suspect code is getting stuck (and then timing out) on the end of input with while(scanf("%i %i %s", &b1, &b2, &a). Suggest instead while(scanf("%i %i %s", &b1, &b2, &a) == 3. Please report if this "unsticks" the time-out issue. – chux Sep 12 '17 at 20:19
• It would be much simpler to use the standard library strtoull() for input; I do think you need to roll your own output function, though. – Toby Speight Dec 12 '17 at 9:59

No, you don't need to convert to base 10. Base 10 is in fact quite slow to operate with, as it is in no way a "native" base for computers, which store integers in binary format.

Let's do the math. Assume you need to convert four digit number from base a to base b. Let x_i denote the digit of the number in base a and y_i the digit in base b:

In base a the number is:

x1*a^3 + x2*a^2 + x3*a^1 + x4*a^0 = ((x1*a + x2)*a + x3)*a + x4

In base b it becomes:

y1*b^3 + y2*b^2 + y3*b^1 + y4*b^0 = ((y1*b + y2)*b + y3)*b + y4

The right side of these equations suggests an algorithm idea: to convert a number to binary format from a string s in base a, start with zero, and in each step multiply the number so-far with a and add the next digit. This requires only one multiplication per loop, not two, like in your approach (although that's not likely the reason why your code is too slow.)

int len = strlen(s);
int i;
unsigned long long number = 0;

for (i = 0; i < len; ++i) {
unsigned digit;
if (s[i] >= '0' && s[i] <= '9') {
digit = s[i] - '0';
} else {
digit = s[i] - 'A' + 10;
}
number = number * a + digit;
}

You had the rest of it already: adding for completeness. For conversion to base b, in each step divide by b.

const char digits[] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'};

char result;
/* Note the end condition here: stop when the number becomes zero */
for(i = 0; number != 0; ++i) {
unsigned digit = number % b;
number /= b;
result[i] = digits[digit];
}

Now result contains the digits backwards. To print them in order:

for (; i >= 0; --i) {
putchar(result[i]);
}

Other minor performance notes

1. Don't call strlen() twice - there's no need to do it more than once anyway, but if there was, you could cache the result and pass as a parameter.

2. The code in main that determines whether the input string is acceptable is too complex: no need to do the conversion here, just check if each digit is in the acceptable range.

1. instead of this:

base = (base > a[i]-'0') ? base : a[i]-'0';

suggest using this:

base = max(base, a[i] - '0');
1. Avoid variable names like l - easy to confuse with 1.

2. Use const before read-only variabes (such as the array of digits).

Minor performance improvements

ToDec()

No need to run down the string twice. No need to call strlen(a);. The post b *= base is potential signed integer overflow, which is UB, even when a is in range. Avoid that.

Use const to allow for some optimizations not seen by some compilers.

base is only good up to base 36, not needed for long long base. OK to use int/unsigned.

No need to check for valid conversion prior to conversion, can do both at the same time.

ToDec() is a misnomer. Code is converting to a long long, not a "dec" which implies decimal - there is no decimal-ness here.

Code assumes ASCII (we will stick with that) yet it is a niche portability concern.

Suggested re-write

long long To_longlong(const char *a, int base, const char **endptr) {
long long value = 0;
while (1) {
inti digit;
int ch = *a;
if (ch >= '0' && ch <= '9') {
digit = ch - '0';
}
else if (ch >= 'A' && ch <= 'Z') {
digit = ch - 'A' + 10;
}
else {
break;  // not a digit
}
if (digit >= base) {
break; // digit out of range
}
value = value * base + digit;
a++;
}
*endptr = a;
return value;
}

Usage

const char *endptr;
long long value = To_longlong(a, b1, &endptr);
if (*endptr) printf("%s is an illegal base %i number\n", a, b1);
else continue_with_conversion();

Note: there is no detection for long long overflow. That requires additional code.

Could use isdigit((unsigned char) ch) in lieu of ch >= '0' && ch <= '9'. Similar for isupper((unsigned char) ch) in lieu of ch >= 'A' && ch <= 'Z'

Using unsigned vs. signed math may improve things a marginally amount on select processors.

OP can experiment. As with all small linear improvements, profiling is recommended.

ToB2()

OP's code is OK, but better to use a%b, a/b idiom (than broj[n] = a%b2; a = (a-broj[n])/b2;) to allow a compiler to recognize that the mod and quotient can be calculated using related code - perhaps at the same time. A good compiler will recognize this.

For performance, usually best to call output functions once and use a simply fputs().

#define ToB2_N (sizeof (long long)*CHAR_BIT + 1)

void ToB2(long long a, int b2) {
assert(a >= 0);  // For this code, only use positive values.
char dest[ToB2_N];
char *p = &dest[ToB2_N - 1]; // start at last position.
*p = '\0'; // null character

// do loop to form an output when a == 0
do {
*(--p) == uzorak[a % b2];
a /= b2;
} while (a);

fputs(p, stdout);
}

OT

char uzorak[] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'};

Should respect display width

char uzorak[] = { // digits
'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E',
'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T',
'U', 'V', 'W', 'X', 'Y', 'Z' };

I'd code as below (even though that adds a null character).

const char uzorak[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";