Как я могу вычислить 2 ^ n для больших n?

Question

Я пытаюсь написать программу, которая принимает число n в качестве входных данных и выводит результат 2 в степень n. Проблема в том, что n может быть очень большим (до 100 000). По сути, я пытаюсь вычислить pow(2, n); для очень больших чисел.

Я думаю, что способ сделать это - сохранить цифры в массиве, поскольку нет встроенного числового типа, который мог бы хранить значения, которые являются такими большими.

Цифры представлены в десятичном формате (основание 10).

Я использую C, а не C ++, поэтому я не могу использовать векторы STL и другие контейнеры C ++. Я также не могу использовать внешние библиотеки, такие как GMP . Мне нужно реализовать алгоритм вручную в чистом C.

Answer 1

Проблема не в том, чтобы вычислить 2 в старшую степень, а в том, чтобы преобразовать это число в десятичное представление:

• Представим большие числа с массивами 32-разрядных целых чисел без знака.
• Вычисление 2 ⁿ так же просто, как установка одного бита.
• Преобразование в двоичную форму можно выполнить путем многократного деления этого числа на 1000000000 с одновременным получением 9 цифр.

Вот простая, но быстрая реализация:

#include <stdint.h>
#include <stdio.h>

void print_2_pow_n(int n) {
    int i, j, blen = n / 32 + 1, dlen = n / 29 + 1;
    uint32_t bin[blen], dec[dlen];
    uint64_t num;

    for (i = 0; i < blen; i++)
        bin[i] = 0;
    bin[n / 32] = (uint32_t)1 << (n % 32);

    for (j = 0; blen > 0; ) {
        for (num = 0, i = blen; i-- > 0;) {
            num = (num << 32) | bin[i];
            bin[i] = num / 1000000000;
            num = num % 1000000000;
        }
        dec[j++] = (uint32_t)num;
        while (blen > 0 && bin[blen - 1] == 0)
            blen--;
    }
    printf("2^%d = %u", n, dec[--j]);
    while (j-- > 0)
        printf("%09u", dec[j]);
    printf("\n");
}

int main() {
    int i;
    for (i = 0; i <= 100; i += 5)
        print_2_pow_n(i);
    print_2_pow_n(1000);
    print_2_pow_n(10000);
    print_2_pow_n(100000);
    return 0;
}

Вывод:

2^0 = 1
2^5 = 32
2^10 = 1024
2^15 = 32768
2^20 = 1048576
2^25 = 33554432
2^30 = 1073741824
2^35 = 34359738368
2^40 = 1099511627776
2^45 = 35184372088832
2^50 = 1125899906842624
2^55 = 36028797018963968
2^60 = 1152921504606846976
2^65 = 36893488147419103232
2^70 = 1180591620717411303424
2^75 = 37778931862957161709568
2^80 = 1208925819614629174706176
2^85 = 38685626227668133590597632
2^90 = 1237940039285380274899124224
2^95 = 39614081257132168796771975168
2^100 = 1267650600228229401496703205376
2^1000 = 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376
2^10000 = 1995063116880758384883742<...>91511681774304792596709376
2^100000 = 9990020930143845079440327<...>97025155304734389883109376

2 ¹⁰⁰⁰⁰ имеет 30103 цифр, что точноfloor(100000 * log10(2)).На моем старом ноутбуке он выполняется за 33 миллисекунды.

Answer 2

Просто создайте битовый массив и установите n-й бит. Затем разделите на 10, как если бы битовый массив имел младший порядок номер и распечатать остатки в обратном порядке, чтобы получить основную-10 представление вашей n-й степени два.

Эта быстрая программа, представленная ниже, делает это, и она дает мне те же результаты, что и bc, так что я думаю, что это работает. Процедура печати может использовать некоторые настройки.

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

