将二进制转换为十进制的最快方法？

Question

我有四个无符号的32位整数,表示无符号的128位整数,以小端顺序表示:

typedef struct {
    unsigned int part[4];
} bigint_t;

我想将此数字转换为十进制字符串表示形式并将其输出到文件中.

现在,我正在使用一个bigint_divmod10函数将数字除以10,跟踪余数.我重复调用此函数,将余数作为数字输出,直到数字为零.这很慢.这是最快的方法吗？如果是这样,有没有一种聪明的方法来实现我没有看到的这个功能？我试过看GMP get_str.c,但我发现它非常难以理解.

编辑:这是我能够为divmod10函数提供的最快的代码:

static unsigned uint128_divmod10(uint128 *value)
{
    unsigned int a = value->word[3];
    unsigned int b = value->word[2];
    unsigned int c = value->word[1];
    unsigned int d = value->word[0];

    unsigned int diva = a / 5;
    unsigned int divb = b / 5;
    unsigned int divc = c / 5;
    unsigned int divd = d / 5;

    value->word[3] = diva;
    value->word[2] = divb;
    value->word[1] = divc;
    value->word[0] = divd;

    unsigned int moda = a - diva*5;
    unsigned int modb = b - divb*5;
    unsigned int modc = c - divc*5;
    unsigned int modd = d - divd*5;

    unsigned int mod = 0;
    mod += moda;
    unsigned int carryb = mod*858993459;
    mod += modb;
    if (mod >= 5) {
        mod -= 5;
        carryb++;
    }
    unsigned int carryc = mod*858993459;
    mod += modc;
    if (mod >= 5) {
        mod -= 5;
        carryc++;
    }
    unsigned int carryd = mod*858993459;
    mod += modd;
    if (mod >= 5) {
        mod -= 5;
        carryd++;
    }

    uint128_add(value, carryd, 0);
    uint128_add(value, carryc, 1);
    uint128_add(value, carryb, 2);

    if (value->word[0] & 1) {
        mod += 5;
    }
    uint128_shift(value, -1);
    return mod;
}

其中add函数定义为:

static void uint128_add(uint128 *value, unsigned int k, unsigned int pos)
{
    unsigned int a = value->word[pos];
    value->word[pos] += k;
    if (value->word[pos] < a) {
        // overflow
        for (int i=pos+1; i<4; i++) {
            value->word[i]++;
            if (value->word[i]) {
                break;
            }
        }
    }
}

Answer 1

这取决于您对这些数字还做了什么。您可以权衡空间效率的轻微损失和多精度算术效率的适度损失，以换取非常高效的十进制转换。关键是要以 10 的幂而不是 2 的幂为基数进行多精度算术。

例如，您可以使用基数 10,000，将一位数字打包到 16 位字中，然后对 32 位整数中的数字进行算术运算。（如果您使用的是 64 位计算机，则可以将其加倍并以 1,000,000,000 为基数。）这种代码在时间上相对高效，但不如使用 2 的本机幂那么快，因为您无法利用硬件上的进位位。而且你不能用相同的位数表示尽可能多的整数。但它在十进制之间的转换方面非常出色，因为您无需任何长除法即可转换各个数字。

如果您需要表示从零到 的整个数字范围((1 << 128) - 1)，您仍然可以这样做，但添加一个额外的数字，这样您的数字就会更大。

如果事实证明您确实需要额外的空间/速度（也许您正在进行大量加密 128 位计算），那么同时将 div/mod 除以 10 的方法是我所知道的最快的方法。唯一的另一个技巧是，如果小整数很常见，您可以特殊处理它们。（也就是说，如果三个最高有效的32位字都为零，则只需使用本机除法进行转换即可。）

有没有一种聪明的方法来实现我没有看到的这个功能？

Dave Hanson 的《C 接口和实现》中有一个关于多精度算术的冗长章节。将大数除以一位数是一种特殊情况，具有以下高效实现：

int XP_quotient(int n, T z, T x, int y) {
    int i;
    unsigned carry = 0;
    for (i = n - 1; i >= 0; i--) {
        carry = carry*BASE + x[i];
        z[i] = carry/y;
        carry %= y;
    }
    return carry;
}

为了充分理解，拥有这本书确实很有帮助，但是源代码仍然比 GNU 源代码更容易理解。您可以轻松地将其调整为使用基数 10,000（目前使用基数 256）。

摘要：如果您的性能瓶颈是转换为十进制，请以 10 的幂为基数实现多精度算术。如果您的机器的本机字大小为 32 并且您使用的是 C 代码，则在 16 位字中使用 10,000。