[Karel-Lodewijk]

CTphpnwb's suggestion is excellent if you want a binary number because 2^10000 is a nice round number in binary. But if you want a decimal result it might not be so easy. In decimal 2^10000 is not so round, in fact it is:

Spoiler

19950631168807583848837421626835850838234968318861924548520089498529438830221946631919961684036194597899331129423209124271556491349413781117593785932096323957855730046793794526765246551266059895520550086918193311542508608460618104685509074866089624888090489894838009253941633257850621568309473902556912388065225096643874441046759871626985453222868538161694315775629640762836880760732228535091641476183956381458969463899410840960536267821064621427333394036525565649530603142680234969400335934316651459297773279665775606172582031407994198179607378245683762280037302885487251900834464581454650557929601414833921615734588139257095379769119277800826957735674444123062018757836325502728323789270710373802866393031428133241401624195671690574061419654342324638801248856147305207431992259611796250130992860241708340807605932320161268492288496255841312844061536738951487114256315111089745514203313820202931640957596464756010405845841566072044962867016515061920631004186422275908670900574606417856951911456055068251250406007519842261898059237118054444788072906395242548339221982707404473162376760846613033778706039803413197133493654622700563169937455508241780972810983291314403571877524768509857276937926433221599399876886660808368837838027643282775172273657572744784112294389733810861607423253291974813120197604178281965697475898164531258434135959862784130128185406283476649088690521047580882615823961985770122407044330583075869039319604603404973156583208672105913300903752823415539745394397715257455290510212310947321610753474825740775273986348298498340756937955646638621874569499279016572103701364433135817214311791398222983845847334440270964182851005072927748364550578634501100852987812389473928699540834346158807043959118985815145779177143619698728131459483783202081474982171858011389071228250905826817436220577475921417653715687725614904582904992461028630081535583308130101987675856234343538955409175623400844887526162643568648833519463720377293240094456246923254350400678027273837755376406726898636241037491410966718557050759098100246789880178271925953381282421954028302759408448955014676668389697996886241636313376393903373455801407636741877711055384225739499110186468219696581651485130494222369947714763069155468217682876200362777257723781365331611196811280792669481887201298643660768551639860534602297871557517947385246369446923087894265948217008051120322365496288169035739121368338393591756418733850510970271613915439590991598154654417336311656936031122249937969999226781732358023111862644575299135758175008199839236284615249881088960232244362173771618086357015468484058622329792853875623486556440536962622018963571028812361567512543338303270029097668650568557157505516727518899194129711337690149916181315171544007728650573189557450920330185304847113818315407324053319038462084036421763703911550639789000742853672196280903477974533320468368795868580237952218629120080742819551317948157624448298518461509704888027274721574688131594750409732115080498190455803416826949787141316063210686391511681774304792596709376

If you want an exact solution, I would use a bignum library.

If you want an approximation and the result no longer fits in a double/log double. Then you could do something like:

we want 2^10000

If the base number was 10, a power could be calculated by just shifting the number, so we rewrite the exponent in a part that'll make the base 10 (log2(10)) and the rest.

So, we rewrite

2^10000
= 10 ^ (10000/log2(10))
= 10 ^ 3010.3
= 10 ^ 0.3 * 10 ^ 3010

So we have reduced our huge exponential to a reasonable small one (10^0.3) and a shift operation.

= 1.99526231... * 10^3010

This result is not exact because 10^0.3 can't be calculated exactly (with a double)

This post has been edited by Karel-Lodewijk: 02 March 2012 - 02:22 PM

[Karel-Lodewijk]

CTphpnwb, on 02 March 2012 - 09:07 PM, said:

Base10 = Binary
2^0 = 1
2^1 = 10
2^2 = 100
2^3 = 1000

See a pattern?
2^n = 1 in the n binary position, where in this case 0 <= n <= 10000
Now you need to store it. That's where the array comes in. Next, you need to calculate the base10 equivalent and display it.

The point is that it doesn't solve anything. Now you have a really big binary number and now you got to convert it to a decimal numer. So how do we do that.

10....00 to base 10
= 0 * 2^0 + 0 * 2^1 + ... + 0*2^9999 + 1*2^10000
= 2 ^ 10000

That didn't sove much did it. The base conversion requires you to be able to calculate a really big exponential.

This post has been edited by Karel-Lodewijk: 02 March 2012 - 02:52 PM

[Itchigon]

CTphpnwb, on 02 March 2012 - 02:07 PM, said:

Base10 = Binary
2^0 = 1
2^1 = 10
2^2 = 100
2^3 = 1000

See a pattern?
2^n = 1 in the n binary position, where in this case 0 <= n <= 10000
Now you need to store it. That's where the array comes in. Next, you need to calculate the base10 equivalent and display it.