uint_least32_t div32(size_t N, uint_least32_t Z[/*N*/], uint_least32_t X[/*N*/], uint_least32_t Y)
{
    uint_least64_t carry; size_t i;
    for(carry=0, i = N-1; i!=-1; i--)
        carry = (carry << 32) + X[i], Z[i] = carry/Y, carry %= Y;
    return carry;
}

void pr10(uint_least32_t *X, size_t N)
{
    /*very quick and dirty; based on recursion*/
    uint_least32_t rem=0;
    if(!X[N?N-1:0]) return;
    rem = div32(N,X,X,10);
    while(N && !X[N-1]) N--;
    pr10(X,N);
    putchar(rem+'0');
}
int main(int C, char **V)
{
    uint_least32_t exp = atoi(V[1]);
    size_t nrcells = exp/32+1;
    uint_least32_t *pow  = calloc(sizeof(uint_least32_t),nrcells);
    if(!pow) return perror(0),1;
    else pow[exp/32] = UINT32_C(1)<<(exp%32);
    pr10(pow,nrcells);

}

Пример выполнения:

$ ./a.out 100
1267650600228229401496703205376

Answer 3

Поскольку в исходной постановке задачи не указана база вывода, здесь приведена реализация шутки:

#include <stdio.h>

void print_2_pow_n(int n) {
    printf("2^%d = 0x%d%.*d\n", n, 1 << (n % 4), n / 4, 0);
}

int main() {
    int i;
    for (i = 0; i < 16; i++)
        print_2_pow_n(i);
    print_2_pow_n(100);
    print_2_pow_n(100000);
    return 0;
}

Вывод:

2^0 = 0x1
2^1 = 0x2
2^2 = 0x4
2^3 = 0x8
2^4 = 0x10
2^5 = 0x20
2^6 = 0x40
2^7 = 0x80
2^8 = 0x100
2^9 = 0x200
2^10 = 0x400
2^11 = 0x800
2^12 = 0x1000
2^13 = 0x2000
2^14 = 0x4000
2^15 = 0x8000
2^100 = 0x10000000000000000000000000
2^100000 = 0x10...<0 repeated 24998 times>...0

Answer 4

Мне не удалось найти решение с логарифмической сложностью (возведение в квадрат по квадратам), но Мне удалось написать наивную реализацию со сложностью времени O (noOfDigits * pow), noOfDigits за 2 ^ n будет n * log10 (2) +1;

Я проверил ответ только по первым нескольким цифрам https://www.mathsisfun.com/calculator-precision.html, и он кажется правильным.

#include <stdio.h>
#include <math.h>
//MAX is no of digits in 2^1000000
#define MAX 30103
int a[MAX];
int n;
void ipow(int base, int exp,int maxdigits)
{
    a[0]=1;
    for (;exp>0;exp--){
            int b=0;
            for(int i=0;i<maxdigits;i++){
                a[i]*=base;
                a[i]+=b;
                b=a[i]/10;
                a[i]%=10;
            }
    }
}
int main()
{
    int base=2;
    int pow=100000;
    n=log10(2)*pow+1;
    printf("Digits=%d\n",n);
    ipow(base,pow,n);
    for(int i=n-1;i>=0;i--){
        printf("%d",a[i]);
    }
    return 0;
}

Я также написал код для возведения в степень путем возведения в квадрат, но с неоптимизированной функцией умножения. Который кажется быстрее, чем приведенная выше реализация.

