Old problem, but still in my mind

few years ago, i was asked to solve a "simple" c++ problem. The problem is: output the result of 3^9999 in c++. The trap is in the size of the resulting number, it is gigantic, so there should be some kind of trick, the last i remember that someone solved it by placing the answer inside the array... But i couldn't get it, please help me with this one (don't suggest any internal libraries)
I'd try and figure out something with strings, basically anything with 'infinite' length
Last edited on
I said before:
You can try the pow function if the number is to large to store in any regular data type.

I've never used it my self, and I'm not to sure how it works, but if you read about it you might find it useful.

And please note that I'm not a hundred percent sure if this function does what I think it does.


EDIT::

Now I tested the pow function. Did not give the result I'd expected...
I did:
1
2
3
4
5
6
7
8
#include <stdio.h>
#include <math.h>

int main ()
{
  printf ("3 ^ 9999 = %lf\n", pow (7,9999));
  return 0;
}

And got:
3 ^ 9999 = 1.#INF00


Guess pow doesn't give us a solution to the problem. Or at least not this way =)
Last edited on
Normally you'd be using a library that allows you to manipulate large numbers. I use GNU MP:

1
2
3
4
5
6
7
8
#include <iostream>
#include <gmpxx.h>
int main()
{  
   mpz_class result;
   mpz_ui_pow_ui(result.get_mpz_t(), 3, 9999);
   std::cout << "3^9999 = " << result << '\n';
}


(by the way, boost.multiprecision finally passed review, so we'll have a near-standard way to do this in C++ shortly: http://lists.boost.org/boost-announce/2012/08/0359.php )
Last edited on
closed account (o3hC5Di1)
As you mention array, perhaps the number was actually stored as a c-string (char-array)?

It holds individual characters, like so:

1
2
3
4
5
6
7
8
char number[50]; //max number size of 50 digits
number[0] = 3;  //set initial number to three
char result[50];

for (int i=0; i<9999; i++)
{
    square(number);
}


Where the square function takes a reference to the number and multiplies it by its own.
This is done as you would do a multiplication on paper, multiplying every digit and using a variable to do carrying to the next number.

I know this is probably not the most optimal solution, but this is possibly what school teachers are looking for by giving this as a basic exercises.

All the best,
NwN
Topic archived. No new replies allowed.