2^1000 result too large!

This is a discussion on 2^1000 result too large! within the C++ Programming forums, part of the General Programming Boards category; So I've got a challenge to get the result of 2^1000, then add each digit of that result together. The ...

  1. #1
    Registered User
    Join Date
    May 2008
    Location
    Australia
    Posts
    230

    2^1000 result too large!

    So I've got a challenge to get the result of 2^1000, then add each digit of that result together. The only problem is, the maximum size integer you can use in C++ is a 64 bit integer, which can store a maximum value of 2^64. So, to be honest, I have NO idea how this is going to be possible (But there HAS to be a way, 100% guaranteed)... I'd like some hints towards a solution if possible (that is if anyone knows ;o). So yeah, some hints would be nice! Thanks

    P.s I'm sure a few of you know where this challenge is coming from
    Last edited by pobri19; 09-28-2008 at 08:29 AM.
    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.

  2. #2
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Unless there is some mathematical answer you might use (or write your own minimal) large number class. For example I wrote my own small Large class for this and the following user program:

    Code:
    int main()
    {
        Large num("1");
        for (int i = 0; i != 1000; ++i) {
            num.multiply_by_two();
        }
        std::cout << num << '\n' << num.sum_digits() << '\n';
    }
    And got the result (hope it is correct, seemed to work ok for smaller numbers):

    10715086071862673209484250490600018105614048117055 33607443750388370351051124936122493198378815695858 12759467291755314682518714528569231404359845775746 98574803934567774824230985421074605062371141877954 18215304647498358194126739876755916554394607706291 45711964776865421676604298316526243868372056680693 76
    1366
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  3. #3
    Registered User
    Join Date
    May 2008
    Location
    Australia
    Posts
    230
    Wow. Cheers for that man! That's the right answer Very nice. Oh but how did you make the class haha, did you do it in chunks and store the result in a string? I don't really know how it works, but I thought it would be harder than that.
    Last edited by pobri19; 09-28-2008 at 09:04 AM.
    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.

  4. #4
    The larch
    Join Date
    May 2006
    Posts
    3,573
    The class declaration looks like this:
    Code:
    class Large
    {
        std::vector<char> buffer;
    public:
        Large(const std::string& s_num);
        void multiply_by_two();
        unsigned sum_digits() const;
        friend std::ostream& operator<<( std::ostream& os, const Large& num);
    };
    So each digit is represented as a char (well, actually a char in range 0 - 9, and the constructor and the output routine take care of adding/substracting '0'. I also stored the digits in reverse order internally to make multiplying easier but this is just an implementation detail).

    The only hard thing is to multiply by two. But you do know how to do this on paper? (multiply each digit by 2 and carry over 1 if the result is more than 9.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  5. #5
    Registered User
    Join Date
    May 2008
    Location
    Australia
    Posts
    230
    Man, you're a genius Thanks!
    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.

  6. #6
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    The best big number class is GMP.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  7. #7
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    is this a project Euler problem? seems like it would be

  8. #8
    Budding Synth Programmer samGwilliam's Avatar
    Join Date
    Feb 2002
    Location
    Trefforest
    Posts
    368
    Quote Originally Posted by anon View Post
    Unless there is some mathematical answer you might use (or write your own minimal) large number class. For example I wrote my own small Large class for this and the following user program:

    Code:
    int main()
    {
        Large num("1");
        for (int i = 0; i != 1000; ++i) {
            num.multiply_by_two();
        }
        std::cout << num << '\n' << num.sum_digits() << '\n';
    }
    And got the result (hope it is correct, seemed to work ok for smaller numbers):

    10715086071862673209484250490600018105614048117055 33607443750388370351051124936122493198378815695858 12759467291755314682518714528569231404359845775746 98574803934567774824230985421074605062371141877954 18215304647498358194126739876755916554394607706291 45711964776865421676604298316526243868372056680693 76
    1366
    That's pretty cool.

    Did you store the number as a byte per digit and perform the carrying manually or something?
    MSVC++ 6.0

  9. #9
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by samGwilliam View Post
    That's pretty cool.

    Did you store the number as a byte per digit and perform the carrying manually or something?
    I think that's implied in the answer anon gave.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  10. #10
    Registered User
    Join Date
    Jun 2005
    Posts
    6,259
    Quote Originally Posted by anon View Post
    Unless there is some mathematical answer you might use (or write your own minimal) large number class.
    There are mathematical results that make it possible to get an answer without computing the actual value of 2^1000. Have a look here.

  11. #11
    Registered User
    Join Date
    Jan 2008
    Posts
    287
    Just so you're aware, DigitSum arithmetic as described on that page is vastly different from calculating the sum of the digits of 2^1000. For starters, the DigitSum of any number results in a single digit answer. That should have been a huge clue right there....

  12. #12
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,634
    There are mathematical results that make it possible to get an answer without computing the actual value of 2^1000.
    Unfortunately, the challenge requires one to compute 2^1000, and only then sum its digits.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Large scale crawler with C/C++???
    By joshskender in forum C++ Programming
    Replies: 12
    Last Post: 10-12-2006, 05:13 AM
  2. parse truly large numbers to binary
    By alch in forum C Programming
    Replies: 3
    Last Post: 07-20-2006, 01:39 PM
  3. Large String Comparisions...
    By alvifarooq in forum C++ Programming
    Replies: 10
    Last Post: 05-30-2005, 03:54 AM
  4. Computing Large Values
    By swbluto in forum C++ Programming
    Replies: 8
    Last Post: 04-07-2005, 03:04 AM
  5. Return Statement
    By Daveo in forum C Programming
    Replies: 21
    Last Post: 11-09-2004, 04:14 AM

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