#define MAX 30103
int a[MAX];
int b[MAX];
int z[MAX];
//stores product in x[]; mul of large arrays implemented in n^2 complexity
//n and m are no of digits in x[] and y[]
//returns no of digits in product
int mul(int x[],int y[],int n,int m){
    for(int i=0;i<n+m;i++)
        z[i]=0;
    for(int j=0;j<m;j++){
        int c=0;
        for(int i=0;i<n+m;i++){
            z[i+j]+=x[i]*y[j];
            z[i+j]+=c;
            c=z[i+j]/10;
            z[i+j]%=10;
        }
    }
    for(int i=0;i<n+m;i++){
            x[i]=z[i];
    }
    if(x[n+m-1]==0)
        return n+m-1;
    return n+m;
}
//stores answer in x[]
int ipow(int base, int exp)
{
    int n=1,m=0;
    for(int i=0;base>0;i++){
        b[i]=base%10;
        base/=10;
        m++;
    }
    a[0]=1;
    for (;;)
    {
        if (exp & 1)
            n=mul(a,b,n,m);
        exp >>= 1;
        if (!exp)
            break;
        m=mul(b,b,m,m);
    }
}
int main()
{
    int base=2;
    int pow=100000;
    n=log10(2)*pow+1;
    printf("Digits=%d\n",n);
    ipow(base,pow);
    printf("\n");
    for(int i=n-1;i>=0;i--){
        printf("%d",a[i]);
    }
    return 0;
}

Answer 5

Это довольно наивное и неэффективное решение.Как и просили, числа представлены в виде массива десятичных цифр.Мы вычисляем экспоненту 2 ⁿ путем повторного добавления числа 2 к себе: начнем с e := 2 и повторим e := e + e n раз.

Чтобы придумать верхнюю границу дляДля длины нашего массива digits мы используем следующий подход:

• Представление числа x в базе b имеет ⌈log _b (x) ⌉ цифр.
• Сравнивая количество цифр между двоичным и десятичным представлением любого числа x, мы обнаруживаем, что они отключаются только на постоянный коэффициент, если пренебречь округлением (⌈⌉).
  log ₂ (x) / log ₁₀ (x) = 1 / log ₁₀ (2) = 3.3219 ...> 3
• 2 ⁿ имеетlog ₂ (2 ⁿ ) = n двоичных цифр.
• Следовательно, 2 ⁿ имеет около n / 3 десятичных цифр.Из-за проблем округления мы добавляем +1 к этому.

void print(int digits[], int length) {
    for (int i = length - 1; i >= 0; --i)
        printf("%d", digits[i]);
    printf("\n");
}
void times2(int digits[], int length) {
    int carry = 0;
    for (int i = 0; i < length; ++i) {
        int d = 2 * digits[i] + carry;
        digits[i] = d % 10;
        carry = d / 10;
    }
}
int lengthOfPow2(int exponent) {
    return exponent / 3 + 1;
}
// works only for epxonents > 0
void pow2(int digits[], int length, int exponent) {
    memset(digits, 0, sizeof(int) * length);
    digits[0] = 2;
    for (int i = 1; i < exponent; ++i)
        times2(digits, length);
}
int main() {
    int n = 100000;
    int length = lengthOfPow2(n);
    int digits[length];
    pow2(digits, length, n);
    print(digits, length);
    return 0;
}

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

diff \
  <(compiledProgram | sed 's/^0*//' | tr -d '\n') \
  <(bc <<< '2^100000' | tr -d '\n\\')

Как уже указывалось, это решение не очень эффективно.Скомпилированное с clang -O2 вычисление 2 ^100'000 заняло 8 секунд на Intel i5-4570 (3,2 ГГц).

Следующим шагом для ускорения этого процесса будет повторение куба вашегочисло вместо многократного умножения на 2. Даже при наивной реализации шага куба это должно быть быстрее, чем реализация, представленная в этом ответе.

Если вам нужно быть еще более эффективным, вы можете реализовать шаг куба, используячто-то вроде алгоритма Карацубы или даже быстрого преобразования Фурье (БПФ).С подходом кубирования и БПФ вы можете вычислить 2 ⁿ с точностью до O (n · log (n)) (может быть дополнительный коэффициент log (log (n)) из-за проблем округления в FFT).

Answer 6

Шаг 1: Решите, как вы собираетесь представлять бигнум

Для этого уже есть библиотеки. Библиотека *1003* * Multiple Precision Integer *1003* является широко используемой опцией. (Но, согласно вашему редактированию, это не вариант. Вы все еще можете взглянуть на некоторых из них, чтобы увидеть, как они работают, но это не обязательно.)

