calculating 2^1000 and its sum of the digits

zaahm18 (63)

Hi, i have an exercise from eulers 9A where I have to compute 2^1000 and find the sum of its integer. How do I do it?

My first intake is this:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
 
// this is the pseudocode copied from my function (defined):

// I want to store numbers in an array with mod of 0x7fffffffffffffff
mutable deque<unsigned long long> vec;
void power2(int x)
    {
        vec.push_back(0);
        for (int i = 1; i <= x; i += 64)
            vec.push_back(0);
        int i = 1;
        unsigned long long mod = 0x7fffffffffffffff;
        while (i < 64 && i < x)
        {
            vec[1] = (unsigned long long)pow(2, i);
            i++;
        }
        if (i >= 64)
        {
            int carry;
            vec[2] = vec[1] % mod;
            vec[1] /= mod;
            for (; i < x; i++)
            {
                vec[floor(i / 64)] = (unsigned long long)pow(2, i%64);
                if (vec[floor(i / 64)] == mod)
                {
                    carry = vec[floor(i / 64)] % mod;
                    vec[floor(i / 64)] /= mod;
                    while (carry > 0)
                    {
                        vec[floor(i / 64) + 1] = carry;
                        carry--;
                    }
                }
            }
        }
    }

// THis is how I sum the digits:
    void digitsum(int x = 1)
    {
        if (!vec.empty())
        {
            for (int i = 1; i < vec.size(); i++)
            {
                while (vec[i] != 0)
                {
                    vec[0] += vec[i] % 10;
                    vec[i] /= 10;
                }
            }
        }
        else
        {
            vec.clear();
            vec.push_back(0);
            while (x != 0)
            {
                vec[0] += (x % 10);
                x /= 10;
            }
        }
    }
// Calling function.
    void power2sum(int x)
    {
        vec.clear();
        power2(x);
        digitsum(x);
    }


I've tried to debug but I couldn't find the solution to calculate big integers.
lastchance (6980)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
 
#include <iostream>
#include <iomanip>
#include <vector>
using namespace std;

const int MOD = 1000000000;
const int WMOD = 9;



unsigned long long sumDigits( unsigned long long n ) { return n < 10 ? n : sumDigits( n / 10 ) + n % 10; }


//=====================================================================


class BigInt
{
public:
   vector<unsigned long long> digits;       // digits stored in REVERSE order;
   BigInt( unsigned long long n = 0 );      // construct from integer
};

//------------------

BigInt::BigInt( unsigned long long n )
{
   digits.clear();
   if ( n == 0 )
   {
      digits.push_back( 0 );
   }
   else
   {
      while ( n )
      {
         digits.push_back( n % MOD );
         n /= MOD;
      }
   }
}

//------------------

BigInt operator * ( const BigInt &a, const BigInt &b )
{
   BigInt result = 0;

   int asize = a.digits.size();
   int bsize = b.digits.size();

   for ( int i = 0; i < asize; i++ )        // Multiply by the ith digit of a and i tens
   {
      unsigned long long carry = 0;
      for ( int j = 0; j < bsize || carry > 0; j++ )
      {
         if ( i + j < result.digits.size() ) carry += result.digits[i+j];
         if ( j < bsize ) carry += a.digits[i] * b.digits[j];
         int digit = carry % MOD;
         carry /= MOD;
         if ( i + j < result.digits.size() ) result.digits[i+j] = digit;
         else                                result.digits.push_back( digit );
      }
   }
   return result;
}

//------------------

ostream &operator << ( ostream &out, const BigInt &a )
{
   out << a.digits.back();
   for ( int i = a.digits.size() - 2; i >= 0; i-- ) out << setw( WMOD ) << setfill( '0' ) << a.digits[i];
   return out;
}

//======================================================================

int main()
{
   BigInt Two50 = 1ull << 50;
   BigInt result = Two50;
   for ( int n = 2; n <= 20; n++ ) result = result * Two50;

   unsigned long long sumd = 0;
   for ( auto d : result.digits ) sumd += sumDigits( d );

   cout << "2^1000 = " << result << '\n';
   cout << "The sum of its digits = " << sumd << '\n';
}


2^1000 = 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376
The sum of its digits = 1366

Ganado (6811)
lastchance (6980)
Cheers Ganado! I obviously had lots of fun the last time I had a go at that challenge, too!
zaahm18 (63)
BOI, i wasn't expected that....
Topic archived. No new replies allowed.