Iterative calculation of large powers of a number by digits?

Question

Mathematics

It is necessary to calculate a large power of a number and at the same time it is necessary to obtain all the digits of the result. For example 3^1000.
The initial data (power and base) are given as integers, and the result must be placed in an array.
I managed to do it only by sequential multiplication of numbers and carry control, but this algorithm has a lot of iterations.

#include <stdio.h>
int main() {
    int e,i,m;
    int a = 23; //base
    int b = 100; //power
    int b1 = b;
    int c[1000] = {1,10};//result
    do{ e = 0;
        i = 0;
        while (c[i]<10) {
            m = c[i]*a+e;
            c[i++] = m%10;
            e = m/10;
            }
         while (e>0) {
            c[i++] = e%10;
            e/=10;
            }
        c[i]=10;
        } while (--b);
    printf("Digit count %d\n%d^%d=\n",i,a,b1);
    do {printf("%d",c[i-1]);} while (--i);
    return 0;
}

Is it possible to optimize the algorithm by mathematical methods?

Answer 1

There is a non-algorithmic way to speed up your decision - store not one number in each cell of the array - but several. In fact, perform calculations in the number system 10000 instead of 10. Or even 1000000000 - but then you need to do temporary calculations (multiplication) in int64_t so that there is no overflow.
Still, when displaying such a number, it is necessary to display leading zeros for all cells, except for the oldest one.
There is also an algorithmic way - but it is more complicated. There is an algorithm for binary exponentiation. The bottom line is that you square the number and multiply by the base if necessary.
But in this form, the algorithm will be even slower on large numbers. He will need O(log K) multiplications of large by large (which is done in O(L^2), where L is the length of the number, which will be O(K)). The final complexity of this algorithm will be O(K^2 log K).
When as your current solution does K short multiplications (Each is O(K)) - total O(k^2) operations. But if you apply fast multiplication of long numbers through the fast Fourier transform , then the final complexity will be O(K log ^ 2 K log log K). For power=100 you won't really feel the difference, it will even be slower, but at some 10000 it will already be noticeably faster.
I advise you to try the usual optimizations before taking on the Fourier transform.
Also, instead of storing the end of the number as a special value of 10, you should separately store the length of the number in some variable with a telling name (at least len). Then the code will be much more readable.

Answer 2

Fast exponentiation algorithms