Add the digits in 2^1000

[carleye]

how do i add digits in 2^1000;
i need idea on how to do it?

[lastchance]

Do it in base 2.

[Chervil]

There may be 'clever' ways of handling this, involving something I've overlooked.

To find 2^n, you only need to add repeatedly:

    unsigned int x = 1;
    for (int i=0; i<10; ++i)
        x += x;

That should give 2^10 or 1024.

But you'd need a way to handle an integer having just a bit over 300 decimal digits. A simple 'brute-force' approach would be to write a very basic big-integer class. It wouldn't need lots of sophistication, just the ability to add. (Well, it wouldn't even need to be a class, since the requirements are so specific, it doesn't need the extra flexibility). (you might instead of add, just double or multiply by 2, whatever you prefer).

After that, processing the digits to get the sum is not hard.

[lastchance]

There was a similar problem involving factorials at
http://www.cplusplus.com/forum/beginner/219005/#msg1009519
You could easily modify it to do 2^N rather than Factorial(N).

[carleye]

Error: Interger const too large to fit

#include<iostream>
#include<math.h>
using namespace std;

int main()
{double z;
double  num=123456789123456789123456789;
double sum=0;


while(num>=1)
{
cout<<fixed;
cout<<num<<endl;
sum=sum+fmod(num,10);
num=num-fmod(num,10);
num=num/10;

}
cout<<sum<<endl;



}

[JLBorges]

> Error: Interger const too large to fit

Make it a floating point literal.
double num = 123456789123456789123456789.0 ;

Note that this may not give the results that you expect; floating point is an approximate representation of (a subset of) real numbers.

Try this:

#include <iostream>

int main()
{
    double num = 123456789123456789123456789.0 ;
    std::cout << std::fixed << num << '\n' ;

    num = 1111111111111111111111111111111111111111111111111111111111.0 ;
    std::cout << num << '\n' ;

    num = 9999999999999999999999999999999999999999999999999999999999999999999999.0 ;
    std::cout << num << '\n' ;
}

[lastchance]

You are going to need a monumental amount of precision.

107150860718626 ...huge number of digits ... 7205668069376
Number of digits = 302
Sum of digits = 1366

[jonnin]

there must be some clever way to do this without computing the value?

[lastchance]

there must be some clever way to do this without computing the value?

log₁₀( 2¹⁰⁰⁰ ) = 1000 log₁₀( 2 ) = 301.03
So you will need 302 digits to represent it.

Each digit lies between 0 and 9 - average 4.5. [Actually, the first must be 1 (from the fractional bit of the logarithm), whilst the last must be 6 (since the last number in powers of 2 cycles 2,4,8,6,2,4,8,6 ... repeating every 4). However, this is a minor difference, given the number of digits.]

302 * 4.5 gives 1359 as an approximation for the sum of digits. The true answer is 1366.

This is Project Euler Problem 16. if you ever do find a clever way of doing it without writing a few lines of code please let me know @Jonnin! I would be very interested.

[carleye]

i tried this but i am getting answer 1189

#include<iostream>
#include<math.h>
using namespace std;

int main()
{double z;
double  num=pow(2,1000);
num=num*1.0;
double sum=0;


while(num>=1)
{
cout<<fixed;
cout<<"here is the number "<<num<<endl;
sum=sum+fmod(num,10);
num=num-fmod(num,10);
num=num/10;

}
cout<<sum<<endl;



}

[mbozzi]

Good idea, however IEEE754 binary64 floating point values (i.e., most doubles) can not exactly represent integers greater than 2^53.
You're suffering rounding error.

[carleye]

So what should i do?

[Chervil]

What I suggested in the earlier post. Write your own code to handle a big integer. You might use a std::string or std::vector to store the 302 digits.

You could follow the suggestion from Lastchance and use some ideas from this thread:
http://www.cplusplus.com/forum/beginner/219005/#msg1009519


Or maybe, another recent post, consider the code from JLBorges here:
http://www.cplusplus.com/forum/general/218826/#msg1009107

[lastchance]

@carleye

Below is the factorial function that I linked to (and @Chervil also). I have spread it out and added more comments than I would usually do. The key thing is that it uses a vector<int> to store individual digits (starting from the "right") and it basically works by mimicking "long multiplication" - remember school before you were allowed a calculator!

This one uses recursion, but that's not vital: you could use a loop.

