How to allocate enough memory to convert an unsigned long long int into string

Question

With a code where I have a struct:

struct fibo_entry {                 /* Definition of each table entry */
    int n;
    unsigned long long int lli;     /* 64-bit integer */
    char *str;
};

I have to solve a Fibonacci sequence where I have the following:

    fibo_table = (struct fibo_entry *)malloc(sizeof(struct fibo_entry));
    //fibo_table->str = (char *)malloc(1 + 8 * sizeof(char)); // !!??

    for (i = 0; i <= n; i++) {
        fibo_table[i].n = i;

    if (i == 0) {
        fibo_table[i].lli = 0;
        //sprintf(fibo_table[i].str, "%llu", fibo_table[i].lli);
        //fibo_table[i].str = atoi(fibo_table[i].lli);
      
    } else if (i == 1) {
        fibo_table[i].lli = 1;
    } else {
        fibo_table[i].lli = fibo_table[i-1].lli + fibo_table[i-2].lli;
        //log10(fibo_table[i].lli);
    }
}

The process to calculate Fibonacci is done, the problem that I have comes when I have to calculate the memory that I need to allocate a long long int in the string.

I know that the numbers use 64 bits each and I tried with malloc and the concept that sprintf should work to convert one in another, but I can't find a solution. Every time that I try to run the program, just fail.