Thanks for your help so far, I feel bad having to ask for more help in explaining this.

I'm having issues with storing the number in an array. I understand the pattern, so for example 2^10000 = 1 followed by 10,000 zero's. But I don't get how to do this in code form? Is there some form of psuedocode you could give me just for populating the array and then I could work out how to convert into Base10?

Karel, what I want is basically:

1. User enters a number x (between 1-10000)
2. Program calculates 2 pow x
3. Program adds all digits of 2 pow x together. E.g. 2 pow 4 = 16, 1+6 = 7.
4. Print this result to the user

In regards to your explanation, do I need to keep precision to work out part 3. or could I work this out by using your method?

[Karel-Lodewijk]

Itchigon, on 02 March 2012 - 09:48 PM, said:

Karel, what I want is basically:

1. User enters a number x (between 1-10000)
2. Program calculates 2 pow x
3. Program adds all digits of 2 pow x together. E.g. 2 pow 4 = 16, 1+6 = 7.
4. Print this result to the user

In regards to your explanation, do I need to keep precision to work out part 3. or could I work this out by using your method?

Nope you pretty much need full precision. Like I said, use a bignum library. You could do it by hand but it would require a bit of work.

[Itchigon]

Karel-Lodewijk, on 02 March 2012 - 03:01 PM, said:

Itchigon, on 02 March 2012 - 09:48 PM, said:

Karel, what I want is basically:

1. User enters a number x (between 1-10000)
2. Program calculates 2 pow x
3. Program adds all digits of 2 pow x together. E.g. 2 pow 4 = 16, 1+6 = 7.
4. Print this result to the user

In regards to your explanation, do I need to keep precision to work out part 3. or could I work this out by using your method?

Nope you pretty much need full precision. Like I said, use a bignum library. You could do it by hand but it would require a bit of work.

I'm not allowed to use a bignum library as the assignment says so.

[CTphpnwb]

Storing the number is the easy part. Outputting the decimal equivalent is harder.

using namespace std;
#include <iostream>

void store2n(unsigned long b[], int n) {
	int byte_num = n/64;
	int position = n % 64;
	int temp = 1;
	temp = temp<<position;
	b[byte_num] = temp;
}

int main (int argc, char * const argv[]) {
	unsigned long big[157] = {0};
	store2n(big, 70);
	for (int i = 156; i >= 0; i--) {
		cout << big[i] << "_";
	}
	cout << endl <<"Note that this number is 64 * 2^64 since we're seeing the decimal value store in each array element, not the actual decimal number." << endl;
	
	cout << 10000.0/(sizeof(unsigned long)*8) << endl;
	
	return 0;
}

[Karel-Lodewijk]

I think the simplest would be using a vector of unsigned char and do a x2 each time, pushing new digits as they are needed. i.e.:

{2} * 2
{4} * 2
{8} * 2 //push a 1
{6,1} * 2
{2,3}
...

This post has been edited by Karel-Lodewijk: 02 March 2012 - 03:21 PM

[jimblumberg]

Since your base will always be 2 wouldn't this be easier using shifting? After all pow(2,16) is the same as 1<<16. And as long as you only shift ((numeric_limits<unsigned type>::digits) - 1) maximum you will stay in within the size of your unsigned type value. To do a higher number of shifts start using an array of your maximum shifted values. For example for 100 (1.26765e+30) (using 32 bit unsigned value) shift 1<<31 1<<31 1<<31 1<<7 ( 2147483648 * 2147483648 * 2147483648 * 128 = 1.26765e+30) Also remember with "Big" floating point numbers you will also start seeing errors because of the number of significant digits of your floating point number.


Jim

[Itchigon]

Karel that could be done using arrays too right? I'm only using C.

[CTphpnwb]

jimblumberg, on 02 March 2012 - 06:25 PM, said:

Since your base will always be 2 wouldn't this be easier using shifting?

That's what I did. After determining which element to use and how many bits are left over to shift:

    temp = temp<<position;

[jimblumberg]

Could you explain your magic numbers? Why are you passing 70 to your program? Why the 64 in your function, and why (sizeof(unsigned long)*8) in main? What output does your program produce?

It produces this on my machine:

Quote

0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_
0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0
_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_
0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_0_64_0_

Note that this number is 64 * 2^64 since we're seeing the decimal value store in each array element, not the actual decimal number.
312.5

Is that correct?

Jim

This post has been edited by jimblumberg: 02 March 2012 - 04:29 PM

[Itchigon]

Yea i'm not sure what those numbers actually mean, I also get the same output Jim.

[CTphpnwb]