You obviously don't need a factorial ... but, in principle, you only need to make minor changes to THREE lines:
(1) The end of the recursion for the factorial is 1! = 1 - you could use either 2⁰=1 or 2¹ = 2 (your choice) - adjust line 18
(2) The recursion for the factorial is n! = n * (n-1)! - you will need 2ⁿ = 2 * 2^n-1 - adjust line 30
(3) You want 2¹⁰⁰⁰, not 2¹⁰⁰ - adjust line 44

Cosmetically, it would then make sense to rename Factorial to PowerOf2 or something.


This is by no means the only way of doing the problem.
- you could use a loop rather than recursion;
- vector<int> is quite profligate, using 4 bytes for each digit; you could use vector<short>, vector<char> or string
- you could do the problem by repeated long addition (@Chervil's original suggestion) rather than long multiplication; I only prefer the latter because it makes it easier to generalise to powers of other numbers;
- you could shortcut the number of multiplies; e.g. 2¹⁰⁰⁰ = (2¹⁰)¹⁰⁰ = 1024¹⁰⁰
- you could (with more work) write a "proper" high-precision integer class in binary (good luck!)

#include <iostream>
#include <vector>
#include <numeric>      // for accumulate
using namespace std;


//*******************************************************************
// Uses recursion: n! = n * (n-1)!                                  *
//   i.e.         Factorial(n) = n * Factorial(n-1)                 *
// with end of recursion    Factorial(1) = 1                        *
//                                                                  *
// Because the number is too large for a normal integer, the digits *
// of the result are returned (in reverse order) in a vector<int>   *
//*******************************************************************

vector<int> Factorial( int n )                        
{
   if ( n == 1 ) return vector<int>{ 1 };        // End of the recursion: Factorial(1) = 1

   vector<int> result;                           // Will store, and eventually return, the answer.
   vector<int> last = Factorial( n - 1 );        // Recursive call for previous value, Factorial(n-1)

   int size = last.size();                       // Number of digits in Factorial(n-1).
                                                 //    With normal long multiplication, each will be multiplied by n in turn
   int i = 0;                                    // i will be the index of the digit (i=0 holds ones, i=1 holds tens, i=2 holds hundreds etc.)
   int carry = 0;                                // Any 'carry' into the next tens column for multiplication; obviously 0 to start.

   while ( i < size || carry > 0 )               // i < size makes sure each digit is multiplied by n
   {                                             //    Any carry > 0 goes into the next column if necessary
      if ( i < size ) carry += n * last[i];      // Multiplies the digit in last[i] by n, and adds to any existing carry (which may be 0)
      result.push_back( carry % 10 );            // Done this digit multiply, so put in result
      carry /= 10;                               // Go into the next tens column (e.g 16 would give 6 carry 10, or add 1 to next column)
      i++;                                       // Move to next digit
   }
   return result;                                // Returns the vector<int> representing the factorial
}


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


int main()
{
   vector<int> F = Factorial( 100 );             // Call the function and put the result in a vector<int>

   for ( int j = F.size() - 1; j >= 0; j-- ) cout << F[j];     // Write the result (note: digits were stored in reverse order)

   cout << "\nNumber of digits = " << F.size() << '\n';                         // Number of digits is just the number of elements in this vector<int>
   cout << "Sum of digits = " << accumulate( F.begin(), F.end(), 0 ) << '\n';   // Add digits with std::accumulate()
                                                                                //    (or you could write your own function to sum them)
}

[48T7M4Gy]

#include <iostream>

int main()
{
    const int LIMIT = 400;
    int n[LIMIT] = {0};
    int temp, carryover = 0, remainder = 0, sum = 0;
    
    n[0] = 1;
    
    for (int k = 0; k < 1000; k++)
    {
        for (int i = 0; i < LIMIT; i++)
        {
            temp = 2 * n[i] + carryover;
            
            carryover = temp/10;
            remainder = temp % 10;
            
            n[i] = remainder;
        }
    }
    
    bool first_non_zero = false;
    int count = 1;
    
    for(int j = LIMIT - 1; j >= 0; j--)
    {
        if(n[j] == 0 && !first_non_zero)
            std::cout << ' ';
        else
        {
            first_non_zero = true;
            std::cout << n[j];
            if(count % 50 == 0)
                std::cout << '\n';
            count++;
        }
        
        sum += n[j];
    }
    
    std::cout << std::endl;
    std::cout << "Answer: " << sum << '\n';
    
    return 0;
}

10715086071862673209484250490600018105614048117055
33607443750388370351051124936122493198378815695858
12759467291755314682518714528569231404359845775746
98574803934567774824230985421074605062371141877954
18215304647498358194126739876755916554394607706291
45711964776865421676604298316526243868372056680693
76
Answer: 1366
Program ended with exit code: 0

[dhayden]

there must be some clever way to do this without computing the value?

See one algorithm here:
http://www.eng.utah.edu/~nmcdonal/Tutorials/BCDTutorial/BCDConversion.html

[lastchance]

See one algorithm here:
http://www.eng.utah.edu/~nmcdonal/Tutorials/BCDTutorial/BCDConversion.html

Hmm. That was hard work. The only easy part was the binary representation of 2^1000.

#include <iostream>
#include <string>
#include <vector>
using namespace std;

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

struct BCD{ int b[4]; };                                                      // binary digits (in reverse order: lowest value first)

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

int BCDtoDec( int *b ){ return b[0] + 2 * b[1] + 4 * b[2] + 8 * b[3]; }

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

void Add3( int *b  )                                                           // add 3 to a binary
{                                                                              // (assumes no array overflow)
   *b += 3;
   while ( *b > 1 )
   {
      *(b+1) += *b / 2;
      *b %= 2;
      b++;
   }
}

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

vector<BCD> binaryToBCD( const string &s )                                     // s should hold a binary string
{                                                                              // returns the BCD digits (lowest first)
   int slen = s.size();

   int size = slen;
   vector<int> b( size, 0 );                                                   // binary as a vector<int>
   for ( int i = 0; i < slen; i++ ) if ( s[i] == '1' ) b[size-1-i] = 1;        // note reversal of order

   for ( int shift = 0; shift < slen; shift++ )                                // successive shifts
   {
      // Check all current groups of 4; if greater than or equal to 5 then add 3
      for ( int p = slen; p < size; p += 4 ) if ( BCDtoDec( b.data() + p ) >= 5 ) Add3( b.data() + p );

      // Shift across
      if ( b[size - 1] == 1 ) b.insert( b.end(), { 1, 0, 0, 0 } );             // if we need a new group
      for ( int i = size - 1; i > 0; i-- ) b[i] = b[i-1];                      // shift the rest
      size = b.size();
   }

   // Group the BCD digits
   int p = slen;
   vector<BCD> bcd;
   while ( p < size ) { bcd.push_back( { b[p], b[p+1], b[p+2], b[p+3] } );   p += 4; }

   return bcd;
}

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

int main()
{
   string s = '1' + string( 1000, '0' );                    // original binary - as a string

   vector<BCD> bcd = binaryToBCD( s );                      // BCD digits (lowest value first)

   int sum = 0;
   for ( int i = bcd.size() - 1; i >= 0; i-- )
   {
      int digit = BCDtoDec( bcd[i].b );
      cout << digit;
      sum += digit;
   }
   cout << "\nSum of digits = " << sum;
}

10715086071862673 ... lots of digits ... 4386837205668069376
Sum of digits = 1366

I guess that if all you want to do is sum the digits then you can cut it down to the following code.

#include <iostream>
#include <vector>
using namespace std;

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

int BCDtoDec( int *b ){ return b[0] + 2 * b[1] + 4 * b[2] + 8 * b[3]; }

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

void Add3( int *b  )                                                           // add 3 to a binary
{                                                                              // (assumes no array overflow)
   *b += 3;
   while ( *b > 1 )
   {
      *(b+1) += *b / 2;
      *b %= 2;
      b++;
   }
}

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

int main()
{
   int slen = 1001, size = slen;
   vector<int> b( size, 0 );                                                   // binary as a vector<int>
   b[size-1] = 1;

   for ( int shift = 0; shift < slen; shift++ )                                // successive shifts
   {
      // Check all current groups of 4; if greater than or equal to 5 then add 3
      for ( int p = slen; p < size; p += 4 ) if ( BCDtoDec( b.data() + p ) >= 5 ) Add3( b.data() + p );

      // Shift across
      if ( b[size - 1] == 1 ) b.insert( b.end(), { 1, 0, 0, 0 } );             // if we need a new group
      for ( int i = size - 1; i > 0; i-- ) b[i] = b[i-1];                      // shift the rest
      size = b.size();
   }

   int p = slen, sum = 0;
   while ( p < size ) { sum += BCDtoDec( b.data() + p );   p += 4; }
   cout << "Sum of digits = " << sum;
}

Sum of digits = 1366