Итерационное вычисление больших степеней числа по цифрам?

Question

[Игорь Шабанов]

Необходимо вычислять большую степень числа и при этом необходимо получить все цифры результата. Например 3^1000.
Исходные данные (степень и основание) задаются как целые числа, а результат нужно уложить в массив.
У меня получилось сделать только последовательным перемножением чисел и контролем переноса, но данный алгоритм имеет очень много итераций.

#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;
}

Есть ли возможность математическими методами оптимизировать алгоритм?

Comments

[Wataru]

Оберните код в тег code (кнопка </> в редакторе). Иначе вопрос удалят.

[Игорь Шабанов]

Спасибо

Answer 1

[Wataru]

Есть неалгоритмический способ ускорить ваше решение - храните в каждой ячейке массива не одну цифру - а несколько. Фактически, проводите вычисления в системе счисления 10000, вместо 10. Или даже 1000000000 - но тогда надо временные вычисления (умножение) делать в int64_t, чтобы переполнения не было.

Еше, при выводе такого числа надо выводить ведущие нули для всех ячеек, кроме самой старшей.

Есть и алгоритмический способ - но он сложнее. Есть алгоритм бинарного возведения в степень. Суть в том, что вы возводите число в квадрат и домножаете на базу если надо.

Но в таком виде алгоритм будет даже медленнее на больших числах. Ему потребуется O(log K) умножений большого на большое (которое делается за O(L^2), где L - длина числа, которая будет O(K)). Итоговая сложность этого алгорима будет O(K^2 log K).

Когда как ваше текущее решение делает K коротких умножений (Каждое - O(K)) - всего O(k^2) операций. Но если применять быстрое умножение длинных чисел через быстрое преобразование Фурье то итоговая сложность будет O(K log^2 K log log K). Для power=100 особо вы разницы не почуствуете, даже медленнее будет, но вот при каких-нибудь 10000 уже будет заметно быстрее.

Советую попробовать обычные оптимизации, прежде чем браться за преобразование фурье.

Еще, вместо хранения конца числа в виде особого значения 10 - вам стоит отдельно хранить длину числа в какой-то переменной с говорящим названием (хотя бы len). Тогда код будет сильно читабельнее.

Comments

[Rsa97]

Ему потребуется O(log K) умножений большого на большое (которое делается за O(L^2), где L - длина числа, которая будет O(K)).

Умножение также можно свести к бинарному алгоритму. Нет принципиальной разницы между
xⁿ = x * x * ... * x
и
x * n = x + x + ... + x
Таким образом умножение мы сводим к операциям *2 (то есть сложение с собой) и +x

[Wataru]

Rsa97, Опишите свой алгоритм на бумажке и попробуйте подсчитать, сколько там операций. Все те же самые O(L^2) вы и получите. Тот логарифм, который вы сюда впихиваете - он от числа X - и будет как раз длиной L.

Не зря умные дядьки 60 лет голову ломают над алгоритмами быстрого умножения длинных чисел.

Answer 2

[Rsa97]

Алгоритмы быстрого возведения в степень

Comments

[Wataru]

Важное замечание - этот алгоритм будет быстрее наивного, только если использовать быстрое преобразование фурье для собственно умножения чисел.

Ну, или если вам ответ только по модулю нужен.