Incrementing result as integer array digits in C

Question

I have a function which calls another function and checks for condition to see if it's true, then it increments an integer. It's all fine and working but there will be a problem for very large results. It couldn't fit even in long long.

Example:

unsigned long long div(int num_first[], int num_second[])
{
    unsigned long long div_result = 0;

    while (compare(num_first, num_second) != -1)
    {
        divsub(num_first, num_second);
        div_result++;
    }

    return div_result; // return div_result to main
}

That function works fine, but if div_result gets too large it crashes or causes undefined behavior. I want to store its result as array like so:

div_result = 25464878454

I want it to be:

div_result[max] = {2, 5, 4, 6, 4, 8, 7, 8, 4, 5, 4}

How do I achieve this?

EDIT: I decided to use unsigned long long as folks suggest. That suits my case.

I'm a bit confused, why an array and not a simple comparison to a max to take appropriate actions (i.e. like increment another counter to keep track of the number of times you reach max?) — David C. Rankin
– David C. Rankin, Commented Apr 30, 2015 at 19:12
It needs to be an array... another counter is not a good idea. — vvvsg
– vvvsg, Commented Apr 30, 2015 at 19:14
what about unsigned long long then you would have duplicated the range — jhole
– jhole, Commented Apr 30, 2015 at 19:14
@WashingtonGuedes they don't really matter here. problem is div_result — vvvsg
– vvvsg, Commented Apr 30, 2015 at 19:15
@vvvsg Q1, make the function the same type as div_result which is long long. Q2, you want div_result to be an array. That's the coding style of the operands innit? — Weather Vane
– Weather Vane, Commented Apr 30, 2015 at 19:45

jhole · Accepted Answer · 2015-04-30 19:46:04Z

1

you can write your own little bigint plus increment functionality:

#include <iostream>

using namespace std;

const int MAXDIGITS=12;

void inc(int bignum[MAXDIGITS])
{
    ++bignum[MAXDIGITS-1];
    int carry=0;
    for(int i = MAXDIGITS-1; i>=0; --i)
    {
        bignum[i] += carry;
        if(bignum[i]>9)
        {
            carry = 1;
            bignum[i] = 0;
        }
        else
            break;
    }
}

int main()
{
    int div_result[MAXDIGITS] = {0};

    // test inc function
    for(int i=0; i<9999991; ++i)
        inc(div_result);

    for(int i=0; i<MAXDIGITS; ++i)
        cout << div_result[i];

    return 0;
}

answered Apr 30, 2015 at 19:46

jhole

4,2712 gold badges24 silver badges38 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

jhole Over a year ago

Well, the important part inc would be same in C I guess.

Weather Vane Over a year ago

I am beginning to suspect that OP didn't write the bigint functions he is calling, otherwise he would not be having this trouble, and would have used the same scheme for his counter..

vvvsg Over a year ago

I DID RIGHT MY BIG INT FUNC. anyway i'm gonna use unsigned long long.

jhole Over a year ago

@WeatherVane: ha, right, would save another instruction

David C. Rankin · Accepted Answer · 2015-05-02 15:50:03Z

Well since I worked on your original question, I'll go ahead and post the results for that as well in case you change your mind. Converting a number to an array can be approached in a number of ways. Here is one scheme using a recursive function and a helper to correct the order of the digits.

note: for 32-bit OS, overflow will occurr due to x86 utilizing a 4-bit long, a 32-bit safe version using 8-bit long long is included below, a 3rd version using preprocessor directives integrating both versions is included at the end:

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

#define MAXDIG 32

void digits2array (long x, long *a, size_t *idx);
int digits2array_rev (long x, long *a, size_t *i);

int main (void) {

    long n = 25464878454;
    long ar[MAXDIG] = {0};
    size_t idx = 0;
    int i = 0;

    digits2array (n, ar, &idx);    /* convert n to array    */

    printf ("\n array:\n\n");

    for (i = 0; i < idx; i++)       /* output results       */
        printf ("   ar[%2d] : %ld\n", i, ar[i]);

    return 0;
}

/* converts x to array of digits in a (reverse order) */
int digits2array_rev (long x, long *a, size_t *i) 
{
    if (x < 10) {
        a[(*i)++] = x;
        return x;
    }

    a[(*i)++] = x % 10;

    return digits2array_rev (x / 10, a, i);
}

/* helper function to reverse results of digits2array_rev */
void digits2array (long x, long *a, size_t *idx)
{
    long tmp[MAXDIG] = {0};
    int i = 0;

    digits2array_rev (x, tmp, idx);     /* fill array with digits (reversed) */

    for (i = 0; i < *idx; i++)          /* reverse to correct order */
        a[*idx - 1 - i] = tmp[i];
}

Output/Results

