C base conversion from decimal to ternary

Question

I'm converting an integer value to a ternary number (which is a String). I suspect there should be a better way to achieve this with less computational effort.

My algorithm directly implements the long division method to convert a number between decimal and any base.

char *get_ternary_str(int value) {
  char buffer[3] = { "000" };
  int dividend = value;

  int i = 0;
  do {
    int remainder = dividend % 3;
    dividend = dividend / 3;
    buffer[i] = ((char)remainder + '0');
    i++;
  } while(dividend >= 1 && i < 3);

  char temp = buffer[2];
  buffer[2] = buffer[0];
  buffer[0] = temp;

  return buffer;
}

Even if in this example the ternary number is 3 digits long, my goal is to make it n-digit long. Suggestions on how to do this to n-digit ternary numbers are also welcome.

Answer 1

• You should allocate your buffer dynamically using malloc.
• You can initialize your char array with zeros using memset.
• And lastly, you can calculate the char array length mathematically. Ceiling to Log [value] base 3 will give you the character size of your string. And please keep in mind to add an extra char to use null.

Because of you ask for suggestion, i'm not providing code. But, if you need further help, you can indicate on comment.

Answer 2

Code has problems.

Returning a pointer to a local variable

Returning a pointer to a local (non-static) variable is undefined behavior (UB). Do not rely on that memory to be valid after the function is complete.

char *get_ternary_str(int value) {
  char buffer[3] = ...
  ...
  return buffer;  // UB
}

Fails with negative numbers

-1 % 3 --> -1, so remainder + '0' will not generate a digit character.

int remainder = dividend % 3;
...
buffer[i] = ((char)remainder + '0');

Insufficient space

buffer[3] is too small for a string of "000" as space is needed for the null character. buffer[3] is big enough for an array of 3 digit characters, but certainly a string is desired.

// char buffer[3] = { "000" };
char buffer[3+1] = { "000" };

Null character never assigned

Certainly the result should be a string which requires a null character '\0'. Code needs to be amended to insure that.

---

my goal is to make it n-digit long
Suggestions on how to do this to n-digit ternary numbers are also welcome.

A char buffer is needed to cope with the formed string. A simple solution is to pass in a buffer pointer large enough for the worse case. I recommend to also pass in the size of the buffer.

Below is a solution to handle any base 2-36.

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

// Maximum buffer size (worst case: INT_MIN and base 2)
#define ITOA_BASE_N (1 + sizeof(int)*CHAR_BIT + 1)

char *itoa_base(char *dest, size_t sz, int i, unsigned base) {
  char buf[ITOA_BASE_N];
  char *s = &buf[sizeof buf - 1];  // set to last character.
  *s = '\0';
  unsigned u = (unsigned) i;  // Use unsigned to cope with INT_MIN ...
  if (i < 0) {
    u = -u;                   // ... as -INT_MIN is UB
  }
  do {
    *(--s) = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"[u % base];
    u /= base;
  } while (u);
  if (i < 0) {
    *(--s) = '-';
  }
  size_t size_used = &buf[sizeof buf] - s;
  if (size_used > sz) {
    return NULL;  // or some other error handling.
  }
  return memcpy(dest, s, size_used);
}

The test employs a compound literal for temporary storage, but one could pass in a fixed buffer if desired.

#define TO_BASE3(x) itoa_base((char [ITOA_BASE_N]){0}, ITOA_BASE_N, (x), 3)

void test3(int x) {
  char *s = TO_BASE3(x);
  // do stuff with `s`, it is valid for until the end of this block
  printf("base10:%11d base3:'%s'\n", x, s);
}

int main(void) {
  test3(0);
  test3(1);
  test3(42);
  test3(-81);
  test3(INT_MAX);
  test3(INT_MIN);
}

Output

base10:          0 base3:'0'
base10:          1 base3:'1'
base10:         42 base3:'1120'
base10:        -81 base3:'-10000'
base10: 2147483647 base3:'12112122212110202101'
base10:-2147483648 base3:'-12112122212110202102'

