сдвиг от двоичного к десятичному основанию

Question

Мне нужен алгоритм, который преобразует целое число без знака произвольного размера (которое хранится в двоичном формате) в десятичное.то есть, чтобы сделать его читаемым человеком;)
В настоящее время я использую, возможно (или очевидно) несколько наивный способ непрерывного вычисления модуля и остатка путем деления на десять.
К сожалению, скорость немного ... хромает.

например, я вычисляю 2000 ^ 4000 (с моей библиотекой bignum), что занимает примерно 1,5 секунды (без пламени, пожалуйста, xD).Однако распечатка, включая необходимое базовое преобразование, занимает около 15 минут, что довольно раздражает.

Я проверил bc, который выполняет обе операции намного менее чем за одну секунду.
Как это происходит?(Не умножение с FFT и не только с базовым преобразованием)

Answer 1

В настоящее время я использую, возможно (или очевидно) несколько наивный способ непрерывного вычисления модуля и остатка путем деления на десять.
Тогда у вас должна быть O(n^2) сложность, которая должна быть намного лучше, чем 15 минут.

Хотя стоит посмотреть, как именно вы делите на 10.

1. Убедитесь, что вы применяете не общее деление длинных на длинные, а более простой алгоритм деления длинных чисел на стандартные.
2. Убедитесь, что вы повторно используете память. Выделение блоков по 10 Кбайт 10000 раз наверняка ухудшит вашу производительность.

редактировать
Как разделить длинное двоичное число на 10 за один проход и получить результат и напоминание. Без дополнительной памяти.
Простой псевдокод (a[0] является цифрой высшего порядка)

int r = 0;
for (int i = 0; i < n; ++i) {
    r = r * 2 + a[i];
    a[i] = r / 10;
    r = r % 10;
}

Давайте рассмотрим пример, число 100111011 = 315.

Шаг 0: r = 1, a[0] = 0
Шаг 1: r = 2, a[1] = 0
Шаг 2: r = 4, a[2] = 0
Шаг 3: r = 9, a[3] = 0
Шаг 4: r = 9, a[4] = 1
Шаг 5: r = 9, a[5] = 1
Шаг 6: r = 8, a[6] = 1
Шаг 7: r = 7, a[7] = 1
Шаг 8: r = 5, a[8] = 1

Итак, напоминание - 5, а результат - 000011111 = 31.

Answer 2

Я думаю, что bc использует 10 ^ n в качестве основы вместо 2. Так что каждая внутренняя "цифра" - это просто n десятичных цифр, и, по крайней мере, для десятичного ввода / вывода проблема становится тривиальной.

Answer 3

Нет необходимости использовать возведение в степень:

#include "stdio.h"
#include "stdlib.h"
#include "string.h"

int main(){
    char a[] = "10011";
    unsigned long int res= 0;
    int i;

    for(i = 0; i < strlen(a); i++){
        res = (res<<1) + (a[i]-'0');
    }

    printf("%d",res);
    return 0;
}

ПЕРВОЕ ОБНОВЛЕНИЕ

Теперь длина не должна быть проблемой ...

#include "stdio.h"
#include "stdlib.h"
#include "string.h"

char *doubles(char *);
char *sum(char *,int);

int main(){
    char a[] = "10011";
    char *res = calloc(2,sizeof(char));
    int i;

    res[0] = '0';
    for(i = 0; i < strlen(a); i++){
        res = sum(doubles(res),(a[i]-'0'));
    }

    printf("%s",res);
    return 0;
}

char *doubles(char *s){
    int i,len = strlen(s),t = 0;
    char *d;
    d = calloc(len+1,sizeof(char));
    for(i = 0; i < len; i++){
        t = ((s[len-i-1]-'0')<<1) + t;

        d[len-i] = ('0' + (t%10));
        t = t/10;
    }

    d[0] = t+'0';

    return (d[0] == '0')?d+1:d;
}

char *sum(char *s,int n){
    int i, len = strlen(s),t = n;
    char *d = calloc(len+1,sizeof(char));

    for(i = 0; i < len ; i++){
        t = (s[len-i-1]-'0') + t;
        d[len-i] = ('0' + (t%10));
        t = t/10;
    }
    d[0] = t+'0';

    return (d[0] == '0')?d+1:d;
}