$ ./bin/digits2array

 array:

   ar[ 0] : 2
   ar[ 1] : 5
   ar[ 2] : 4
   ar[ 3] : 6
   ar[ 4] : 4
   ar[ 5] : 8
   ar[ 6] : 7
   ar[ 7] : 8
   ar[ 8] : 4
   ar[ 9] : 5
   ar[10] : 4

32-bit Safe Version (using long long)

On 32-bit OS's overflow would still occur. Changing the types to long long (8-bit int on x86), allows the program to operate on x86 without issue.

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

#define MAXDIG 32

void digits2array (long long x, long long *a, size_t *idx);
long long digits2array_rev (long long x, long long *a, size_t *i);

int main (void) {

    long long n = 25464878454;
    long long ar[MAXDIG] = {0};
    size_t idx = 0;
    int i = 0;

    digits2array (n, ar, &idx);    /* convert n to array    */

    printf ("\n array:\n\n");

    for (i = 0; i < idx; i++)       /* output results       */
        printf ("   ar[%2d] : %lld\n", i, ar[i]);

    return 0;
}

/* converts x to array of digits in a (reverse order) */
long long digits2array_rev (long long x, long long *a, size_t *i) 
{
    if (x < 10) {
        a[(*i)++] = x;
        return x;
    }

    a[(*i)++] = x % 10;

    return digits2array_rev (x / 10, a, i);
}

/* helper function to reverse results of digits2array_rev */
void digits2array (long long x, long long *a, size_t *idx)
{
    long long tmp[MAXDIG] = {0};
    int i = 0;

    digits2array_rev (x, tmp, idx);     /* fill array with digits (reversed) */

    for (i = 0; i < *idx; i++)          /* reverse to correct order */
        a[*idx - 1 - i] = tmp[i];
}

64/32-bit Version w/Preprocessor Directives

You can accomplish the same thing for x86, while preserving the original types for x86_64 through the use of preprocessor directives. (understanding that there is actually no storage benefit -- long (8-bit on x86_64), long long (8-bit on x86)).

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

#if defined(__LP64__) || defined(_LP64)
# define BUILD_64   1
#endif

#define MAXDIG 32

#ifdef BUILD_64
void digits2array (long x, long *a, size_t *idx);
int digits2array_rev (long x, long *a, size_t *i);
#else
void digits2array (long long x, long long *a, size_t *idx);
long long digits2array_rev (long long x, long long *a, size_t *i);
#endif

int main (void) {

#ifdef BUILD_64
    long n = 25464878454;
    long ar[MAXDIG] = {0};
#else
    long long n = 25464878454;
    long long ar[MAXDIG] = {0};
#endif
    size_t idx = 0;
    int i = 0;

    digits2array (n, ar, &idx);    /* convert n to array    */

    printf ("\n array:\n\n");

    for (i = 0; i < idx; i++)       /* output results       */
#ifdef BUILD_64
        printf ("   ar[%2d] : %ld\n", i, ar[i]);
#else
        printf ("   ar[%2d] : %lld\n", i, ar[i]);
#endif

    return 0;
}

/* converts x to array of digits in a (reverse order) */
#ifdef BUILD_64
int digits2array_rev (long x, long *a, size_t *i)
#else
long long digits2array_rev (long long x, long long *a, size_t *i)
#endif
{
    if (x < 10) {
        a[(*i)++] = x;
        return x;
    }

    a[(*i)++] = x % 10;

    return digits2array_rev (x / 10, a, i);
}

/* helper function to reverse results of digits2array_rev */
#ifdef BUILD_64
void digits2array (long x, long *a, size_t *idx)
{
    long tmp[MAXDIG] = {0};
#else
void digits2array (long long x, long long *a, size_t *idx)
{
    long long tmp[MAXDIG] = {0};
#endif
    int i = 0;

    digits2array_rev (x, tmp, idx);     /* fill array with digits (reversed) */

    for (i = 0; i < *idx; i++)          /* reverse to correct order */
        a[*idx - 1 - i] = tmp[i];
}

Are you using the exact data types? I just I just copied/pasted and got the exact same results. What are you running this on? Hold on, you must be running on a 32-bit box. Give me a bit and I'll update it.
I was thinking, one way to improve the efficiency of your code, would be to use a normal increment until you hit the upper limit of 25464878454, then convert it to an array using this code, then proceed with the BigNum scheme that increments the array. That would save you 25464878454 function calls/branches to the BigNum scheme when it is not necessary.

Collectives™ on Stack Overflow

Incrementing result as integer array digits in C

2 Answers 2

4 Comments

32-bit Safe Version (using long long)

64/32-bit Version w/Preprocessor Directives

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

32-bit Safe Version (using long long)

64/32-bit Version w/Preprocessor Directives

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related