Read input into a dynamic sized int?

Question

I need to read a huge number from the stdin, here is the code i have so far:

int main() {
    int x;
    int* n1;
    scanf("%d", &x); // I get the number of digits the integer will have

    n1 = malloc(x * sizeof(int)); // I resize the integer pointer
}

So my question is how can I read this possibly huge sized int from stdin?

Answer 1

the most reliable method of handling very large numbers is to use the 'bignum.c', which is available at: http://www3.cs.stonybrook.edu/~skiena/392/programs/bignum.c

the referenced code is a complete program,. but the functions and struct are free to use.

where is what you would find there:

/*  bignum.c
    Implementation of large integer arithmetic: addition, subtraction,
        multiplication, and division.

    begun: February 7, 2002
    by: Steven Skiena
*/

/*
Copyright 2003 by Steven S. Skiena; all rights reserved. 

Permission is granted for use in non-commerical applications
provided this copyright notice remains intact and unchanged.

This program appears in my book:

"Programming Challenges: The Programming Contest Training Manual"
by Steven Skiena and Miguel Revilla, Springer-Verlag, New York 2003.

See our website www.programming-challenges.com for additional information.

This book can be ordered from Amazon.com at

http://www.amazon.com/exec/obidos/ASIN/0387001638/thealgorithmrepo/

*/


#include <stdio.h>

#define MAXDIGITS   100     /* maximum length bignum */ 

#define PLUS        1       /* positive sign bit */
#define MINUS       -1      /* negative sign bit */

typedef struct {
        char digits[MAXDIGITS];         /* represent the number */
    int signbit;            /* 1 if positive, -1 if negative */ 
        int lastdigit;          /* index of high-order digit */
} bignum;


print_bignum(bignum *n)
{
    int i;

    if (n->signbit == MINUS) printf("- ");
    for (i=n->lastdigit; i>=0; i--)
        printf("%c",'0'+ n->digits[i]);

    printf("\n");
}

int_to_bignum(int s, bignum *n)
{
    int i;              /* counter */
    int t;              /* int to work with */

    if (s >= 0) n->signbit = PLUS;
    else n->signbit = MINUS;

    for (i=0; i<MAXDIGITS; i++) n->digits[i] = (char) 0;

    n->lastdigit = -1;

    t = abs(s);

    while (t > 0) {
        n->lastdigit ++;
        n->digits[ n->lastdigit ] = (t % 10);
        t = t / 10;
    }

    if (s == 0) n->lastdigit = 0;
}

initialize_bignum(bignum *n)
{
    int_to_bignum(0,n);
}


int max(int a, int b)
{
    if (a > b) return(a); else return(b);
}

/*  c = a +-/* b;   */

add_bignum(bignum *a, bignum *b, bignum *c)
{
    int carry;          /* carry digit */
    int i;              /* counter */

    initialize_bignum(c);

    if (a->signbit == b->signbit) c->signbit = a->signbit;
    else {
        if (a->signbit == MINUS) {
            a->signbit = PLUS;
            subtract_bignum(b,a,c);
            a->signbit = MINUS;
        } else {
                        b->signbit = PLUS;
                        subtract_bignum(a,b,c);
                        b->signbit = MINUS;
        }
        return;
    }

    c->lastdigit = max(a->lastdigit,b->lastdigit)+1;
    carry = 0;

    for (i=0; i<=(c->lastdigit); i++) {
        c->digits[i] = (char) (carry+a->digits[i]+b->digits[i]) % 10;
        carry = (carry + a->digits[i] + b->digits[i]) / 10;
    }

    zero_justify(c);
}


subtract_bignum(bignum *a, bignum *b, bignum *c)
{
    int borrow;         /* has anything been borrowed? */
    int v;              /* placeholder digit */
    int i;              /* counter */

    initialize_bignum(c);

    if ((a->signbit == MINUS) || (b->signbit == MINUS)) {
                b->signbit = -1 * b->signbit;
                add_bignum(a,b,c);
                b->signbit = -1 * b->signbit;
        return;
        }

    if (compare_bignum(a,b) == PLUS) {
        subtract_bignum(b,a,c);
        c->signbit = MINUS;
        return;
    }

        c->lastdigit = max(a->lastdigit,b->lastdigit);
        borrow = 0;

        for (i=0; i<=(c->lastdigit); i++) {
        v = (a->digits[i] - borrow - b->digits[i]);
        if (a->digits[i] > 0)
            borrow = 0;
        if (v < 0) {
            v = v + 10;
            borrow = 1;
        }

                c->digits[i] = (char) v % 10;
        }

    zero_justify(c);
}

