Computational Mathematics – How to Handle Big Powers on Big Numbers

algorithmsbig numberscomputational mathematicsexponentiation

I'm struggling with the way to calculate an expression like $n^{915937897123891}$ where $n$ could be really any number between 1 and the power itself.

I'm trying to program (C#) this and therefor performance is key.

I tried

 for(i <= 915937897123891)
     value = n * value;

But that is obviously very very slow.

I wander if it is possible to achieve this using bitwise operators.
Also I would like to know what steps I could take to improve the way the calculate this.
Additionally I would also like to know how this should be solved without a calculator, just with (much?) paper and pen.

Feel free to ask for more information.

Thanks in advance,
Mixxiphoid

Best Answer

The general method using exponentiation by squaring.

In some situations, the time analysis is fully determined by realizing that the direct algorithm uses $\Theta(n)$ multiplies, but the square-and-multiply algorithm only uses $\Theta(\log n)$ multiplies. However, numbers grow large in this calculation, and the cost of multiplication becomes significant and must be accounted for.

Let $N$ be the exponent and $M$ be the bit size of $n$. The direct algorithm has to, in its $k$-th multiply, compute an $M \times kM$ product (that is, the product of an $n$ bit number by a $kn$-bit number). Using high school multiplication, this costs $kM^2$, and the overall cost is

$$ \sum_{k=1}^{N-1} k M^2 \approx \frac{1}{2} N^2 M^2 $$

With $N$ as large as it is, that's a lot of work! Also, because $n$ is so small, the high school multiplication algorithm is essentially the only algorithm that can be used to compute the products -- the faster multiplication algorithms I mention below can't be used to speed things up.

In the repeated squaring approach, the largest squaring is $NM/2 \times NM/2$. The next largest is $NM/4 \times NM/4$, and so forth. The total cost of the squarings is

$$ \sum_{i=1}^{\log_2 N} \left(2^{-i} N M \right)^2 \approx \sum_{i=1}^{\infty} N^2 M^2 2^{-2i} = \frac{1}{3} N^2 M^2$$

Similarly, the worst cost case for the multiplications done is that it does one $M \times NM$ multiply, one $M \times NM/2$ multiply, and so forth, which add up to

$$ \sum_{i=0}^{\infty} M (M N) 2^{-i} = 2 M^2 N $$

The total cost is then in the same ballpark either way, and there are several other factors at work that would decide which is faster.

However, when both factors are large, there are better multiplication algorithms than the high school multiplication algorithm. For the best ones, multiplication can be done in essentially linear time (really, in $\Theta(n \log n \log \log n)$ time), in which case the cost of the squarings would add up to something closer to $MN$ time (really, $MN \log(MN) \log \log(MN)$), which is much, much, much faster.

I don't know if BigInteger uses the best algorithms for large numbers. But it certainly uses something at least as good as Karatsuba, in which case the cost of the squarings adds up to something in the vicinity of $(NM)^{1.585}$.

Related Question