Huge Powers

[R.a.B.B.i.T]

I need to find a fairly effecient method of calculating huge powers of huge numbers (power and number both being out to 7 or 8 places).  C/C++/ASM/Java is preferred, although I could possibly do it in other languages.  Any idea on how I could go about doing this (without using an array)?

[Adron]

I need to find a fairly effecient method of calculating huge powers of huge numbers (power and number both being out to 7 or 8 places).  C/C++/ASM/Java is preferred, although I could possibly do it in other languages.  Any idea on how I could go about doing this (without using an array)?

If that's what you want to do, and you want an exact answer, you will be using an array or a ready-made library that uses an array. There is no native support for such numbers.

[R.a.B.B.i.T]

Gah, I was hoping it could be done without one, but if it can't, how should I start?

[Kp]

If you really care about speed, go with an assembly implementation (either find one or write one).  Unless you're writing something designed to do huge amounts of big number cryptography, I doubt you really need the extra speed up an assembly implementation can give you.  If you want to use something ready made, java.math.BigInteger or find one of the dozens of C/C++ libraries (vlong, OpenSSL's BN, GNU MP all come to mind).

[R.a.B.B.i.T]

Eh, it depends on the speed gain, but whatever.  My CS teacher asked me if I could create a [somewhat] quick program to do this.  He said he made one but it took hours to do one calculation (I think he raised x-billion to the power of x-trillion or something).  Thanks for the help

[Adron]

It definitely shouldn't take hours to do.

[Yoni]

Eh, it depends on the speed gain, but whatever. My CS teacher asked me if I could create a [somewhat] quick program to do this. He said he made one but it took hours to do one calculation (I think he raised x-billion to the power of x-trillion or something). Thanks for the help

Consider that the trivial algorithm for calculating a^b for very long a, b has time complexity O(b log a), while a slightly more thoughtful algorithm has time complexity O((log a)(log b)). (Logs are base 2 inside big O.) With the input numbers your teacher tried, the trivial algorithm requires an amount of operations in the hundreds of trillions, and the better one requires only several thousand ones.

Are you in high school or beyond? Either way (but especially in the former), CS teachers aren't always that bright

[R.a.B.B.i.T]

High school, but my teacher is one of those guys whose first programming language was punch cards

Also, I have no idea what O() is.

[K]

High school, but my teacher is one of those guys whose first programming language was punch cards

Also, I have no idea what O() is.

O(x) means the execution time of a function is less than or equal to x  It's used to describe the order of magnitude of a function.  For example:

Code Select Expand


void func(int n)
{
   for(i = 0; i < n; ++n)
      for(j = 0; j < n; ++n)
         feh;
}
has O(n^2), because the time taken to execute the function is (some constant for the instructions) times n squared.  A binary search has O(log_2(n)), because execution time is the logarithm base 2 of the number of nodes times some constant for the time of the instructions.

Big O Notation

[Yoni]

Here are both algorithms. I assume that b is a positive integer. If b is not a positive integer, something different needs to be done.

The slow, obvious one:

1) Multiply a by itself, b times. The result is a^b.

This one has time complexity O(b log a), because the multiplication by a is O(log a) and it is performed b times. Usually the multiplication is expressed as O(1) - but that is wrong, because a can be very long, and the multiplication requires an amount of work in linear correspondence with the amount of digits in "a".

The much faster one:

1) r = a            // r means "result"
2) While b > 1:

2.1) If b is even:
2.1.1) r = r*r
2.1.2) b = b/2

2.2) Else (if b is odd):
2.2.1) r = r*a
2.2.2) b = b - 1

3) return r

Take a few minutes and try to understand why that works and why it is much faster. This is the O((log a)(log b)) one and should not take hours on such small numbers as billions and trillions.

[R.a.B.B.i.T]

I've constructed a function based off of that, but it doesn't work (testing 5 to 3 and 5 to 4 both give 625, so something is wrong).

Code Select Expand

__int64 dealy(__int64 a, __int64 b)
{
    __int64 r = a;
    printf("Calculating,,,\n");

    while(b > 1)
    {
        if(b % 2 == 0)
        {
            r *= r;
            b /= 2;
        }else if(b % 2 == 1) {
            r *= a;
            b--;
        }
    }

    return r;
}

On top of that, using large numbers (such as 10000000 to 10000000) yeilds 0 because I'm not using a  type which has enough room for the values, so I don't exactly know what to use.

[Arta]

As an aside, using mod there will slow you down a lot. You can test for even/odd with a bitwise and:

Code Select Expand


if(n & 1)
  // odd
else
  // even


[Yoni]

Ack... The algorithm I illustrated was totally wrong. I tried to change it from recursive to iterative and didn't stop to make sure what I was doing was correct. Sorry

This (mixture of iterative and recursive) algorithm definitely works, with the same time complexity as I explained above (also logarithmic memory complexity now - I guess that can't be avoided):

Power(a, b):       // b is a positive integer

1. While b > 1:

1.1. If b is even:
1.1.1. a = a * a
1.1.2. b = b / 2

1.2. Else (if b is odd):
1.2.1. t = Power(a, (b-1)/2)
1.2.2. Return a*t*t

2. Return a

[R.a.B.B.i.T]

That is faring a little better, but even still, the returns top out at x ** 31 (2 ** 31 ==-2147483648, 31 ** 31 == -2010103841, and the such), they simply start rolling over to negatives then to 0.  Using unsigned __int64 does not resolve this issue, and I am still at a loss.

[Arta]

If you want to store bigger numbers than will fit into 64 bits, you need a bigint library. Kp posted some links earlier.