Если вы хотите свернуть свои собственные, я не рекомендую хранить десятичные цифры. Если вы сделаете это, вам нужно будет преобразовывать двоичное представление в двоичное представление и обратно всякий раз, когда вы хотите выполнить арифметику с компонентами. Лучше иметь что-то вроде связанного списка uint32_t s вместе со знаковым битом. Вы можете преобразовать из / в десятичное число, когда хотите читать и писать, но выполняйте математику в двоичном формате.

Шаг 2: реализовать возведение в степень

Здесь я буду предполагать реализацию связанного списка bignum; Вы можете адаптировать алгоритмы по мере необходимости.

Если вы просто рассчитываете степень 2, это легко. За ним следует 1, за которым следуют N 0, поэтому, если в каждом блоке хранится М битов, и вы хотите представить 2^N, то просто укажите floor(N/M) блоков всех 0 и сохраните 1 << (N % M) в самом значимом блоке.

Если вы хотите эффективно возвести возведение в степень с произвольными основаниями, вы должны использовать возведение путем возведения в квадрат . Идея заключается в том, что если вы хотите вычислить 3 ^ 20, вы не умножаете 3 * 3 * 3 * ... * 3. Скорее, вы вычисляете 3^2 = 3 * 3. Тогда 3^4 = 3^2 * 3^2. 3^8 = 3^4 * 3^4. 3^16 = 3^8 * 3^8. И вы сохраняете каждый из этих промежуточных результатов на ходу. Затем, как только вы достигнете точки, в которой возведение в квадрат снова приведет к большему числу, чем вы хотите, вы прекратите возводить в квадрат и собрать окончательный результат из имеющихся у вас фигур. В этом случае 3^20 = 3^16 * 3^4.

Этот подход вычисляет окончательный результат за 5 шагов вместо 20, и, поскольку время является логарифмическим с точки зрения показателя степени, выигрыш в скорости становится более выраженным, чем больше показатель степени. Даже вычисление 3 ^ 100000 требует только 21 умножения.

Не существует умного подхода к умножению, о котором я знаю; вы, вероятно, можете просто сделать что-то в соответствии с базовым алгоритмом умножения длинных символов, который вы изучили в начальной школе, но на уровне блоков: причина, по которой мы использовали uint32_t s раньше вместо uint64_t, заключается в том, что мы можем привести операнды к большего типа и умножьте их без риска потери битов переноса для переполнения.

Преобразовать из двоичного в десятичное для печати

Сначала найдите наибольшее значение, кратное 10, меньше вашего числа.
Я оставляю выполнение этого эффективно в качестве упражнения для читателя, но вы, вероятно, можете управлять им, возводя возведение в квадрат, возводя в квадрат, чтобы найти верхнюю границу, а затем вычитая различные сохраненные промежуточные значения, чтобы перейти к действительному значению быстрее, чем вы делите на 10 раз.

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

Но как бы вы его не получили, у вас есть q, такое, что q = k * 10, 10 * q > n, q <= n, вы можете просто циклически проходить одну десятичную цифру за раз:

for (; q; q /= 10) {
   int digit = n / q; //truncated down to floor(n/q)
   printf("%d", digit);
   n -= digit * q;
}

Возможно, в литературе где-то есть более эффективный метод, но я не знаком с одним из них. Но это не главное, если нам нужно только сделать неэффективную часть при написании вывода; это медленно независимо от алгоритма. Я имею в виду, что для печати всех 100 000 цифр может потребоваться миллисекунда или две. Это не имеет значения, когда мы показываем число для потребления человеком, но если бы нам пришлось ждать миллисекунду как часть вычисления в цикле, это сложилось бы и стало бы ужасно неэффективным. Вот почему мы никогда не храним числа в десятичном представлении: представляя их как двоичное внутренне, мы выполняем неэффективные части один раз на входе и один раз на выходе, но все между ними быстро.