It's just an example: 2^70 = (2^8) * (2^64) = 64 * 2^64
The first element of the array holds 0 through 2^64 -1
The second holds (0 through 2^64 - 1) * 2^64
and so on...

The last line shows how many elements you need in the array to represent 2^10000 on your system. Mine shows: 156.25 because there are 8 bytes in a long int on my system.
10000.0/(8*8) = 156.25
(8 bytes * 8 bits per byte)

Jim's system is using 4 bytes in a long int so he'd need 313 elements in the array:
10000.0/(4*8) = 312.5

If you use part of a byte you have to use the whole thing, so my code uses 157 for the size of big[]:

	unsigned long big[157] = {0};

Jim's would need to be 313 and each element would hold 2^32 possible values instead of 2^64 so the math would be a little different.

This post has been edited by CTphpnwb: 02 March 2012 - 06:11 PM

[jimblumberg]

I still don't really understand your code. I don't see why you need such a large array, You should be able to hold 2^10000 with an array size of 14 (actually with this size you can hold a number of 2^16383). This is also the largest value that a long double will hold on my machine when using pow(2.0,16283) which is 5.9487e4931 in decimal.

Using your program as a base, this is what I came up with.

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

void store2n(std::vector<int>& b, int n)
{
   // Determine the size of the vector needed to hold this power.
   int k = 0;
   while((1<<k++) < n);
   // Need one less bit space.
   b.resize(k-1);

   for(int i = b.size()-1; i >= 0; --i)
   {  // Fill in the proper bit positions.
      if(n - (1<<i) >= 0)
      {
         b[i] = 1;
         n = n - (1<<i);
      }
   }
}

int getTotal(const std::vector<int>& big)
{
   int total = 0;
   for (int i = big.size()-1; i >= 0; --i)
      if(big[i])
         total += (1<<i);
   return(total);
}

std::vector<int> add2n(std::vector<int>& a, std::vector<int>& B)/>
{
   std::vector<int> temp((a.size() + b.size()),0);
   store2n(temp,getTotal(a) + getTotal(B)/>);

   return(temp);
}

int main ()
{
   int howBig;

   std::vector<int> big;
   std::vector<int> small;
   std::vector<int> medium;

   int smallP = 30;
   int mediumP = 40;

   store2n(small,smallP);
   store2n(medium,mediumP);
   big = add2n(small,medium);

   // 2^16383 is the largest number that can be held in a large double on my machine.


   howBig = smallP+mediumP;

   cout << "2 to the " << howBig << " power. \n\n";

   cout << "In Decimal is " << pow(2.0,(long double)(howBig)) << "\n\n";

   cout << "Which is ";
   for (int i = big.size()-1; i >= 0; i--) {
      cout << big[i] << " ";
   }
   cout << " in binary \n\n";
   int total = 0;
   cout << "Which is ";

   for (int i = big.size()-1; i >= 0; --i) {
      if(big[i])
      {
         total += (1<<i);
         big[i] = (1<<i);
         cout << big[i];
         cout << " + ";
      }
      else
      {
         cout << 0;
         if( i > 0) cout << " + ";
      }
   }
   cout << " = " << total << endl << endl;
   cout << "In Decimal is " << pow(2.0,(long double)(total)) << "\n\n";

   return 0;
}

And this is the output that this program produces:

Quote

2 to the 70 power.

In Decimal is 1.18059e+21

Which is 1 0 0 0 1 1 0 in binary

Which is 64 + 0 + 0 + 0 + 4 + 2 + 0 + = 70

In Decimal is 1.18059e+21

And if I change the program to produce 2^10,000 I get this output:

Quote

2 to the 10000 power.

In Decimal is 1.99506e+3010

Which is 1 0 0 1 1 1 0 0 0 1 0 0 0 0 in binary

Which is 8192 + 0 + 0 + 1024 + 512 + 256 + 0 + 0 + 0 + 16 + 0 + 0 + 0 + 0 + = 10000

In Decimal is 1.99506e+3010

Jim

[CTphpnwb]

Well, I'm not sure why you're using doubles at all. Sure, you can represent the number with them, but not accurately. Try adding 2^10000 and 2^1. Your result will be the same as 2^10000. If you want to store the number down to the least significant digit you have to use an array of integers. That leaves you with:

2^0 requires 1 bit => 1
2^1 requires 2 bits => 10
2^2 requires 3 bits => 100
...
2^10 requires 11 bits => 10000000000

So, 2^N requires N+1 bits and 2^10000 requires 10001 bits.
10001/64(bits per long int) = 156.265625 long integer values, meaning we'd need to use an array with 157 integers to store this value, assuming we didn't use a sign bit.