compare_bignum(bignum *a, bignum *b)
{
    int i;              /* counter */

    if ((a->signbit == MINUS) && (b->signbit == PLUS)) return(PLUS);
    if ((a->signbit == PLUS) && (b->signbit == MINUS)) return(MINUS);

    if (b->lastdigit > a->lastdigit) return (PLUS * a->signbit);
    if (a->lastdigit > b->lastdigit) return (MINUS * a->signbit);

    for (i = a->lastdigit; i>=0; i--) {
        if (a->digits[i] > b->digits[i]) return(MINUS * a->signbit);
        if (b->digits[i] > a->digits[i]) return(PLUS * a->signbit);
    }

    return(0);
}

zero_justify(bignum *n)
{
    while ((n->lastdigit > 0) && (n->digits[ n->lastdigit ] == 0))
        n->lastdigit --;

        if ((n->lastdigit == 0) && (n->digits[0] == 0))
        n->signbit = PLUS;  /* hack to avoid -0 */
}


digit_shift(bignum *n, int d)       /* multiply n by 10^d */
{
    int i;              /* counter */

    if ((n->lastdigit == 0) && (n->digits[0] == 0)) return;

    for (i=n->lastdigit; i>=0; i--)
        n->digits[i+d] = n->digits[i];

    for (i=0; i<d; i++) n->digits[i] = 0;

    n->lastdigit = n->lastdigit + d;
}



multiply_bignum(bignum *a, bignum *b, bignum *c)
{
    bignum row;         /* represent shifted row */
    bignum tmp;         /* placeholder bignum */
    int i,j;            /* counters */

    initialize_bignum(c);

    row = *a;

    for (i=0; i<=b->lastdigit; i++) {
        for (j=1; j<=b->digits[i]; j++) {
            add_bignum(c,&row,&tmp);
            *c = tmp;
        }
        digit_shift(&row,1);
    }

    c->signbit = a->signbit * b->signbit;

    zero_justify(c);
}


divide_bignum(bignum *a, bignum *b, bignum *c)
{
        bignum row;                     /* represent shifted row */
        bignum tmp;                     /* placeholder bignum */
    int asign, bsign;       /* temporary signs */
        int i,j;                        /* counters */

    initialize_bignum(c);

    c->signbit = a->signbit * b->signbit;

    asign = a->signbit;
    bsign = b->signbit;

    a->signbit = PLUS;
        b->signbit = PLUS;

    initialize_bignum(&row);
    initialize_bignum(&tmp);

    c->lastdigit = a->lastdigit;

    for (i=a->lastdigit; i>=0; i--) {
        digit_shift(&row,1);
        row.digits[0] = a->digits[i];
        c->digits[i] = 0;
        while (compare_bignum(&row,b) != PLUS) {
            c->digits[i] ++;
            subtract_bignum(&row,b,&tmp);
            row = tmp;
        }
    }

    zero_justify(c);

    a->signbit = asign;
    b->signbit = bsign;
}



main()
{
    int a,b;
    bignum n1,n2,n3,zero;

    while (scanf("%d %d\n",&a,&b) != EOF) {
        printf("a = %d    b = %d\n",a,b);
        int_to_bignum(a,&n1);
        int_to_bignum(b,&n2);

        add_bignum(&n1,&n2,&n3);
        printf("addition -- ");
        print_bignum(&n3);

        printf("compare_bignum a ? b = %d\n",compare_bignum(&n1, &n2));

        subtract_bignum(&n1,&n2,&n3);
        printf("subtraction -- ");
        print_bignum(&n3);

                multiply_bignum(&n1,&n2,&n3);
        printf("multiplication -- ");
                print_bignum(&n3);

        int_to_bignum(0,&zero);
        if (compare_bignum(&zero, &n2) == 0)
            printf("division -- NaN \n");
                else {
            divide_bignum(&n1,&n2,&n3);
            printf("division -- ");
                    print_bignum(&n3);
        }
        printf("--------------------------\n");
    }
}

Answer 2

There is no such thing as a "dynamic sized int" in C. As others have suggested, depending on your use case, reading the number as a string might be what you want. (If you use scanf for this, beware of buffer overflows.)

If you need to do arithmetic on the number, you might wish to use an existing library such as libgmp for this to benefit from an existing solution to the problem. You could also re-implement libgmp's functionality yourself, but unless you're doing this as a learning exercise, there's little reason to.

Answer 3

The way you are designing it right now, you will have a pointer to int, in other words: an array of ints. The biggest integer type you can store you numbers in is long long (its size depends on the machine, on 64-bit machines it's generally 8 bytes).

You may also consider either storing the number in a string (after allocating a char*) or, as you wrote, in an array of ints, where each of the array elements would hold arbitrary number of digits (then I would suggest using getchar() and atoi() functions instead of scanf()).

Answer 4

int x;
int* n1;
int i;
scanf("%d", &x);

n1 = malloc(x * sizeof(int));

for(i = 0; i < x; ++i){
    scanf("%1d", &n1[i]);//Read (unsigned) one digit
}
for(i = 0; i < x; ++i){
    printf("%d", n1[i]);
}
puts("");