Answer 3

You can trade some memory space for calculation time, if that is your concern, using a simple and small look-up table.

Consider this C++ (earlier versions of your question asked for ideas in that language too) snippet as an example of the algorithm I'm proposing.

#include <iostream>
#include <array>
#include <vector>
#include <string>
#include <iomanip>
#include <algorithm>
#include <limits>

std::string ternary_from(int value)
{ 
    // The idea is to elaborate three figures (in base 3) at a time
    constexpr int dim = 3 * 3 * 3;

    // Note the values, are "reversed"
    static const std::array<std::string, dim> inner_parts {
        "000", "100", "200", "010", "110", "210", "020", "120", "220", 
        "001", "101", "201", "011", "111", "211", "021", "121", "221", 
        "002", "102", "202", "012", "112", "212", "022", "122", "222" 
    };

    static const std::array<std::string, dim> parts {
        "", "1", "2", "01", "11", "21", "02", "12", "22", 
        "001", "101", "201", "011", "111", "211", "021", "121", "221", 
        "002", "102", "202", "012", "112", "212", "022", "122", "222" 
    };

    if ( value == 0 )
        return std::string{"0"};

    std::string result;

    // Thanks @Chux for recalling that -INT_MIN is UB
    unsigned tmp = value;
    if ( value < 0 )
        tmp = -tmp;

    // note that 'dim' = 27, so you are performing a third of the calculations
    while (tmp >= dim)
    {
        unsigned remainder = tmp % dim;
        // concatenating a string at the end is easier...
        result += inner_parts[remainder];
        tmp = tmp / dim;
    }
    result += parts[tmp];

    if (value < 0)
        result += '-';

    // now the string needs to be reversed. e.g. 3 -> 10(3), not 01 
    std::reverse(result.begin(), result.end());
    return result;
}

int main()
{
    std::vector<int> tests {
        42, -8, 0, 81, 27, -28, std::numeric_limits<int>::max(), std::numeric_limits<int>::min()
    };

    std::cout << "   decimal           ternary\n";
    for (int i : tests)
    {
        std::cout << std::setw(12) << i << std::setw(23) << ternary_from(i) << '\n';
    }
}

It outputs

   decimal           ternary
          42                   1120
          -8                    -22
           0                      0
          81                  10000
          27                   1000
         -28                  -1001
  2147483647   12112122212110202101
 -2147483648  -12112122212110202102

Answer 4

I allocate dynamic memory in the main function and pass a pointer to the function. This way I can manage the memory. For each allocation you need a deallocation. I allocate 1 element more than string length for string termination. You algorithm is nearly unchanged. I changed the index of the buffer to avoid reordering of buffer elements.

#include<stdio.h>
#include<stdlib.h>

void get_ternary_str(char* buffer, int value, unsigned int n) {
  int dividend = value;

  int i = 0;
  do {
    int remainder = dividend % 3;
    dividend = dividend / 3;
    buffer[n - 1 - i] = ((char)remainder + '0');
    i++;
  } while(i < n);

  buffer[i] = 0;
}

int main() {
    int n = 5;
    char* buffer = (char*) malloc(n * sizeof(char));

    int value = 31;
    get_ternary_str(buffer, value, n - 1);

    printf("%s", buffer);
    free(buffer);
    return 0;
}

With the idea from Y.Doktur and here is the same code with dynamic length. I use a pointer to pointer to pass and receive a pointer.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

char* get_ternary_str(unsigned int value) {
  int n = value > 2 ? 1 + floor(log(value) / log(3)) : 1;
  char* buffer = (char*) malloc((n+1) * sizeof(char));
  int dividend = value;

  int i = 0;
  do {
    int remainder = dividend % 3;
    dividend = dividend / 3;
    buffer[n - 1 - i] = ((char)remainder + '0');
    i++;
  } while(i < n);

  buffer[i] = 0;
  return buffer;
}

int main() {

  int value = 31;
  char* buffer = get_ternary_str(value);

  printf("%s", buffer);
  free(buffer);
  return 0;
}