Dealing with VEERRRYYYY big numbers

[hunkeelin]

Write your question here.

  let's say i design a function 

unsigned int foo(unsigned int n){
 blablablal;
}

 

If in main i call the function foo(12938498213749127389840) it will not work because the int is bigger than 2^31, changing to double or long won't work too because the number i put is just too big. So how can I deal with such a big number in the first place? Is there absolutely no way to do it?

[JLBorges]

Typically, one would use an arbitrary precision integer library.

Fortunately, mainstream C++ now has one, in Boost Multiprecision.
http://www.boost.org/doc/libs/1_55_0/libs/multiprecision/doc/html/index.html

#include <boost/multiprecision/cpp_int.hpp>
#include <iostream>

using bigint = boost::multiprecision::cpp_int ;

bigint factorial( bigint n ) { return n < 2 ? bigint(1) : n * factorial(n-1) ; }

int main()
{

    std::cout << factorial(81) << '\n' ;
}

http://coliru.stacked-crooked.com/a/85c971d121551294

[jidder]

can you not just keep putting long before int until its large enough ?

e.g
long long long long int

edit: actually i just tried this and gcc doesnt support more the two longs

[JLBorges]

See: http://en.cppreference.com/w/cpp/language/types

[hunkeelin]

Thanks.

Now, what if I want to do it in C? I thought of converting it to string since you can print string no matter how long it is then chunk by chunk eval it. For me I need to check whether the HUUUUGGGEE number is a palindrome.

[giblit]

if it's just checking if it's a palindrome you can do that easily with strings.

Put an iterator and the start and another at the end and compare them with each other while moving towards the middle.

[JLBorges]

> Now, what if I want to do it in C?
> I thought of converting it to string since you can print string no matter how long it is
> then chunk by chunk eval it.

We do not need to perform any numeric computations on the huge number. So we can just accept the individual digits of the number one by one as characters, and place them into a huge string.

The messy part in C would be the memory management of the huge string.

Something like this would be typical:

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

int main()
{
    size_t sz = 20 ;
    char* number = (char*)malloc(20) ;
    if( number == NULL ) return 1 ;

    puts( "please type in the number: " ) ;

    int c ;
    // skip over leading white space
    while( ( c = getchar() ) != EOF )
    {
        if( !isspace(c) )
        {
            ungetc( c, stdin ) ;
            break ;
        }
    }

    size_t pos = 0 ;
    // keep going till we hit EOF or a non-digit character is entered
    while( ( c = getchar() ) != EOF )
    {
        if( c == '\n' ) continue ; // new line, user wants to enter more digits,
                                    // go on to get the next digit

        if( !isdigit(c) ) break ; // a non-digit character is entered,
                                   // there are no more digits

        number[pos] = c ; // c holds a digit

        if( pos == sz-1 ) // if we have run out of space
        {
            // resize the buffer
            sz *= 2 ; // use a canonical doubling strategy

            // try to reallocate to the bigger buffer
            char* temp = (char*)realloc( number, sz ) ;
            if( temp == NULL )
            {
               free(number) ;
               return 1 ;
            }
            else number = temp ;
        }
        ++pos ;
    }

    number[pos] = 0 ; // null terminate

    printf( "The number is: %s\n", number ) ;

    // TODO: check if it is a palindrome

    // check if digit at positiion 0 is the same as digit at position pos-1,
    // check if digit at positiion 1 is the same as digit at position pos-2,
    // till the middle digit is reached

    // print out the result of the check


    free(number) ;
}

http://coliru.stacked-crooked.com/a/57265d03d17b28f2

[hunkeelin]

^ errrr I can't really understand the code. I see you create a buffer and iterate it as it goes, what about this.
Can you give me a simple example of a function that takes in A and output A?

unsigned int foo(unsigned int a)
{
??????? (return a;)
}

also regarding your answer, what if the size is better than 20? I see you set sz = 20 at the beginning of your code.
I dont' want to copy your code to finish my assignment without understanding anything. It haunt me sooner or later in the future.

[JLBorges]

> errrr I can't really understand the code

Have you been taught dynamic memory allocation in C? Have malloc(), realloc() and free() been mentioned?

If the answer to the above is 'no', then you have perhaps misunderstood the assignment that was given to you. For instance, an upper limit might have been placed on the number of digits.

If, instead, the answer to the question was 'yes', then read on.

> what if the size is better than 20?
> I see you set sz = 20 at the beginning of your code.

Look carefully at lines 36 to 49 of the code.

[hunkeelin]

^ Yes, in my lecture malloc and free is mentioned. But mentioned it is. Obviously I don't get it. I'm trying to create a function I mentioned above as step 1.

[JLBorges]

> ^ Yes, in my lecture malloc and free is mentioned. But mentioned it is.
> Obviously I don't get it

So, first try to get it. Before you try to write functions which use dynamically allocated memory.

There are a lot of tutorials about dynamically allocated buffers and how to grow them. For instance:
http://fydo.net/gamedev/dynamic-arrays
http://irccrew.org/~cras/security/howto/dynamic.html