8

I'm trying to calculate a large number, which requires BigInteger.Pow(), but I need the exponent to also be a BigInteger and not int.

i.e.

BigInteger.Pow(BigInteger)

How can I achieve this?

EDIT: I came up with an answer. User dog helped me to achieve this. 

public BigInteger Pow(BigInteger value, BigInteger exponent)
{
    BigInteger originalValue = value;
    while (exponent-- > 1)
        value = BigInteger.Multiply(value, originalValue);
    return value;
}
John Saunders
  • 160,644
  • 26
  • 247
  • 397
avi12
  • 157
  • 1
  • 2
  • 8

5 Answers5

9

Just from the aspect of general maths, this doesn't make sense. That's why it's not implemented.

Think of this example: Your BigInteger number is 2 and you need to potentiate it by 1024. This means that the result is a 1 KB number (2^1024). Now imagine you take int.MaxValue: Then, your number will consume 2 GB of memory already. Using a BigInteger as an exponent would yield a number beyond memory capacity!

If your application requires numbers in this scale, where the number itself is too large for your memory, you probably want a solution that stores the number and the exponent separately, but that's something I can only speculate about since it's not part of your question.

If your your issue is that your exponent variable is a BigInteger, you can just cast it to int:

BigInteger.Pow(bigInteger, (int)exponent); // exponent is BigInteger
bytecode77
  • 14,163
  • 30
  • 110
  • 141
  • 1
    And of course if he has a `BigInteger` value that just happens to be less than ~2 billion he can always cast it down to an `Int32` before passing it to `pow`, if that's his concern. – Servy May 13 '15 at 20:35
  • The number is too large to use int. Example of a large number to be calculated: [Googleplex](http://en.wikipedia.org/wiki/Googleplex) – avi12 May 14 '15 at 03:20
  • 2
    Googlepex can not be stored in memory as a number. It would consume memory beyond imagination (10^100 bytes). What do you need those numbers for and why can't handle them "theoretically" rather than actually storing the number? – bytecode77 May 14 '15 at 10:33
  • 1
    Googol is 10^100. But Googolplex is 10^10^100. Therefore, it cannot simply be calculated. – avi12 May 14 '15 at 14:00
  • 2
    Well, you answered your own question then ;) – bytecode77 May 14 '15 at 16:08
  • `The result is a 1KB number`, `Your number will consume 2 GB of memory`: not quite. They will consume 1Kb and 2 Gb (notice the lowercase b which stands for bits, not bytes). That's still a lot, but 1/8 the memory. – Bip901 Feb 22 '22 at 08:05
5

Pow(2, int64.MaxValue) requires 1,152,921 terabytes just to hold the number, for a sense of scale. But here's the function anyways, in case you have a really nice computer.

  static BigInteger Pow(BigInteger a, BigInteger b) {
     BigInteger total = 1;
     while (b > int.MaxValue) {
        b -= int.MaxValue ;
        total = total * BigInteger.Pow(a, int.MaxValue);
     }
     total =  total * BigInteger.Pow(a, (int)b);
     return total;
  }
dog
  • 1,307
  • 13
  • 10
  • 2
    You're funny :D Maybe in a thousand years, someone will stumble upon this post and laugh at us having just a few gigs of RAM... – bytecode77 May 13 '15 at 21:16
  • When I try to use this method, I get `Exception of type 'System.OutOfMemoryException' was thrown.` Can I perform the action without throwing an exception? – avi12 May 14 '15 at 14:10
  • A computer with 1 bit of memory can store a number from 0 to 1, a computer with 100 bits of memory can store a number from 0 to (2^100)-1. The biggest number you could compute is about Pow(2,bits available). So the function above will not work if you don't have enough memory, hence the 'System.OutOfMemoryException' exception. – dog May 14 '15 at 17:00
  • 2
    1,152,921 terabytes should be enough for anyone. – codekaizen Sep 29 '15 at 23:17
1

As others have pointed out, raising something to a power higher than the capacity of int is bad news. However, assuming you're aware of this and are just being given your exponent in the form of a BigInteger, you can just cast to an int and proceed on your merry way:

BigInteger.Pow(myBigInt, (int)myExponent);

or, even better,

try
{
    BigInteger.Pow(myBigInt, (int)myExponent);
}
catch (OverflowException)
{
    // Do error handling and stuff.
}
Eric Dand
  • 1,106
  • 13
  • 37
1

For me the solution was to use the function BigInteger.ModPow(BigInteger value, BigInteger exponent, BigInteger modulus) because I needed to do a mod afterwards anyway.

The function calculates a given BigInteger to the power of another BigInteger and calculates the modulo with a third BitInteger. Although it will still take a good amount of CPU Power it can be evaluated because the function already knows about the modulo and therefore can save a ton of memory.

Hope this might help some with the same question.

Edit: Is available since .Net Framework 4.0 and is in .Net Standard 1.1 and upwards.

Marc
  • 105
  • 7
0

I came up with: 

public BigInteger Pow(BigInteger value, BigInteger exponent)
{
    BigInteger originalValue = value;
    while (exponent-- > 1)
        value = BigInteger.Multiply(value, originalValue);
    return value;
}
avi12
  • 157
  • 1
  • 2
  • 8