do you really need to save it to a string, or do you just need to `printf` it? — yano, Mar 17 '21 at 14:44
Why do you need to the number as a string anyway? This is totally redundant. Otherwise you could use [`snprintf`](http://www.cplusplus.com/reference/cstdio/snprintf/). Read its documentation closely, especially the "Return value" section. — Jabberwocky, Mar 17 '21 at 14:44
2^64 = 18446744073709551616-1, so the longest string can be `strlen("18446744073709551615")+1` — Devolus, Mar 17 '21 at 14:44
Related question: [How do I determine the number of digits of an integer in C?](https://stackoverflow.com/q/1068849/10077) — Fred Larson, Mar 17 '21 at 14:45
more pertinent, you're allocating space for only one `struct fibo_entry` .. so you're invoking undefined behavior for every `n > 0` in your `for` loop. If `n == 0` always then no need for the loop. — yano, Mar 17 '21 at 14:48
`sizeneeded = 1 + snprintf(NULL, 0, "%llu", longlongunsignedvalue);` — pmg, Mar 17 '21 at 15:01

Adrian Mole · Answer 1 · 2021-03-17T15:29:25.293

If you are writing a (positive) number, n, in decimal notation (as the %llu format specifier will), then the number of digits will be (the integral part of) log₁₀(n) + 1.

So, in order to (pre-)determine the maximum buffer size required, you can use the log10 function on the compiler-defined constant, ULLONG_MAX (this is the maximum value that an unsigned long long int can have). Note that, when allocating the character buffer, you should add 1 to the number of digits, to allow for the nul-terminator in your string.

The following short program may be helpful:

#include <stdio.h>
#include <stdint.h>
#include <math.h>
#include <limits.h>

int main()
{
    size_t maxdigits = (size_t)(log10((double)(ULLONG_MAX)) + 1);
    printf("Max. digits in unsigned long long = %zu!\n", maxdigits);
    printf("Max. value for the type is: %llu\n", ULLONG_MAX);
    return 0;
}

On most modern systems, unsigned long long int will be 64 bits, with a maximum value of 18446744073709551615 (20 digits); however, it is better to use the platform/compiler-specific ULLONG_MAX, rather than relying on any particular value being correct.

Further, rather than calculating this maxdigits value multiple times, you need only calculate a 'global' constant once, then re-use that as and when required.

`static const size_t maxdigits = sizeof(unsigned long) * CHAR_BIT * 30103 / 100000 + 1;` provides a compile-time constant and does not require a math routine. (.30103 is a smidge over log(2).) — Eric Postpischil, Mar 17 '21 at 15:31
@EricPostpischil Fantastic - but shouldn't that be taking `sizeof(unsigned long long)`? — Adrian Mole, Mar 17 '21 at 15:33
@BrunoMartín As yano pointed out in the comments, you need to allocate space for `n+1` structures, not just one: `fibo_table = malloc(sizeof(struct fibo_entry) * (n+1));` — Adrian Mole, Mar 17 '21 at 15:39

chux - Reinstate Monica · Answer 2 · 2021-03-19T16:33:35.667

How to allocate enough memory to convert an unsigned long long int into string

With an n-bit unsigned integer, a buffer of log10(2^n - 1) + 1 + 1 is needed. +1 for "ceiling" and +1 for the null character.

To find this value at compiler time, could use:

#define LOG10_2_N 302
#define LOG10_2_D 1000
#define ULL_STR_SIZE1 (sizeof (unsigned long long)*CHAR_BIT * LOG10_2_N / LOG10_2_D + 2)

To find this at pre-processor time is a little trickier as we need to find the bit width via macros. This approach also takes space advantage if rare padding bits are used.

// Numbers of bits in a Mersenne Number
// https://mathworld.wolfram.com/MersenneNumber.html
// https://stackoverflow.com/a/4589384/2410359
#define IMAX_BITS(m) ((m)/((m)%255+1) / 255%255*8 + 7-86/((m)%255+12))
#define ULLONG_BIT_WIDTH IMAX_BITS(ULLONG_MAX)

// 28/93 is a tight fraction for log10(2)
#define LOG10_2_N 28
#define LOG10_2_D 93
#define ULL_STR_SIZE2 (ULLONG_BIT_WIDTH * LOG10_2_N / LOG10_2_D + 1 + 1)

ULL_STR_SIZE2 is suitable for #if ULL_STR_SIZE2 ... processing.

fibo_table[i].str = malloc(ULL_STR_SIZE2);
if (fibo_table[i].str) {
  sprintf(fibo_table[i].str, "%llu", fibo_table[i].lli);

Or at run-time, to "right size", call snprintf() first and find the size needed for per each integer via the return value of *printf().

int n = snprintf(NULL, 0, "%llu", fibo_table[i].lli);
fibo_table[i].str = malloc(n + 1);
if (fibo_table[i].str) {
  sprintf(fibo_table[i].str, "%llu", fibo_table[i].lli);

Or slightly more efficient, form a worst case size temporary buffer, write to it and then duplicate the string.

char tmp[ULL_STR_SIZE2];
snprintf(tmp, sizeof tmp, "%llu", fibo_table[i].lli);
fibo_table[i].str = strdup(tmp);

Alternative: change pointer char *str to an array.

struct fibo_entry {
  int n;
  unsigned long long int lli;
  //char *str;
  char *str[ULL_STR_SIZE2];
};

and use

snprintf(fibo_table[i].str, sizeof fibo_table[i].str, "%llu", fibo_table[i].lli);

Best to not assume long long is 64-bit. It is at least 64-bit.

@SGeorgiades Yes 146/485 is optimal to bitwidths 28000+. 28/93 is sufficient for bit widths up to 92. Either fraction, when not optimal does error on being a tad too big. With pre-processor math being at least 63-bit, many such fractions are possible including 301031/1000000 being clearly derived from log10(2) = 0.301030927835... — chux - Reinstate Monica, Mar 19 '21 at 16:17
Should be 0.3010299956... --> 301030/1000000 or `30103L/100000` — chux - Reinstate Monica, Mar 20 '21 at 07:39

Asaf Itach · Answer 3 · 2021-03-17T17:16:36.673

0

size_t CountDigit(long long int num)
{
    size_t count = 0;

    if(num < 0)
    {
        count++;
    }

    while (num)
    {
         count++;
         num \=10;
    }
    count++;\\thats for the '\0'
    return (count);
}

then you can use count for malloc and after that you can use sprintf or do it yourself, to insert the right chars in it.

edited Mar 17 '21 at 17:16

answered Mar 17 '21 at 16:38

Asaf Itach

300
6
13

score 0 · Answer 4 · answered Mar 31 '21 at 15:25

You can calculate how many digits you need to use doing something like number_digits = (int)log10((double)num) + 1; and then reserve enough space with fibo_table[i].str = malloc(number_digits * sizeof(char)); remember you need to do this every for iteration, after those two steps you can now use the sprintf as you were sprintf(fibo_table[i].str, "%llu", fibo_table[i].lli);, code would look something like this:

 int number_digits;
 for (i = 0; i <= n; i++) {
 if (i == 0) {
  ....
 } else if (i == 1) {
  ....
 } else {
  ....
 }
 number_digits = (int)log10((double)i) + 1;
 fibo_table[i].str = malloc(number_digits*sizeof(char));
 sprintf(fibo_table[i].str, "%llu", fibo_table[i].lli);
}

How to allocate enough memory to convert an unsigned long long int into string

4 Answers4