二进制到十进制的基移

Question

我需要一种将任意大小的无符号整数（以二进制格式存储）转换为十进制的算法。即使其易于阅读;)
我目前使用可能（或显然）有点幼稚的方式通过除以十来连续计算模数和余数。
不幸的是速度有点……蹩脚。

例如 我计算 2000^4000（使用我的 bignum 库）大约需要 1.5 秒（请不要着火 xD）。然而，包括必要的基本转换在内的打印需要大约 15 分钟，这非常烦人。

我已经测试过 bc，它在不到一秒的时间内完成了这两项操作。
它是如何做到的？ （不是 fft 的乘法以及任何基本转换）

Answer 1

我目前使用可能（或显然）有点幼稚的方式通过除以十来连续计算模数和余数。
那么您的复杂度应该是 O(n^2)，这应该比 15 分钟要好得多。

不过，值得一看的是如何除以 10。

1. 确保您应用的不是长数除以长数的通用除法，而是应用长数除以标准数的更简单算法。
2. 确保重用内存。分配 10Kb 块 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;
}