Thread: Large numbers

  1. #1
    Registered User
    Join Date
    Apr 2007
    Location
    Sweden
    Posts
    12

    Large numbers

    I simply want a type that can hold something big enough to print the following value when the 'n' constant is equal to at least 100. Is this possible? If not, how can I get this value?

    Code:
    #include <iostream>
    
    const int n = 66;
    
    int main(void) {
        unsigned long long sum;
        
        for (int i=1;i<n;i++)
            sum*=(n-i);
        
        // this value is way too big if I use any 'n' value higher than 66
        // I can get as far as n=66 with an unsigned long long
        // it prints: 9 223 372 036 854 775 808 
        std::cout << sum;
    
        return 0;
    }
    Thankful for help..

  2. #2
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    To store numbers that large you'll need to use a library of some kind, such as GMP.

    [edit] Or you can implement it yourself, of course. You could represent a number as
    Code:
    char number[DIGITS];
    or something and do the multiplication by hand. [/edit]
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  3. #3
    Sanity is for the weak! beene's Avatar
    Join Date
    Jul 2006
    Posts
    321
    A type, i think an unsigned long long is as far as you can go (might be wrong).

  4. #4
    Registered User
    Join Date
    Apr 2007
    Location
    Sweden
    Posts
    12
    Quote Originally Posted by dwks View Post
    To store numbers that large you'll need to use a library of some kind, such as GMP.

    [edit] Or you can implement it yourself, of course. You could represent a number as
    Code:
    char number[DIGITS];
    or something and do the multiplication by hand. [/edit]
    Yes, I was actually thinking about doing that by separating it into two parts and somehow multiply them with eachother, but gave up on that idea after a while. That GMP library looks interesting though, do you know of any that works under Windows?

  5. #5
    Frequently Quite Prolix dwks's Avatar
    Join Date
    Apr 2005
    Location
    Canada
    Posts
    8,057
    Unless you want to use non-standard compiler extensions, you can't get a larger native type than an unsigned long long. Well, you could use a float or a double, but you wouldn't get exact values.

    You realize that sum is uninitialized in your code?
    Code:
        unsigned long long sum;
        
        for (int i=1;i<n;i++)
            sum*=(n-i);
    I'm assuming you set it to 1, right?

    [edit] GMP works under Windows as far as I know. I'll look into it. [/edit]
    [edit=2] Sure it works. http://www.google.ca/search?hl=en&q=...G=Search&meta= [/edit]
    dwk

    Seek and ye shall find. quaere et invenies.

    "Simplicity does not precede complexity, but follows it." -- Alan Perlis
    "Testing can only prove the presence of bugs, not their absence." -- Edsger Dijkstra
    "The only real mistake is the one from which we learn nothing." -- John Powell


    Other boards: DaniWeb, TPS
    Unofficial Wiki FAQ: cpwiki.sf.net

    My website: http://dwks.theprogrammingsite.com/
    Projects: codeform, xuni, atlantis, nort, etc.

  6. #6
    Registered User
    Join Date
    Apr 2007
    Location
    Sweden
    Posts
    12
    Quote Originally Posted by dwks View Post
    You realize that sum is uninitialized in your code?
    Oh, I forgot to add that back. I remade the program since I made a change to the original where I separated the sum into many parts. Strangely enough, it worked regardless :/


    [edit] GMP works under Windows as far as I know. I'll look into it. [/edit]
    [edit=2] Sure it works. http://www.google.ca/search?hl=en&q=...G=Search&meta= [/edit]
    Ok, thank you..

  7. #7
    Tropical Coder Darryl's Avatar
    Join Date
    Mar 2005
    Location
    Cayman Islands
    Posts
    503
    I have a large integer class I wrote a while back... Once I found gmp though, I stopped working on this, but for simple problems like you are doing, it works great. I've attached the source and you are welcomed to use it. If you need any help, you can email or pm me.


    usage:
    add these to your project.
    include the header

    change: unsigned long long sum;
    to: dbInt sum;

    compile and run
    Last edited by Darryl; 06-27-2007 at 08:02 PM.

  8. #8
    Kiss the monkey. CodeMonkey's Avatar
    Join Date
    Sep 2001
    Posts
    937
    base 256 arithmetic... yikes.
    "If you tell the truth, you don't have to remember anything"
    -Mark Twain

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Yikes indeed.

    I suggest taking a look at the bigint class on my website (link is in my sig; See the useful classes page). It works in basically the same way 64bit math operations are emulated on a 32-bit processor, using two-complement numbers of arbitrary size. Memory layout is identical to what you would expect from a native type of the specified size.
    It even has a factorial function built-in!

    Darryl, you might want to check it out too. I see you used Duff's Device in yours, btw.
    Last edited by iMalc; 06-28-2007 at 01:27 AM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  10. #10
    Tropical Coder Darryl's Avatar
    Join Date
    Mar 2005
    Location
    Cayman Islands
    Posts
    503
    Quote Originally Posted by CodeMonkey View Post
    base 256 arithmetic... yikes.
    I do not use base 256. Base 256 would internally store each digit as a byte, while my code stores each digit as a long long.

    ie base 10 = 10 values/digit
    base 256 = 256/digit
    mine using long long is
    base 18446744073709551615 = 18446744073709551615/digit


    Yikes indeed.

    .... Memory layout is identical to what you would expect from a native type of the specified size.
    ...

    Darryl, you might want to check it out too. I see you used Duff's Device in yours, btw.
    My memory layout is as efficient as using a native int64

    It's not the best approach I admit, but it's far better than the naive approach of storing digits as chars like most newbies would. I'll check your's out for curiousity sake but I use gmp now.

    Duff's Device was one of my many attempts at speeding up performance.

    I had tried Karatsuba multiplication but I never could get it working properly with a deque. In retrospect, a more c-like solution would have been speedier over my more c++ approach.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. how to deal wth large numbers
    By bvgsrs in forum C++ Programming
    Replies: 2
    Last Post: 06-18-2007, 06:16 AM
  2. Handling Large Numbers
    By Xzyx987X in forum C Programming
    Replies: 2
    Last Post: 05-03-2004, 02:33 PM
  3. Using really big numbers!
    By Machewy in forum C++ Programming
    Replies: 11
    Last Post: 02-26-2004, 10:49 AM
  4. Help needed with VERY large numbers.
    By jwarner in forum C++ Programming
    Replies: 4
    Last Post: 01-18-2004, 12:01 PM
  5. A (complex) question on numbers
    By Unregistered in forum C++ Programming
    Replies: 8
    Last Post: 02-03-2002, 06:38 PM