storing really large numbers like 100!

This is a discussion on storing really large numbers like 100! within the C++ Programming forums, part of the General Programming Boards category; 100! = 9.33262154 10^157 how would I store this number? I have thought about just putting it in a ...

  1. #1
    Registered User
    Join Date
    Aug 2005
    Posts
    266

    storing really large numbers like 100!

    100! = 9.33262154 10^157

    how would I store this number? I have thought about just putting it in a string.

    But lets say I want to compute the number myself by starting at 2 and then multiplying 3 ..followed by 4 all the way till i get to multiplying 100.

    I would have to store every intermediate step in a string and somehow 'multiply' these strings?

    anyone know of any solution to this?
    should I be factoring the numbers?

    Thanks a lot!

    o yea please, standard library
    Last edited by rodrigorules; 01-23-2010 at 09:36 AM.

  2. #2
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    Yes, the only way to do it using only the standard library, is, I believe, to use an "infinite"-length datatype, such as a "string" or (dynamic) "char[]". You can certainly use this to create a class that can store arbitrarily-large numbers and perform basic operations on them. Ive always wanted to do something like this myself, for fun, but have never got around to doing so. It certainly is interesting.

    If you arent up to creating your own class, I would suggest to use some very well known "large number" libraries. Again, I dont think there is anything in the STDLIB, but there are some very good and well known ones. I dont have any on the top of my head, but a simple search will give you the answers. One thing to ask yourself is "do I have to limit myself to STDLIB?", when you decide which method (implement your own vs. reuse).

  3. #3
    Registered User
    Join Date
    Aug 2005
    Posts
    266
    I guess i will try to do some sort of multiplication with carry over loop and see how that works out.

    now thinking about it, it can't be too difficult. (i hope)

    edit: now thinking about it..i am also going to have to make a function for addition before i can handle multiplication.
    Last edited by rodrigorules; 01-23-2010 at 10:26 AM.

  4. #4
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,485
    Well so long as you know how to do it on paper, then doing the same using strings is no more difficult.

    Not the highest performance to be sure, but it'll work well enough.

    Plus, if you make a decent class out of it, you can tinker with the innards later on.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  5. #5
    Registered User
    Join Date
    Aug 2005
    Posts
    266
    Tried making my addition for strings ... lots of struggle thus far

    and dev c++ isn't really helping with its debugger needing some debugging of its own.


    any ideas? the program always returns 1 (from the 2nd to last statement)


    Code:
    string addition(string num1,string num2)
    {
         string total = "";
         int numSize;
         int carry=0;
         
         //I want the larger digit number on the top row, just as I would on paper.
         // SWAP
         if(num1.length() < num2.length())
         {
             string temp = num1;
             num1 = num2;
             num2 = temp;  
         }
         numSize = num1.length();
         
         //add zeros so they now match in length...so I can simply go from right to left adding cols.
         while(numSize != num2.length())
         {
                num2= "0" + num2;
         }
         
         for(int i = numSize-1; i >= 0; --i)
         {
                        int sum;
    
                        //Here I attempt to add characters together and resolve an integer
                        if(sum = (int)num2[i]+(int)num1[i]+carry > 9)
                        {
                            //when adding, the carry is at most 1.
                            carry = 1;
                            total=(convertInt(sum - 10))+total; 
                        }     
                        else
                        {
                            carry=0;
                            total = convertInt(sum) + total;
    
                        }       
         }
         (carry == 1) ? total = "1" + total : 0;
         return total;
    }
    (convertInt accepts an int and returns it as a string)
    Last edited by rodrigorules; 01-23-2010 at 12:07 PM.

  6. #6
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,485
    Well if you just input the strings, then you have '0' to '9', not 0 to 9

    The actual numeric value of each character is
    ( num[i] - '0' )

    and you do +'0' when you're done with the maths on each character.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  7. #7
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,485
    > and dev c++ isn't really helping with its debugger needing some debugging of its own.
    Dev-c++ is an old and dead project.
    code::blocks is it's successor.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  8. #8
    Registered User
    Join Date
    Aug 2005
    Posts
    266
    Quote Originally Posted by Salem View Post
    > and dev c++ isn't really helping with its debugger needing some debugging of its own.
    Dev-c++ is an old and dead project.
    code::blocks is it's successor.
    yea , i remember it being better

    downloading vs2008 from my school now

    edit: actually i think ill try code blocks first

  9. #9
    Registered User
    Join Date
    Aug 2005
    Posts
    266
    I found out the error

    if(sum = (int)num2[i]+(int)num1[i]+carry > 9)
    the > has precedence over the = ...so sum was always 0 or 1

    new line with +'0'
    if((sum = (( num2[i]-'0' )+( num1[i]-'0' ))+ carry) > 9)
    thank you salem.
    Last edited by rodrigorules; 01-23-2010 at 01:33 PM.

  10. #10
    Registered User
    Join Date
    Aug 2005
    Posts
    266
    I wrote a multiplication now.
    edit: nvm it works with humungo numbers.

    Code:
    string mult(string num1,string num2)
    {
         int carry;  
       
        //make sure num1 is longer or equal to num2.
         if(num1.length() < num2.length())
         {
             string temp = num1;
             num1 = num2;
             num2 = temp;
         }
    
         int num2Size=num2.length();
         int num1Size=num1.length();
    
         string* additionLines = new string[num2Size];
    
         for(int i = num2Size-1; i >= 0; --i)
         {
             carry=0;
             additionLines[i]="";
             for(int j = num1Size-1; j >=0; --j)
             {
                
                int product;
                if( (product = ((num2[i]-'0')*(num1[j]-'0')) + carry) > 9 )
                {
                    carry = product / 10;
                    additionLines[i] = convertInt(product % 10) + additionLines[i];
                }
                else
                {
                    carry = 0;
                    additionLines[i] = convertInt(product) + additionLines[i];
                }
             }
    
             if(carry != 0)
                additionLines[i] = convertInt(carry) + additionLines[i];
    
             if(i < num2Size - 1)
                for(int k=i; k < num2Size - 1; ++k)
                    additionLines[i] = additionLines[i] + "0";
         }
    
         string totalSum="0";
    
         for(int i = 0; i < num2Size; ++i)
         {
             totalSum = addition(totalSum,additionLines[i]);
         }
         delete[] additionLines;
    
    return totalSum;
    }
    Last edited by rodrigorules; 01-23-2010 at 04:36 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Logical errors with seach function
    By Taka in forum C Programming
    Replies: 4
    Last Post: 09-18-2006, 05:20 AM
  2. How to return/use VERY LARGE numbers?
    By 99atlantic in forum C++ Programming
    Replies: 8
    Last Post: 04-05-2005, 10:13 PM
  3. Representing a Large Integer with an Array
    By random_accident in forum C Programming
    Replies: 3
    Last Post: 03-03-2005, 07:56 PM
  4. Representing a Large Integer with an Array
    By random_accident in forum C++ Programming
    Replies: 3
    Last Post: 03-03-2005, 11:23 AM
  5. Large Numbers
    By Hypercase in forum C++ Programming
    Replies: 1
    Last Post: 10-02-2004, 06:56 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21